Delannoy, Schröder, and Motzkin Numbers

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 × 1 grid, there are 3 paths (see also SVG version):

3 paths: NE; N,E; E,N

For a 2 × 2 grid, there are 13 paths (SVG version):

13 paths: NE,NE; N,NE,N; N,E,NE; NE,N,E; etc.

3 × 3 grid, 63 paths (SVG version):

63 paths: NE,NE,NE; N,NE,NE,E; N,NE,E,NE; etc.

Schröder Numbers

The Delannoy paths that do not rise above the SW–NE diagonal (the paths drawn above in green) represent the Schröder numbers.

Another interpretation of the Schröder numbers is the number of ways a rectangle containing n points—with no two points falling on a line parallel to the rectangle’s edges—can be sliced into smaller rectangles, where each slice intersects one of the points, is parallel to one of the rectangle’s edges, and divides only a single rectangle.

1 slice, 2 ways:

1 slices

2 slices, 6 ways:

2 slices

3 slices, 22 ways:

3 slices

4 slices, 90 ways:

4 slices

See also "Schröder Rectangulations" at the Wolfram Demonstrations Project.

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. (Clearly, for a grid with width n the maximum necessary height is Floor[n/2].)

2 × 2 grid, 2 paths (see also SVG version):

2 paths: NE,SE; E,E

3 × 3 grid, 4 paths (SVG version):

4 paths: NE,SE,E; NE,E,SE; E,NE,SE; E,E,E

4 × 4 grid, 9 paths (SVG version):

9 paths: NE,SE,NE,SE; NE,SE,E,E; etc.

5 × 5 grid, 21 paths (SVG version):

21 paths: NE,SE,NE,SE; NE,SE,E,E; etc.

Definitions and formulas cribbed from Eric Weisstein’s CRC Concise Encyclopedia of Mathematics (CRC Press, 1999), pp. 411 and 1201.

Figures originally designed and rendered using Mathematica; SVG created by hand with help from some Ruby scripts and NoteTab.

[ home ] || [ 080331 ]