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.[1]
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,[6] in which each number is the sum of the three numbers above it:
The central Delannoy numbersD(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).
Computationedit
Delannoy numbersedit
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 (sequence A266213 in the OEIS).
^Covington, Michael A. (2004), "The number of distinct alignments of two strings", Journal of Quantitative Linguistics, 11 (3): 173–182, doi:10.1080/0929617042000314921, S2CID 40549706
^Luther, Sebastian; Mertens, Stephan (2011), "Counting lattice animals in high dimensions", Journal of Statistical Mechanics: Theory and Experiment, 2011 (9): P09026, arXiv:1106.1078, Bibcode:2011JSMTE..09..026L, doi:10.1088/1742-5468/2011/09/P09026, S2CID 119308823
^Breukelaar, R.; Bäck, Th. (2005), "Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior", Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05), New York, NY, USA: ACM, pp. 107–114, doi:10.1145/1068009.1068024, ISBN 1-59593-010-8, S2CID 207157009
^Sulanke, Robert A. (2003), "Objects counted by the central Delannoy numbers" (PDF), Journal of Integer Sequences, 6 (1): Article 03.1.5, Bibcode:2003JIntS...6...15S, MR 1971435