Delannoy and Motzkin Numbers

Back to Robert's Math Figures
_____________________________________

Delannoy Numbers
Delannoy numbers describe the number of paths from the southwest corner of a rectangular grid to the northeast corner, using only single steps north, northeast, or east. Delannoy numbers can be computed recursively using this formula:
D(a, b) = D(a - 1, b) + D(a, b - 1) + D(a - 1, b - 1) [Weisstein 1999],
where D(0, 0) = 1.
For a 1 x 1 grid, there are 3 paths:

For a 2 x 2 grid, there are 13 paths:

3 x 3 grid, 63 paths:

Motzkin Numbers
The Motzkin numbers describe the number of paths from the southwest corner of a grid to the southeast corner, using only steps northeast, east, and southeast.
2 x 2 grid, 2 paths:

3 x 3 grid, 4 paths:

4 x 4 grid, 9 paths:

5 x 5 grid, 21 paths:

Definitions and formulas cribbed from Eric Weisstein's CRC Concise Encyclopedia of Mathematics (CRC Press, 1999), pp. 411 and 1201. Figures designed and rendered using Mathematica 3.0.1.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help

The Math Forum is a research and educational enterprise of the Drexel University School of Education.