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