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 the 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". MathWorld.