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:

Delannoy3x3.svg

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

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]

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