Delannoy number

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 the multinomial coefficient ${\displaystyle {\binom {m+n-k}{k,m-k,n-k}}={\binom {m+n-k}{m}}{\binom {m}{k}}}$. Hence, one gets the closed-form expression

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

An alternative expression is given by

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

or by the infinite series

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

And also

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

where ${\displaystyle A(m,k)}$ is given with (sequence A266213 in the OEIS).

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

${\displaystyle D(m,n)={\begin{cases}1&{\text{if }}m=0{\text{ or }}n=0\\D(m-1,n)+D(m-1,n-1)+D(m,n-1)&{\text{otherwise}}\end{cases}}}$

This recurrence relation also leads directly to the generating function

${\displaystyle \sum _{m,n=0}^{\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}{\binom {n}{k}}{\binom {n+k}{k}},}$

while the second expression above yields

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

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

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

and have a generating function

${\displaystyle \sum _{n=0}^{\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}$.