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.

$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{else}}\end{cases}}$

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 the OEIS).

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

The central Delannoy numbers for a square grid satisfy a three-term recurrence relationship

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

a generating function

$\sum D(n)x^{n}=(1-6x+x^{2})^{-1/2}$

and a closed form

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

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

See also

• Motzkin number
• Narayana number

References

• 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. Vol. 13. Oxford University Press. p. 120. ISBN 978-0-19-922730-3. Zbl 1130.11002.

External links

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