0,2

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

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.

Frits Beukers, Arithmetic properties of Picard-Fuchs equations, Séminaire de Théorie des nombres de Paris, 1982-83, Birkhäuser 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.

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?

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

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

Paul 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.

H. Bateman, Some problems in potential theory, Messenger Math., 52 (1922), 71-78. [Annotated scanned copy]

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

F. D. Cunden, Statistical distribution of the Wigner-Smith time-delay matrix for chaotic cavities, arXiv preprint arXiv:1412.2172 [cond-mat.mes-hall], 2014.

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

M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747, 2014

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

Seth Finkelstein, Letter to N. J. A. Sloane, Mar 24 1990, with attachments.

S. Garrabrant, I. Pak, Counting with irrational tiles, arXiv:1407.8222, 2014.

Nick Hobson, Python program for this sequence

Milan Janjic, Two Enumerative Functions

D. E. Knuth and N. J. A. Sloane, Correspondence, December 1999

R. Mestrovic, Lucas' theorem: its generalizations, extensions and applications (1878--2014), arXiv preprint arXiv:1409.3820, 2014

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.

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(n) = a(-1 - n) for all n in Z. - 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

a(n) = hypergeom([-n, -n], [1], 2). - Peter Luschny, Nov 19 2014

a(n) = Sum_{k=0..n/2} C(n-k,k) * 3^(n-2*k) * 2^k * C(n,k). - Vladimir Kruchinin, Jun 29 2015

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

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

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 *)

a[ n_] := With[ {m = If[n < 0, -1 - n, n]}, SeriesCoefficient[ (1 - 6 x + x^2)^(-1/2), {x, 0, m}]]; (* Michael Somos, Jun 10 2015 *)

(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); /* 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

(Sage)

a = lambda n: hypergeometric([-n, -n], [1], 2)

[simplify(a(n)) for n in range(23)] # Peter Luschny, Nov 19 2014

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

nonn,easy,nice,changed

N. J. A. Sloane

New name and reference Sep 15 1995

Formula and more references from Don Knuth, May 15 1996

approved