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.