Schröder numbers
The Schröder numbers are a sequence of natural numbers with a number of different meanings in combinatorics . They appear among other things when listing certain grid paths, polygon decompositions , trees or permutations . A distinction is made between large Schröder numbers and small Schröder numbers , which essentially only differ by a factor of two.
The Schröder numbers are named after the German mathematician Ernst Schröder , who in 1870 investigated the problem of how many ways brackets can be written in a sum . However, they are said to have already been known to the Greek astronomer Hipparchus of Nicaea .
Definitions
Big Schröder numbers
The large Schröder numbers are for recursive through and
for defined. They form the sequence
Small Schröder numbers
The small Schröder numbers are replaced by and
for defined. They form the sequence
According to Plutarch , this sequence of numbers is said to have already been known to the Greek astronomer Hipparchus of Nicaea , which is why they are also called Hipparchus numbers or Schröder-Hipparchus numbers . They are closely related to the Catalan Numbers and are therefore also known as Super Catalan Numbers .
Meanings
Brackets
In 1870 Ernst Schröder looked at the problem of how many ways it is possible to put brackets into a sum consisting of terms . The brackets should be nested correctly and each contain at least two terms. For example, there are the following eleven such brackets of four terms:
The number of brackets possible in this way is indicated by the small Schröder numbers. If you also allow brackets around the whole sum, you get the large Schröder numbers as a solution to the problem. In comparison, the Catalan numbers indicate the number of possible brackets using exactly pairs of brackets, each of which includes exactly two terms. These brackets correspond to the second line in the above example.
Grid paths
The large Schröder numbers also indicate the number of possible paths in a square grid of the edge length under the following conditions:
- Each path runs from the lower left corner to the upper right corner .
- A step may only be taken to the right , up or diagonally to the top right .
- The diagonal from bottom left to top right must not be exceeded.
Such paths are also called Schröder paths or king paths, as they correspond to the king's possibilities of moving in chess . The small Schröder numbers correspond to the number of those paths in which no section runs on the diagonal.
Equivalently, the large Schröder numbers indicate the number of paths in a grid of the size if the following conditions are met:
- Each path runs from the lower left corner to the lower right corner .
- A step may only be taken diagonally to the top right , diagonally to the right bottom or as a double step to the right .
- The zero line must not be undercut.
These paths are created by rotating, stretching and mirroring the respective paths in the square grid. A double step corresponds to a diagonal step in the square grid and the two inclined steps correspond to the steps to the right and up. The small Schröder numbers also characterize those paths that do not have a vertex at .
Decompositions
The large Schröder numbers also count the number of ways to decompose a regular polygon with corners under the following conditions:
- Each cut goes through two non-adjacent corners.
- The cutting lines may touch at the corners but not intersect inside.
- A previously selected corner must not be the end point of a section.
The small Schröder numbers correspond to the number of possible decompositions of a regular corner, in which no corner is left out.
Equivalent to this, the large Schröder numbers also count the number of possibilities of dividing a square of the side length with cuts into rectangles under the following conditions:
- The points are inside the square .
- Each cut runs horizontally or vertically through exactly one of these points.
- Each cut only divides a single rectangle.
Permutations
The large Schröder numbers also count the number of ordered binary trees with leaves that meet the following conditions:
- The inner nodes are marked with or .
- The leaves remain unmarked.
- The right subtree of each inner node has a different sign than the node itself.
A separable permutation of length corresponds to each such binary tree . Separable permutations are those permutations that can be represented by direct or skewed sums of trivial permutations . They are also the permutations that avoid the two permutation patterns and . The small Schröder numbers indicate the number of trees for which the root node is positive.
Combinatorial equivalence
All these constructions are combinatorially equivalent, that is, there is a bijective mapping between objects that correspond to one another. Each polygon decomposition can be assigned an ordered tree that corresponds to the dual graph of the decomposition. The faces of the decomposition correspond to the inner nodes of the tree and the sides of the polygon to its leaves. A previously selected page is assigned to the root of the tree.
Each polygon decomposition also corresponds to a permissible bracketing of a sum of terms. For this purpose, the sides of the polygon are assigned to the individual terms one after the other, whereby a previously selected side is again omitted. Each corner of the polygon then corresponds to a point at which a bracket can be set and each cutting line to exactly one pair of brackets.
All constructions that are enumerated by the large Schröder numbers have a basic symmetry . Your objects fall into two disjoint classes, which are equally powerful and are each listed by the small Schröder numbers.
properties
Recurrences
0 | 1 | 2 | 3 | 4th | 5 | total | |
0 | 1 | 1 | |||||
1 | 1 | 2 | 3 | ||||
2 | 1 | 4th | 6th | 11 | |||
3 | 1 | 6th | 16 | 22nd | 45 | ||
4th | 1 | 8th | 30th | 68 | 90 | 197 | |
5 | 1 | 10 | 48 | 146 | 304 | 394 | 903 |
A second order linear difference equation is through for the large Schröder numbers
given. Looking at the numbers , those of linear recurrence
suffice, where and for are set, then the large Schröder numbers result on the diagonal, i.e.
- .
The small Schröder numbers accordingly satisfy the linear difference equation
- .
They result for as a sum
- .
Explicit formulas
The large Schröder numbers have the explicit representations
- ,
where is the Gaussian hypergeometric function ,
- ,
where and is a Gegenbauer polynomial of degree , and
- ,
where the Legendre polynomial is of degree .
Generating functions
The generating function of the large Schröder numbers is
and corresponding to the small Schröder numbers
The generating functions fulfill the identities
such as
- .
See also
literature
- Ralph Grimaldi: Fibonacci and Catalan Numbers: An Introduction . John Wiley & Sons, 2012, ISBN 978-1-118-15976-7 , Chapter 34.
- Richard P. Stanley : Enumerative Combinatorics . tape 1 . Cambridge University Press, 2002, ISBN 0-521-66351-2 .
- Richard P. Stanley: Enumerative Combinatorics . tape 2 . Cambridge University Press, 2001, ISBN 0-521-78987-7 .
Web links
- Eric W. Weisstein : Schröder Number . In: MathWorld (English).
- Eric W. Weisstein : Super Catalan Number . In: MathWorld (English).
Individual evidence
- ^ RP Stanley: Enumerative Combinatorics . tape 1 . Cambridge University Press, 2002, pp. 51 .
- ^ RP Stanley: Hipparchus, Plutarch, Schröder, and Hough . In: American Mathematical Monthly . tape 104 , no. 4 , 1997, p. 344-350 .
- ↑ a b c d episode A001003 in OEIS
- ^ E. Schröder: Four combinatorial problems . In: Journal of Mathematics and Physics . tape 15 , 1870, p. 361-376 ( uni-goettingen.de ).
- ^ RP Stanley: Enumerative Combinatorics . tape 2 . Cambridge University Press, 2001, pp. 177 f .
- ↑ a b c d e episode A006318 in OEIS
- ^ R. Grimaldi: Fibonacci and Catalan Numbers: An Introduction . John Wiley & Sons, 2012, p. 34.4 .
- ↑ a b c L. Shapiro, R. Sulanke: Bijections for the Schröder numbers . In: Mathematics Magazine . tape 73 , no. 5 , 2000, pp. 369-376 .
- ^ RP Stanley: Catalan addendum to Enumerative Combinatorics . tape 2 , 2013 ( with.edu [PDF]).
- ^ L. Shapiro, AB Stephens: Bootstrap percolation, the Schröder numbers, and the N-kings problem . In: SIAM Journal on Discrete Mathematics . tape 4 , 1991, pp. 275-280 .
- ↑ D. Foata, D. Zeilberger: A classic proof of a recurrence for a very classical sequence . In: Journal of Combinatorial Theory . A 80, no. 2 , 1997, p. 380-384 .