Delannoy number

Named after	Henri–Auguste Delannoy
No. of known terms	infinity
Formula	${\displaystyle D(m,n)=\sum _{k=0}^{min(m,n)}(\genfrac{}{}{0ex}{}{m}{k})(\genfrac{}{}{0ex}{}{n}{k})2^k}$
OEIS index	A008288 Square array of Delannoy

Inmathematics, aDelannoy number${\displaystyle D}$ counts the paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (m,n), using only single steps north, northeast, or east. The Delannoy numbers are named after French army officer and amateur mathematicianHenri Delannoy.^[1]

The Delannoy number${\displaystyle D(m,n)}$ also counts theglobal alignments of two sequences of lengths${\displaystyle m}$ and${\displaystyle n}$,^[2] the points in anm-dimensionalinteger lattice orcross polytope which are at mostn steps from the origin,^[3] and, incellular automata, the cells in anm-dimensionalvon Neumann neighborhood of radiusn.^[4]

The Delannoy numberD(3, 3) equals 63. The following figure illustrates the 63 Delannoy paths from (0, 0) to (3, 3):

The subset of paths that do not rise above the SW–NE diagonal are counted by a related family of numbers, theSchröder numbers.

TheDelannoy array is aninfinite matrix of the Delannoy numbers:^[5]

m n	0	1	2	3	4	5	6	7	8
0	1	1	1	1	1	1	1	1	1
1	1	3	5	7	9	11	13	15	17
2	1	5	13	25	41	61	85	113	145
3	1	7	25	63	129	231	377	575	833
4	1	9	41	129	321	681	1289	2241	3649
5	1	11	61	231	681	1683	3653	7183	13073
6	1	13	85	377	1289	3653	8989	19825	40081
7	1	15	113	575	2241	7183	19825	48639	108545
8	1	17	145	833	3649	13073	40081	108545	265729
9	1	19	181	1159	5641	22363	75517	224143	598417

In this array, the numbers in the first row are all one, the numbers in the second row are theodd numbers, the numbers in the third row are thecentered square numbers, and the numbers in the fourth row are thecentered octahedral numbers. Alternatively, the same numbers can be arranged in atriangular array resemblingPascal's triangle, also called thetribonacci triangle,^[6] in which each number is the sum of the three numbers above it:

            1          1   1        1   3   1      1   5   5   1    1   7  13   7   1  1   9  25  25   9   11  11  41  63  41  11   1

The row sums of the triangle give successivePell numbers 1, 2, 5, 12, 29, 70, 169,... the sums of the rising diagonals give thetribonacci numbers 1, 1, 2, 4, 7, 13, 24,... ^[7]

Thecentral Delannoy numbersD(n) =D(n,n) are the numbers for a squaren ×n grid. The first few central Delannoy numbers (starting withn = 0) are:

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ... (sequenceA001850 in theOEIS).

For${\displaystyle k}$ diagonal (i.e. northeast) steps, there must be${\displaystyle m-k}$ steps in the${\displaystyle x}$ direction and${\displaystyle n-k}$ steps in the${\displaystyle y}$ direction in order to reach the point${\displaystyle (m,n)}$; as these steps can be performed in any order, the number of such paths is given by themultinomial coefficient${\displaystyle (\genfrac{}{}{0ex}{}{m+n-k}{k,m-k,n-k})=(\genfrac{}{}{0ex}{}{m+n-k}{m})(\genfrac{}{}{0ex}{}{m}{k})}$. Hence, one gets the closed-form expression

${\displaystyle D(m,n)=\sum _{k=0}^{min(m,n)}(\genfrac{}{}{0ex}{}{m+n-k}{m})(\genfrac{}{}{0ex}{}{m}{k}).}$

An alternative expression is given by

${\displaystyle D(m,n)=\sum _{k=0}^{min(m,n)}(\genfrac{}{}{0ex}{}{m}{k})(\genfrac{}{}{0ex}{}{n}{k})2^k}$

or by the infinite series

${\displaystyle D(m,n)=\sum _{k=0}^{\mathrm{\infty }}\frac{1}{2^{k+1}}(\genfrac{}{}{0ex}{}{k}{n})(\genfrac{}{}{0ex}{}{k}{m}).}$

And also

${\displaystyle D(m,n)=\sum _{k=0}^{n}A(m,k),}$

where${\displaystyle A(m,k)}$ is given with (sequenceA266213 in theOEIS).

The basicrecurrence relation for the Delannoy numbers is easily seen to be

This recurrence relation also leads directly to thegenerating function

${\displaystyle \sum _{m,n=0}^{\mathrm{\infty }}D(m,n)x^m{y}^n=(1-x-y-xy{)}^{-1}.}$

Substituting${\displaystyle m=n}$ in the first closed form expression above, replacing${\displaystyle k\leftrightarrow n-k}$, and a little algebra, gives

${\displaystyle D(n)=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n+k}{k}),}$

while the second expression above yields

${\displaystyle D(n)=\sum _{k=0}^n{(\genfrac{}{}{0ex}{}{n}{k})}^2{2}^k.}$

The central Delannoy numbers satisfy also a three-term recurrence relationship among themselves,^[8]

${\displaystyle nD(n)=3(2n-1)D(n-1)-(n-1)D(n-2),}$

and have a generating function

${\displaystyle \sum _{n=0}^{\mathrm{\infty }}D(n)x^n=(1-6x+x^2{)}^{-1/2}.}$

The leading asymptotic behavior of the central Delannoy numbers is given by

${\displaystyle D(n)=\frac{c{\alpha }^n}{\sqrt{n}}(1+O(n^{-1}))}$

where${\displaystyle \alpha =3+2\sqrt{2}\approx 5.828}$and${\displaystyle c=(4\pi (3\sqrt{2}-4){)}^{-1/2}\approx 0.5727}$.

• Motzkin number
• Narayana number
• Schroder-Hipparchus number
• Schroder number

• Weisstein, Eric W."Delannoy Number".MathWorld.

• Integer sequences
• Triangles of numbers
• Combinatorics

• Articles with short description
• Short description matches Wikidata