# Delannoy number

In mathematics, a Delannoy number $D$ describes the number of 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 mathematician Henri Delannoy.[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, ... (sequence A001850 in OEIS).

The following figure illustrates the 63 Delannoy paths through a 3 × 3 grid:

The paths that do not rise above the SW–NE diagonal represent the Schröder numbers.

The Delannoy number $D(m,n)$ also counts the number of global alignments of two sequences of lengths $m$ and $n$.

## Computation

### Delannoy numbers

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

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

An alternative expression is given by

$D(m,n) = \sum_{k=0}^{\min(m,n)} \binom{m}{k} \binom{n}{k} 2^k .$

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

$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

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

### Central Delannoy numbers

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

$D(n) = \sum_{k=0}^n \binom{n}{k} \binom{n+k}{k} ,$

while the second expression above yields

$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,

$n D(n) = 3(2n-1)D(n-1) - (n-1)D(n-2) ,$

and have a generating function

$\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

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

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

## References

1. ^ Banderier, Cyril; Schwer, Sylviane (2005), "Why Delannoy numbers?", Journal of Statistical Planning and Inference 135 (1): 40–54, arXiv:math/0411128.
• Peart, Paul; Woan, Wen-Jin (2002). "A bijective proof of the Delannoy recurrence". Congressus Numerantium 158: 29–33. ISSN 0384-9864. Zbl 1030.05003.
• Rodriguez Villegas, Fernando (2007). Experimental number theory. Oxford Graduate Texts in Mathematics 13. Oxford University Press. p. 120. ISBN 978-0-19-922730-3. Zbl 1130.11002.