Delannoy number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.


Delannoy numbers[edit]

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[edit]

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 .

See also[edit]


  1. ^ Banderier, Cyril; Schwer, Sylviane (2005), "Why Delannoy numbers?", Journal of Statistical Planning and Inference 135 (1): 40–54, arXiv:math/0411128, doi:10.1016/j.jspi.2005.02.004 .
  • 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. 

External links[edit]