0,2

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

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 (benoit7848c(AT)orange.fr), 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 (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), Aug 02 2002

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

Row sums of A063007 and A105870. - Paul Barry (pbarry(AT)wit.ie), 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 (jvospost2(AT)yahoo.com), May 22 2005

The Hankel transform (see A001906 for definition) of this sequence is A036442 : 1, 4, 32, 512, 16384, ... . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), 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. - Nour-Eddine Fahssi (fahssin(AT)yahoo.fr), Jan 27 2008

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.

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.

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

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.

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.

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

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.

T. D. Noe, Table of n, a(n) for n = 0..200

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

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

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

Nick Hobson, Python program for this sequence

Milan Janjic, Two Enumerative Functions

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

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

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

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 (se16(AT)btinternet.com), 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+ ... ) - Mike Hirschhorn (mikeh(AT)maths.unsw.edu.au)

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 (benoit7848c(AT)orange.fr), Feb 13 2003

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

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

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

a(n) = Sum_{k>=n} binomial(k, n)^2/2^(k+1). - Vladeta Jovovic (vladeta(AT)Eunet.yu), 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).

Comment from Peter John (peter.john(AT)tu-ilmenau.de), Oct 19 2006: 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.

Coefficient of x^n in (1 + 3*x + 2*x^2)^n. - Nour-Eddine Fahssi (fahssin(AT)yahoo.fr), Jan 11 2008

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

{Dela[ 0 ], Dela[ 1 ]} = {1, 3}; Dela[ n_ ] := Dela[ n ] = (3(2n-1) Dela[ n-1 ] - (n-1) Dela[ n-2 ])/n

(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 program 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+3x+2x^2)^n, n)) - Paul Barry (pbarry(AT)wit.ie), Aug 22 2007

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

Main diagonal of A064861.

Cf. A026003, A052141, A084773.

Adjacent sequences: A001847 A001848 A001849 this_sequence A001851 A001852 A001853

Sequence in context: A092467 A034478 A026715 this_sequence A130525 A000259 A007855

nonn,easy,nice

njas

New name and reference Sep 15 1995. Formula and more references from D. E. Knuth May 15 1996.

More terms from James A. Sellers (sellersj(AT)math.psu.edu), Feb 16 2000