In mathematics, a Delannoy number 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.
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:
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 also counts the number of global alignments of two sequences of lengths and .
For diagonal (i.e. northeast) steps, there must be steps in the direction and steps in the direction in order to reach the point ; as these steps can be performed in any order, the number of such paths is given by the multinomial coefficient . Hence, one gets the closed-form expression
An alternative expression is given by
The basic recurrence relationship for the Delannoy numbers is easily seen to be
This recurrence relation also leads directly to the generating function
Central Delannoy numbers
Substituting in the first closed form expression above, replacing , and a little algebra, gives
while the second expression above yields
The central Delannoy numbers satisfy also a three-term recurrence relationship among themselves,
and have a generating function
The leading asymptotic behavior of the central Delannoy numbers is given by
where and .
- 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.