Delannoy number

Summary

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]

Delannoy number
Named afterHenri–Auguste Delannoy
No. of known termsinfinity
Formula
OEIS index

The Delannoy number also counts the number of global alignments of two sequences of lengths and ,[2] the number of points in an m-dimensional integer lattice or cross polytope which 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] while the number of cells on a surface of an m-dimensional von Neumann neighborhood of radius n is given with (sequence A266213 in the OEIS).

Example edit

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 edit

The Delannoy array is an infinite matrix of the Delannoy numbers:[5]

 m
n 
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 edit

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).

Computation edit

Delannoy numbers edit

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).

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 edit

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

 

and have a generating function

 

The leading asymptotic behavior of the central Delannoy numbers is given by

 

where   and  .

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, MR 2202337, S2CID 16226115
  2. ^ 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
  3. ^ 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
  4. ^ 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
  5. ^ 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
  6. ^ Sloane, N. J. A. (ed.). "Sequence 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.
  7. ^ Peart, Paul; Woan, Wen-Jin (2002). "A bijective proof of the Delannoy recurrence". Congressus Numerantium. 158: 29–33. ISSN 0384-9864. MR 1985142. Zbl 1030.05003.

External links edit