Delannoy number

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

Image:Delannoy3x3.svg

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

The Delannoy array is an infinite matrix of the Delannoy numbers:{{citation

| last = Sulanke | first = Robert A.

| title = Objects counted by the central Delannoy numbers

| year = 2003

| journal = Journal of Integer Sequences

| volume = 6

| issue = 1

| page = Article 03.1.5

| bibcode = 2003JIntS...6...15S

| mr = 1971435

| url = http://www.emis.de/journals/JIS/VOL6/Sulanke/delannoy.pdf}}

:

In this array, the numbers in the first row are all one, the numbers in the second row are the odd numbers, the numbers in the third row are the centered square numbers, and the numbers in the fourth row are the centered octahedral numbers. Alternatively, the same numbers can be arranged in a triangular array resembling Pascal's triangle, also called the tribonacci triangle,{{Cite OEIS|A008288|name=Square array of Delannoy numbers D(i,j) (i >= 0, j >= 0) read by antidiagonals}} 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 1

1 11 41 63 41 11 1

The central Delannoy numbers D(n) = D(n, n) are the numbers for a square n × n grid. The first few central Delannoy numbers (starting with n = 0) are:

:1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ... {{OEIS|id=A001850}}.

For $k$ diagonal (i.e. northeast) steps, there must be $m-k$ steps in the $x$ direction and $n-k$ steps in the $y$ direction in order to reach the point $(m,\; n)$; as these steps can be performed in any order, the number of such paths is given by the multinomial coefficient

$\backslash binom\{m+n-k\}\{k\; ,\; m-k\; ,\; n-k\}\; =\; \backslash binom\{m+n-k\}\{m\}\; \backslash binom\{m\}\{k\}$. Hence, one gets the closed-form expression

:$D(m,n)\; =\; \backslash sum\_\{k=0\}^\{\backslash min(m,n)\}\; \backslash binom\{m+n-k\}\{m\}\; \backslash binom\{m\}\{k\}\; .$

An alternative expression is given by

:$D(m,n)\; =\; \backslash sum\_\{k=0\}^\{\backslash min(m,n)\}\; \backslash binom\{m\}\{k\}\; \backslash binom\{n\}\{k\}\; 2^k$

or by the infinite series

:$D(m,n)\; =\; \backslash sum\_\{k=0\}^\backslash infty\; \backslash frac\{1\}\{2^\{k+1\}\}\; \backslash binom\{k\}\{n\}\; \backslash binom\{k\}\{m\}.$

And also

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

where $A(m,k)$ is given with {{OEIS|id=A266213}}.

The basic recurrence relation for the Delannoy numbers is easily seen to be

:

This recurrence relation also leads directly to the generating function

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

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

:$D(n)\; =\; \backslash sum\_\{k=0\}^n\; \backslash binom\{n\}\{k\}\; \backslash binom\{n+k\}\{k\}\; ,$

while the second expression above yields

:$D(n)\; =\; \backslash sum\_\{k=0\}^n\; \backslash binom\{n\}\{k\}^2\; 2^k\; .$

The central Delannoy numbers satisfy also a three-term recurrence relationship among themselves,{{cite journal |last1=Peart |first1=Paul |last2=Woan |first2=Wen-Jin |title=A bijective proof of the Delannoy recurrence |year=2002 |journal=Congressus Numerantium |volume=158 |pages=29–33 |issn=0384-9864 |zbl=1030.05003 |mr = 1985142}}

:$n\; D(n)\; =\; 3(2n-1)D(n-1)\; -\; (n-1)D(n-2)\; ,$

and have a generating function

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

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

:$D(n)\; =\; \backslash frac\{c\; \backslash ,\; \backslash alpha^n\}\{\backslash sqrt\{n\}\}\; \backslash ,\; (1\; +\; O(n^\{-1\}))$

where

$\backslash alpha\; =\; 3\; +\; 2\; \backslash sqrt\{2\}\; \backslash approx\; 5.828$

and

$c\; =\; (4\; \backslash pi\; (3\; \backslash sqrt\{2\}\; -\; 4))^\{-1/2\}\; \backslash approx\; 0.5727$.

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

{{reflist}}

• {{MathWorld|title=Delannoy Number|urlname=DelannoyNumber}}

{{Classes of natural numbers}}

Category:Eponymous numbers in mathematics

Category:Integer sequences

Category:Triangles of numbers

Category:Combinatorics