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:
3 paths

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

3 x 3 grid, 63 paths:
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:
2 paths

3 x 3 grid, 4 paths:
4 paths

4 x 4 grid, 9 paths:
9 paths

5 x 5 grid, 21 paths:
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 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

Copyright © 1996/7 Robert M. Dickau