Schröder numbers

The large Schröder numbers indicate the number of horizontal, vertical or diagonal paths in a square grid that run from the lower left corner to the upper right corner and do not exceed the diagonal

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 ${\displaystyle S_{n}}$ ${\displaystyle n\in \mathbb {N} _{0}}$ ${\displaystyle S_{0}=1}$

${\displaystyle S_{n}=S_{n-1}+\sum _{k=0}^{n-1}S_{k}\cdot S_{n-k-1}}$

for defined. They form the sequence ${\displaystyle n\geq 1}$

${\displaystyle 1,2,6,22,90,394,1806,8558,\ldots }$   (Follow A006318 in OEIS ).

Small Schröder numbers

The small Schröder numbers are replaced by and ${\displaystyle s_{n}}$ ${\displaystyle s_{0}=1}$

${\displaystyle s_{n}={\frac {S_{n}}{2}}=-s_{n-1}+2\,\sum _{k=0}^{n-1}s_{k}\cdot s_{n-k-1}}$

for defined. They form the sequence ${\displaystyle n\geq 1}$

${\displaystyle 1,1,3,11,45,197,903,4279,\ldots }$   (Follow A001003 in OEIS ).

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: ${\displaystyle n+1}$

${\displaystyle {\begin{array}{llllll}a+b+c+d\quad &(a+b)+c+d\quad &a+(b+c)+d\quad &a+b+(c+d)\quad &(a+b+c)+d\quad &a+(b+c+d)\\(a+b)+(c+d)\quad &((a+b)+c)+d\quad &(a+(b+c))+d\quad &a+((b+c)+d)\quad &a+(b+(c+d))\end{array}}}$

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. ${\displaystyle n-1}$

Grid paths

The six possible paths in a (2 × 2) grid

The large Schröder numbers also indicate the number of possible paths in a square grid of the edge length under the following conditions: ${\displaystyle n}$

• Each path runs from the lower left corner to the upper right corner . ${\displaystyle (0,0)}$ ${\displaystyle (n,n)}$
• A step may only be taken to the right , up or diagonally to the top right . ${\displaystyle (+1,0)}$ ${\displaystyle (0,+1)}$ ${\displaystyle (+1,+1)}$
• 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.

The corresponding six paths in a (4 × 2) grid

Equivalently, the large Schröder numbers indicate the number of paths in a grid of the size if the following conditions are met: ${\displaystyle 2n\times n}$

• Each path runs from the lower left corner to the lower right corner . ${\displaystyle (0,0)}$ ${\displaystyle (2n,0)}$
• A step may only be taken diagonally to the top right , diagonally to the right bottom or as a double step to the right . ${\displaystyle (+1,+1)}$ ${\displaystyle (+1,-1)}$ ${\displaystyle (2,0)}$
• 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 . ${\displaystyle y=1}$

Decompositions

The six possible subdivisions of a regular pentagon

The large Schröder numbers also count the number of ways to decompose a regular polygon with corners under the following conditions: ${\displaystyle n+3}$

• 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. ${\displaystyle (n+2)}$

The six possible decomposition of a square into rectangles with two cuts

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: ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle n+1}$

• The points are inside the square . ${\displaystyle n}$ ${\displaystyle (1,1),\ldots ,(n,n)}$
• Each cut runs horizontally or vertically through exactly one of these points.
• Each cut only divides a single rectangle.

Permutations

The six possible binary trees marked with + and - with three leaves

The large Schröder numbers also count the number of ordered binary trees with leaves that meet the following conditions: ${\displaystyle n+1}$

• The inner nodes are marked with or . ${\displaystyle +}$ ${\displaystyle -}$
• 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. ${\displaystyle n+1}$ ${\displaystyle (2,4,1,3)}$ ${\displaystyle (3,1,4,2)}$

Combinatorial equivalence

For the equivalence of decompositions, trees and brackets

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

Triangle of numbers S _{n, k}

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	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

${\displaystyle (n+1)S_{n}=(6n-3)S_{n-1}-(n-2)S_{n-2}}$

given. Looking at the numbers , those of linear recurrence ${\displaystyle S_{n,k}}$

${\displaystyle S_{n,k}=S_{n,k-1}+S_{n-1,k}+S_{n-1,k-1}}$   (Follow A033877 in OEIS )

suffice, where and for are set, then the large Schröder numbers result on the diagonal, i.e. ${\displaystyle S_{n,0}=1}$ ${\displaystyle S_{n,k}=0}$ ${\displaystyle k>n}$

${\displaystyle S_{n}=S_{n,n}}$.

The small Schröder numbers accordingly satisfy the linear difference equation

${\displaystyle ns_{n}=(6n-9)s_{n-1}-(n-3)s_{n-2}}$.

They result for as a sum ${\displaystyle n>0}$

${\displaystyle s_{n}=\sum _{k=1}^{n-1}S_{n-1,k}}$.

Explicit formulas

The large Schröder numbers have the explicit representations

${\displaystyle S_{n}=2\,_{2}F_{1}(-n+1,n+2;2;-1)}$,

where is the Gaussian hypergeometric function , ${\displaystyle _{2}F_{1}}$

${\displaystyle S_{n}=-{\frac {1}{2}}\,C_{n+1}^{(-1/2)}(3)}$,

where and is a Gegenbauer polynomial of degree , and ${\displaystyle n>1}$ ${\displaystyle C_{n}^{(k)}}$ ${\displaystyle n}$

${\displaystyle S_{n}={\frac {1}{2}}\left(-P_{n-1}(3)+6P_{n}(3)-P_{n+1}(3)\right)}$,

where the Legendre polynomial is of degree . ${\displaystyle P_{n}}$ ${\displaystyle n}$

Generating functions

The generating function of the large Schröder numbers is

${\displaystyle G(x)=\sum _{n=0}^{\infty }S_{n}x^{n}={\frac {1-x-{\sqrt {1-6x+x^{2}}}}{2x}}}$

and corresponding to the small Schröder numbers

${\displaystyle g(x)=\sum _{n=0}^{\infty }s_{n}x^{n}={\frac {1+x-{\sqrt {1-6x+x^{2}}}}{4x}}}$

The generating functions fulfill the identities

${\displaystyle (1-x)G(x)-xG(x)^{2}=1}$

such as

${\displaystyle (1+x)g(x)-2g(x)^{2}=x}$.

See also

• Motzkin number

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

1. ^ RP Stanley: Enumerative Combinatorics . tape 1 . Cambridge University Press, 2002, pp. 51 .
2. ^ RP Stanley: Hipparchus, Plutarch, Schröder, and Hough . In: American Mathematical Monthly . tape 104 , no. 4 , 1997, p. 344-350 .
3. ↑ ^{a b c d} episode A001003 in OEIS
4. ^ E. Schröder: Four combinatorial problems . In: Journal of Mathematics and Physics . tape 15 , 1870, p. 361-376 ( uni-goettingen.de ).
5. ^ RP Stanley: Enumerative Combinatorics . tape 2 . Cambridge University Press, 2001, pp. 177 f .
6. ↑ ^{a b c d e} episode A006318 in OEIS
7. ^ R. Grimaldi: Fibonacci and Catalan Numbers: An Introduction . John Wiley & Sons, 2012, p. 34.4 .
8. ↑ ^{a b c} L. Shapiro, R. Sulanke: Bijections for the Schröder numbers . In: Mathematics Magazine . tape 73 , no. 5 , 2000, pp. 369-376 .
9. ^ RP Stanley: Catalan addendum to Enumerative Combinatorics . tape 2 , 2013 ( with.edu [PDF]).
10. ^ 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 .
11. ↑ 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 .