![]() | ||
In mathematics, a Delannoy number
Contents
The Delannoy number
Example
The Delannoy number D(3,3) equals 63. The following figure illustrates the 63 Delannoy paths through a 3 × 3 grid:
The subset of paths that do not rise above the SW–NE diagonal are counted by a related family of numbers, the Schröder numbers.
Delannoy array
The Delannoy array is an infinite matrix of the Delannoy numbers:
In this array, the numbers in the first row are all one, the numbers in the second row are the odd numbers, the numbers in the third row are the centered square numbers, and the numbers in the fourth row are the centered octahedral numbers. Alternatively, the same numbers can be arranged in a triangular array resembling Pascal's triangle, also called the tribonacci triangle, in which each number is the sum of the three numbers above it:
1 1 1 1 3 1 1 5 5 1 1 7 13 7 1 1 9 25 25 9 11 11 41 63 41 11 1Central Delannoy numbers
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).Delannoy numbers
For
An alternative expression is given by
And also
where
The basic recurrence relation for the Delannoy numbers is easily seen to be
This recurrence relation also leads directly to the generating function
Central Delannoy numbers
Substituting
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