Delannoy number

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 Delannoy number D(m,n) also counts the number of global alignments of two sequences of lengths m and n,[2] the number of points in an m-dimensional integer lattice that are at most n steps from the origin,[3] and, in cellular automata, the number of cells in an m-dimensional von Neumann neighborhood of radius n.[4]

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:[5]

n \ m	0	1	2	3	4	5	6	7	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,[6] 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, ... (sequence A001850 in OEIS).

Computation
Delannoy numbers

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 relation 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

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

\( 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

Motzkin number
Narayana number

References

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
Covington, Michael A. (2004), "The number of distinct alignments of two strings", Journal of Quantitative Linguistics 11 (3): 173–182, doi:10.1080/0929617042000314921
Luther, Sebastian; Mertens, Stephan (2011), "Counting lattice animals in high dimensions", Journal of Statistical Mechanics: Theory and Experiment 2011 (9): P09026, arXiv:1106.1078
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
Sulanke, Robert A. (2003), "Objects counted by the central Delannoy numbers" (PDF), Journal of Integer Sequences 6 (1): Article 03.1.5, MR 1971435
"Sloane's A008288 : Square array of Delannoy numbers D(i,j) (i >= 0, j >= 0) read by antidiagonals", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

Peart, Paul; Woan, Wen-Jin (2002). "A bijective proof of the Delannoy recurrence". Congressus Numerantium 158: 29–33. ISSN 0384-9864. Zbl 1030.05003.

External links

Weisstein, Eric W., "Delannoy Number", MathWorld.

It is unknown whether there exists a prime number p such that Cp is also prime.

As of February 2012, the largest known generalized Cullen prime is 427194 × 113 427194 + 1. It has 877,069 digits and was discovered by a PrimeGrid participant from United States.[3]

150 = 2 × 3 × 52

Mathematics Encyclopedia