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.

$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{else}\end{cases}$

For an n × n grid, the first few Delannoy numbers (starting with n=0) are (sequence A001850 in OEIS):

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ...

The following figure illustrates the 63 Delannoy paths through a 3 × 3 grid:

The paths that do not rise above the SW–NE diagonal represent the Schröder numbers.

See also

• Motzkin number
• Narayana number
• Schröder number

References

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