Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
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.
The Delannoy number also counts the number of global alignments of two sequences of lengths and , the number of points in an m-dimensional integer lattice or cross polytope which are at most n steps from the origin, and, in cellular automata, the number of cells in an m-dimensional von Neumann neighborhood of radius n while the number of cells on a surface of an m-dimensional von Neumann neighborhood of radius n is given with .
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.
The Delannoy array is an infinite matrix of the Delannoy numbers:
{| class="wikitable" style="text-align:right;"
|-
!
! 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.