Delannoy number
{{Short description|Number of paths between grid corners, allowing diagonal steps}}
{{ Infobox integer sequence
| named_after = Henri–Auguste Delannoy
| terms_number = infinity
| formula =
| OEIS = A008288
| OEIS_name = Square array of Delannoy
}}
In mathematics, a Delannoy number counts the 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.{{citation |last1=Banderier |first1=Cyril |last2=Schwer |first2=Sylviane |title=Why Delannoy numbers? |year=2005 |journal=Journal of Statistical Planning and Inference |volume=135 |issue=1 |pages=40–54 |arxiv=math/0411128 |doi=10.1016/j.jspi.2005.02.004|s2cid=16226115 |mr = 2202337}}
The Delannoy number also counts the global alignments of two sequences of lengths and ,{{citation |last=Covington |first=Michael A. |year=2004 |title=The number of distinct alignments of two strings |journal=Journal of Quantitative Linguistics |volume=11 |issue=3 |pages=173–182 |doi=10.1080/0929617042000314921|s2cid=40549706 }} the points in an m-dimensional integer lattice or cross polytope which are at most n steps from the origin,{{citation
| last1 = Luther | first1 = Sebastian
| last2 = Mertens | first2 = Stephan
| arxiv = 1106.1078
| issue = 9
| journal = Journal of Statistical Mechanics: Theory and Experiment
| page = P09026
| title = Counting lattice animals in high dimensions
| url = http://stacks.iop.org/1742-5468/2011/i=09/a=P09026
| volume = 2011
| year = 2011| bibcode = 2011JSMTE..09..026L
| doi = 10.1088/1742-5468/2011/09/P09026
| s2cid = 119308823
}} and, in cellular automata, the cells in an m-dimensional von Neumann neighborhood of radius n.{{citation
| last1 = Breukelaar | first1 = R.
| last2 = Bäck | first2 = Th.
| contribution = Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior
| doi = 10.1145/1068009.1068024
| isbn = 1-59593-010-8
| location = New York, NY, USA
| pages = 107–114
| publisher = ACM
| title = Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05)
| year = 2005| s2cid = 207157009
}}
Example
The Delannoy number D(3, 3) equals 63. The following figure illustrates the 63 Delannoy paths from (0, 0) to (3, 3):
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:{{citation
| last = Sulanke | first = Robert A.
| title = Objects counted by the central Delannoy numbers
| year = 2003
| journal = Journal of Integer Sequences
| volume = 6
| issue = 1
| page = Article 03.1.5
| bibcode = 2003JIntS...6...15S
| mr = 1971435
| url = http://www.emis.de/journals/JIS/VOL6/Sulanke/delannoy.pdf}}
:
class="wikitable" style="text-align:right;" |
{{diagonal split header|n | m}}
! width="50" | 0 ! width="50" | 1 ! width="50" | 2 ! width="50" | 3 ! width="50" | 4 ! width="50" | 5 ! width="50" | 6 ! width="50" | 7 ! width="50" | 8 |
---|
0
| 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 |
1
| 1 || 3 || 5 || 7 || 9 || 11 || 13 || 15 || 17 |
2
| 1 || 5 || 13 || 25 || 41 || 61 || 85 || 113 || 145 |
3
| 1 || 7 || 25 || 63 || 129 || 231 || 377 || 575 || 833 |
4
| 1 || 9 || 41 || 129 || 321 || 681 || 1289 || 2241 || 3649 |
5
| 1 || 11 || 61 || 231 || 681 || 1683 || 3653 || 7183 || 13073 |
6
| 1 || 13 || 85 || 377 || 1289 || 3653 || 8989 || 19825 || 40081 |
7
| 1 || 15 || 113 || 575 || 2241 || 7183 || 19825 || 48639 || 108545 |
8
| 1 || 17 || 145 || 833 || 3649 || 13073 || 40081 || 108545 || 265729 |
9
| 1 || 19 || 181 || 1159 || 5641 || 22363 || 75517 || 224143 || 598417 |
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,{{Cite OEIS|A008288|name=Square array of Delannoy numbers D(i,j) (i >= 0, j >= 0) read by antidiagonals}} 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 1
1 11 41 63 41 11 1
Central 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, ... {{OEIS|id=A001850}}.
Computation
=Delannoy numbers=
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
:
or by the infinite series
:
And also
:
where is given with {{OEIS|id=A266213}}.
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 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,{{cite journal |last1=Peart |first1=Paul |last2=Woan |first2=Wen-Jin |title=A bijective proof of the Delannoy recurrence |year=2002 |journal=Congressus Numerantium |volume=158 |pages=29–33 |issn=0384-9864 |zbl=1030.05003 |mr = 1985142}}
:
and have a generating function
:
The leading asymptotic behavior of the central Delannoy numbers is given by
:
where
and
.
See also
References
{{reflist}}
External links
- {{MathWorld|title=Delannoy Number|urlname=DelannoyNumber}}
{{Classes of natural numbers}}