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 SWNE 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:

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:

Similarly, the Schröder numbers count the number of ways to divide a rectangle into n + 1 smaller rectangles using n cuts through n points given inside the rectangle in general position, each cut intersecting one of the points and dividing only a single rectangle in two. The following figure shows the 6 rectangulations into 3 rectangles using two cuts:

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

Schröder numbers also count separable permutations.

See also

References

This article is issued from Wikipedia - version of the 2/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.