Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Schröder number
Summary
In mathematics, the Schröder number also called a large Schröder number or big Schröder number, describes the number of lattice paths from the southwest corner of an grid to the northeast corner 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, ... .
where and They were named after the German mathematician Ernst Schröder.
The following figure shows the 6 such paths through a grid:
A Schröder path of length is a lattice path from to with steps northeast, east, and southeast, that do not go below the -axis. The th Schröder number is the number of Schröder paths of length . The following figure shows the 6 Schröder paths of length 2.
Similarly, the Schröder numbers count the number of ways to divide a rectangle into smaller rectangles using cuts through points given inside the rectangle in general position, each cut intersecting one of the points and dividing only a single rectangle in two (i.e., the number of structurally-different guillotine partitions). This is similar to the process of triangulation, in which a shape is divided into nonoverlapping triangles instead of rectangles. The following figure shows the 6 such dissections of a rectangle into 3 rectangles using two cuts:
Pictured below are the 22 dissections of a rectangle into 4 rectangles using three cuts:
The Schröder number also counts the separable permutations of length
Schröder numbers are sometimes called large or big Schröder numbers because there is another Schröder sequence: the little Schröder numbers, also known as the Schröder-Hipparchus numbers or the super-Catalan numbers. The connections between these paths can be seen in a few ways:
Consider the paths from to with steps and that do not rise above the main diagonal. There are two types of paths: those that have movements along the main diagonal and those that do not. The (large) Schröder numbers count both types of paths, and the little Schröder numbers count only the paths that only touch the diagonal but have no movements along it.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.