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.

also counts the global alignments of two sequences of lengths

,[2] the 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 cells in an m-dimensional von Neumann neighborhood of radius n.[4] 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.

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 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: For

diagonal (i.e. northeast) steps, there must be

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

The basic recurrence relation for the Delannoy numbers is easily seen to be This recurrence relation also leads directly to the generating function 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