login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001850 Central Delannoy numbers: Sum_{k=0..n} C(n,k)*C(n+k,k).
(Formerly M2942 N1184)
102
1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563, 8097453, 45046719, 251595969, 1409933619, 7923848253, 44642381823, 252055236609, 1425834724419, 8079317057869, 45849429914943, 260543813797441, 1482376214227923, 8443414161166173 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Number of paths from (0,0) to (n,n) in an n X n grid using only steps North, Northeast and East (i.e., steps (1,0), (1,1), and (0,1)).

Also the number of ways of aligning two sequences (e.g., of nucleotides or amino acids) of length n, with at most 2*n gaps (-) inserted, so that while unnecessary gappings: - -a a- - are forbidden, both b- and -b are allowed. (If only other of the latter is allowed, then the sequence A000984 gives the number of alignments.) There is an easy bijection from grid walks given by Dickau to such set of alignments (e.g., the straight diagonal corresponds to the perfect alignment with no gaps). - Antti Karttunen, Oct 10 2001

Also main diagonal of array defined by m(i,1)=m(1,j)=1, m(i,j)=m(i-1,j-1)+m(i-1,j)+m(i,j-1) - Benoit Cloitre, May 03 2002

a(n) is the number of n-matchings of a comb-like graph with 2n teeth. Example: a(2)=13 because the graph consisting of a horizontal path ABCD and the teeth Aa, Bb, Cc, Dd has 13 2-matchings: any of the six possible pairs of teeth and {Aa, BC}, {Aa, CD}, {Bb, CD}, {Cc, AB}, {Dd, AB}, {Dd, BC}, {AB, CD}. - Emeric Deutsch, Jul 02 2002

Number of ordered trees with 2n+1 edges, having root of odd degree, nonroot nodes of outdegree at most 2 and branches of odd length. - Emeric Deutsch, Aug 02 2002

The sum of the first n coefficients of ((1 - x) / (1 - 2*x))^n is a(n-1). - Michael Somos, Sep 28 2003

Row sums of A063007 and A105870. - Paul Barry, Apr 23 2005

Prime central Delannoy numbers include a(1) = 3, a(2) = 13, a(8) = 265729. Note that these begin a(2^0), a(2^1), a(2^3). Semiprime central Delannoy numbers include a(4) = 321 = 3 * 107, a(6) = 8989 = 89 * 101. - Jonathan Vos Post, May 22 2005

The Hankel transform (see A001906 for definition) of this sequence is A036442 : 1, 4, 32, 512, 16384, ... . - Philippe Deléham, Jul 03 2005

Also number of paths from (0,0) to (n,0) using only steps U=(1,1), H=(1,0) and D=(1,-1), U can have 2 colors and H can have 3 colors. - N-E. Fahssi, Jan 27 2008

Equals row sums of triangle A152250 and INVERT transform of A109980: (1, 2, 8, 36, 172, 852,...). - Gary W. Adamson, Nov 30 2008

Samieinia, p. 3. The number of Khalimsky-continuous functions with codomain Z can give an example of Delannoy numbers. If we consider instead such functions with codomain N, then we get an example of the other numbers, which are called the Schroeder numbers. - Jonathan Vos Post, Mar 27 2009

REFERENCES

J.-M. Autebert et al., Le treillis des Chemins de Delannoy, Discrete Math., 258 (2002), 225-234.

J.-M. Autebert et al., On generalized Delannoy paths, SIAM J. Discrete Math., 16 (2003), 208-223.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

P. Barry, On the Central Coefficients of Riordan Matrices, Journal of Integer Sequences, 16 (2013), #13.5.1.

P. Barry, On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.6.

Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8.- From N. J. A. Sloane, Oct 08 2012

Frits Beukers, Arithmetic properties of Picard-Fuchs equations, S\'eminaire de Th\'eorie des nombres de Paris, 1982-83, Birkh"auser Boston, Inc.

J. S. Caughman et al., A note on lattice chains and Delannoy numbers, Discrete Math., 308 (2008), 2623-2628.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 81.

Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From N. J. A. Sloane, May 01 2012

M. Dziemianczuk, Generalizing Delannoy numbers via counting weighted lattice paths, INTEGERS, 13 (2013), #A54.

M. D. Hirschhorn, How many ways can a king cross the board?, Austral. Math. Soc. Gaz., 27 (2000), 104-106.

P.-Y. Huang, S.-C. Liu, Y.-N. Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.

S. Kaparthi and H. R. Rao, Higher dimensional restricted lattice paths with diagonal steps, Discr. Appl. Math., 31 (1991), 279-289.

D. F. Lawden, On the Solution of Linear Difference Equations, Math. Gaz., 36 (1952), 193-196.

Lily L. Liu, Positivity of three-term recurrence sequences, Electronic J. Combinatorics, 17 (2010), #R57.

L. Moser, King paths on a chessboard, Note 2487, Math. Gaz., 39 (1955) 54 (one page only).

L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Math., 26 (1961), 223-229.

Munarini, Emanuele, Combinatorial properties of the antichains of a garland. Integers, 9 (2009), 353-374.

M. Shattuck, On the zeros of some polynomials with combinatorial coefficients, Annales Mathematicae et Informaticae, 42 (2013) pp. 93-101, http://ami.ektf.hu.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 2, 1999; see Example 6.3.8 and Problem 6.49.

R. G. Stanton and D. D. Cowan, Note on a "square" functional equation, SIAM Rev., 12 (1970), 277-279.

R. A. Sulanke et al., Another description of the central Delannoy numbers, Problem 10894, Amer. Math. Monthly, 110 (No. 5, 2003), 443-444.

Marius Tarnauceanu, The number of fuzzy subgroups of finite cyclic groups and Delannoy numbers, European Journal of Combinatorics, Volume 30, Issue 1, January 2009, Pages 283-287.

E. X. W. Xia and O. X. M. Yao, A Criterion for the Log-Convexity of Combinatorial Sequences, The Electronic Journal of Combinatorics, 20 (2013), #P3.

LINKS

Chai Wah Wu, Table of n, a(n) for n = 0..1308 (all terms < 10^1000, first 201 terms from T. D. Noe)

C. Banderier and S. Schwer, Why Delannoy numbers?

J. Cigler, Some nice Hankel determinants. Arxiv preprint arXiv:1109.1449, 2011.

E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.

R. M. Dickau, Delannoy and Motzkin Numbers [Many illustrations]

R. M. Dickau, The 13 paths in a 4 X 4 grid

Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, Arxiv preprint arXiv:1203.6792, 2012. - From N. J. A. Sloane, Oct 03 2012

Nick Hobson, Python program for this sequence

Milan Janjic, Two Enumerative Functions

Tony D. Noe, On the Divisibility of Generalized Central Trinomial Coefficients, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.7.

P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.

R. Pemantle and M. C. Wilson, Asymptotics of multivariate sequences, I: smooth points of the singular variety

E. Rowland, D. Zeilberger, A Case Study in Meta-AUTOMATION: AUTOMATIC Generation of Congruence AUTOMATA For Combinatorial Sequences, arXiv preprint arXiv:1311.4776, 2013

Shiva Samieinia, The number of continuous curves in digital geometry, Research Reports in Mathematics, Number 3, Dec 22 2008.

T. Sillke, The Delannoy numbers

R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1.

R. A. Sulanke, Objects Counted by the Central Delannoy Numbers , Journal of Integer Sequences, Vol. 5 (2002), Article 03.1.5

Zhi-Wei Sun, On Delannoy numbers and Schroeder numbers, Journal of Number Theory, Volume 131, Issue 12, December 2011, Pages 2387-2397; http://www.sciencedirect.com/science/article/pii/S0022314X11001715.; arXiv 1009.2486v4.

Eric Weisstein's World of Mathematics, Delannoy Number

Eric Weisstein's World of Mathematics, Schmidt's Problem

W.-J. Woan, Hankel Matrices and Lattice Paths, J. Integer Sequences, 4 (2001), #01.1.2.

FORMULA

P_n(3), where P_n is n-th Legendre polynomial.

G.f.: 1 / sqrt(1 - 6*x + x^2).

a(n) =a(n-1)+2*A002002(n) =sum{j}[A063007(n, j)] - Henry Bottomley, Jul 02 2001

Dominant term in asymptotic expansion is binomial(2n, n)/2^(1/4)*((sqrt(2)+1)/2)^(2n+1)*(1+c_1/n+c_2/n^2+ ... ). - Michael David Hirschhorn

a(n) = Sum_{i=0..n} (A000079[i]*A008459[n, i]) = Sum_{i=0..n} (2^i * C(n, i)^2). - Antti Karttunen, Oct 10 2001

a(n) = sum(k=0..n, C(n+k, n-k)*C(2k, k) ). - Benoit Cloitre, Feb 13 2003

a(n) = sum(k=0..n, C(n, k)^2 * 2^k). - Michael Somos, Oct 08 2003

a(n - 1) = coefficient of x^n in A120588(x)^n if n>=0. - Michael Somos, Apr 11 2012

G.f. of a(n-1) = 1 / (1 - x / (1 - 2*x / (1 - 2*x / (1 - x / (1 - 2*x / (1 - x / ...)))))). - Michael Somos, May 11 2012

INVERT transform is A109980. BINOMIAL transform is A080609. BINOMIAL transform of A006139. PSUM transform is A089165. PSUMSIGN transform is A026933. First backward difference is A110170. - Michael Somos, May 11 2012

E.g.f.: exp(3*x)*BesselI(0, 2*sqrt(2)*x). - Vladeta Jovovic, Mar 21 2004

a(n)=sum{k=0..n, C(2n-k, n)C(n, k)}; - Paul Barry, Apr 23 2005

a(n) = Sum_{k>=n} binomial(k, n)^2/2^(k+1). - Vladeta Jovovic, Aug 25 2006

a(-1 - n) = a(n). - Michael Somos, Sep 23 2006

a(-1) = a(0) = 1; n*a(n) = 3*(2*n-1)*a(n-1) - (n-1)*a(n-2). Eq (4) in T. D. Noe's article in JIS 9 (2006) #06.2.7

Define general Delannoy numbers by (i,j>0): d(i,0)=d(0,j)=1=:d(0,0)and d(i,j)=d(i-1,j-1)+d(i-2,j-1)+d(i-1,j). Then a(k)= sum[{d(k,j)^2}+{d(k-1,j)^2}], j>=0. This is a special case of the following formula for general Delannoy numbers: d(k,j)=sum[{d(p,i)*d(n-p,j-i)}+{d(p-1,i)*d(n-p-1,j-i-1)}], where i>=0 and p=0,1,...,n. - Peter E John, Oct 19 2006

Coefficient of x^n in (1 + 3*x + 2*x^2)^n. - N-E. Fahssi, Jan 11 2008

a(n)=A008288(A046092(n)). - Philippe Deléham, Apr 08 2009

G.f.: 1/(1-x-2x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction). - Paul Barry, May 28 2009

G.f.: d/dx log(1/(1-x*A001003(x))). - Vladimir Kruchinin, Apr 19 2011

G.f.: 1/(2*Q(0) + x - 1) where Q(k) = 1 + k*(1-x) - x - x*(k+1)*(k+2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Mar 14 2013

a(n) = sum(k=0..n, C(n,k) * C(n+k,k) ). - Joerg Arndt, May 11 2013

G.f.: G(0), where G(k)= 1 + x*(6-x)*(4*k+1)/(4*k+2 - 2*x*(6-x)*(2*k+1)*(4*k+3)/(x*(6-x)*(4*k+3) + 4*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 22 2013

G.f.: 2/G(0), where G(k)= 1 + 1/( 1 - x*(6-x)*(2*k-1)/(x*(6-x)*(2*k-1) + 2*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 16 2013

G.f.: G(0)/2, where G(k)= 1 + 1/( 1 - x*(6-x)*(2*k+1)/(x*(6-x)*(2*k+1) + 2*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 17 2013

a(n)^2 = Sum_{k=0..n} 2^k * C(2*k, k)^2 * C(n+k, n-k) = A243949(n). - Paul D. Hanna, Aug 17 2014

EXAMPLE

G.f.: 1 + 3*x + 13*x^2 + 63*x^3 + 321*x^4 + 1683*x^5 + 8989*x^6 + ...

MAPLE

seq(add(multinomial(n+k, n-k, k, k), k=0..n), n=0..20); - Zerinvary Lajos, Oct 18 2006

MATHEMATICA

f[n_] := Sum[ Binomial[n, k] Binomial[n + k, k], {k, 0, n}]; Array[f, 21, 0] (* Or *)

a[0] = 1; a[1] = 3; a[n_] := a[n] = (3(2 n - 1)a[n - 1] - (n - 1)a[n - 2])/n; Array[a, 21, 0] (* Or *)

CoefficientList[ Series[1/Sqrt[1 - 6x + x^2], {x, 0, 20}], x] (* Robert G. Wilson v *)

Table[LegendreP[n, 3], {n, 0, 22}] (* Jean-François Alcover, Jul 16 2012, from first formula *)

a[n_] := Hypergeometric2F1[-n, n+1, 1, -1]; Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Feb 26 2013 *)

PROG

(PARI) {a(n) = if( n<0, n = -1 - n); polcoeff( 1 / sqrt(1 - 6*x + x^2 + x * O(x^n)), n)} /* Michael Somos, Sep 23 2006 */

(PARI) {a(n) = if( n<0, n = -1 - n); subst( pollegendre(n), x, 3)} /* Michael Somos, Sep 23 2006 */

(PARI) {a(n) = if( n<0, n = -1 - n); n++; subst( Pol(((1 - x) / (1 - 2*x) + O(x^n))^n), x, 1)} /* Michael Somos, Sep 23 2006 */

(Python) # from Nick Hobson. Replace leading dots by spaces.

.def f(a, b):

.... if a == 0 or b == 0: return 1

.... return f(a, b-1) + f(a-1, b) + f(a-1, b-1)

....

.for n in xrange(7):

.... print f(n, n),

....

(PARI) a(n)=if(n<0, 0, polcoeff((1+3*x+2*x^2)^n, n)) - Paul Barry, Aug 22 2007

(Maxima) a(n):=coeff(expand((1+3*x+2*x^2)^n), x, n);

makelist(a(n), n, 0, 12); [From Emanuele Munarini, Mar 02 2011].

(PARI) /* same as in A092566 but use */

steps=[[1, 0], [0, 1], [1, 1]]; /* Joerg Arndt, Jun 30 2011 */

(PARI) a(n)=sum(k=0, n, binomial(n, k)*binomial(n+k, k)); \\ Joerg Arndt, May 11 2013

(Python)

from gmpy2 import divexact

A001850 = [1, 3]

for n in range(2, 10**3):

....A001850.append(divexact(A001850[-1]*(6*n-3)-(n-1)*A001850[-2], n))

# Chai Wah Wu, Sep 01 2014

CROSSREFS

Cf. A008288, A027618, A047665. a(n)=T(n, n-1), array T as in A049600.

Main diagonal of A064861.

Cf. A026003, A052141, A084773, A152250, A109980, A000129, A078057.

Cf. A243949.

Sequence in context: A092467 A034478 A026715 * A130525 A243280 A000259

Adjacent sequences:  A001847 A001848 A001849 * A001851 A001852 A001853

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

New name and reference Sep 15 1995.

Formula and more references from Don Knuth, May 15 1996.

More terms from James A. Sellers, Feb 16 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 22 04:02 EDT 2014. Contains 247035 sequences.