Schröder number

In mathematics, a Schröder number describes the number of paths from the southwest corner (0, 0) of an n × n grid to the northeast corner (n, n), using only single steps north, northeast, or east, that do not rise above the SW–NE diagonal.

The first few Schröder numbers are

1, 2, 6, 22, 90, 394, 1806, 8558, .... (sequence A006318 in the OEIS).

They were named after the German mathematician Ernst Schröder.

Examples

The following figure shows the 6 Schröder paths through a 2 × 2 grid:

File:SchroederNumber2x2.svg

Related constructions

Schröder numbers count the number of paths from (0, 0) to (2n, 0), using only single steps northeast or southeast (steps (1, 1) or (1, –1)) or double steps east (steps (2, 0)), that never fall below the x-axis:

File:SchroederWalks2.svg

Similarly, the Schröder numbers count the number of ways to divide a rectangle into n + 1 smaller rectangles using n cuts; with the restriction that there are n points inside the rectangle, no two of these points falling on the same line parallel to either the x-axis or y-axis, and each cut intersects one of the points and divides only a single rectangle in two. The following figure shows the 6 rectangulations into 3 rectangles using two cuts:

File:SchroederRectangulation3.svg

And here are the 22 rectangulations into 4 rectangles using three cuts:

File:SchroederRectangulation4.svg

Schröder numbers also count separable permutations.

See also

• Delannoy number
• Motzkin number
• Narayana number
• Schröder–Hipparchus number

References

• Weisstein, Eric W. "Schröder Number". MathWorld.

External links

• Stanley, Richard P.: Catalan addendum to Enumerative Combinatorics, Volume 2