Schröder number

The Schröder numbers are a sequence of natural numbers with a number of different meanings in combinatorics. They appear among others in the enumeration of certain lattice paths, polygon decompositions, trees or permutations. We distinguish large Schröder numbers and small Schröder numbers that differ only by a factor of two from each other substantially.

The Schröder numbers are named after the German mathematician Ernst Schröder, who examined the problem in 1870, how many ways brackets can be written in a sum. However, they should have been already known to the Greek astronomer Hipparchus of Nicaea.

• 2.1 parantheses
• 2.2 lattice paths
• 2.3 decompositions
• 2.4 permutations
• 2.5 Combinatorial equivalence

• 3.1 recurrences
• 3.2 Explicit formulas
• 3.3 Generating functions

Definitions

Large Schroeder numbers

The large Schröder numbers are for recursively and

For defined. They are the result

Little Schröder numbers

The small Schröder numbers are in accordance with and

For defined. They are the result

According to Plutarch, this number sequence should already have been to the Greek astronomer Hipparchus of Nicaea known, which is why they are also called Hipparchus - Schröder- Hipparchus numbers or numbers. They are closely related to the Catalan numbers, and are therefore also referred to as super - Catalan numbers.

Meanings

Parantheses

Ernst Schröder looked at the problem in 1870, how many ways it is possible to put parentheses in a sum consisting of terms. The brackets should thereby be correctly nested and each comprising at least two terms. For example, there are the following eleven such parantheses of four terms:

The number of possible in this way parantheses is given just by the little Schröder numbers. When parentheses around the whole sum around also permits obtained as the solution of the problem, the large Schröder numbers. In comparison, give the Catalan numbers, the number of possible parantheses carefully bracket pairs in which each comprise exactly two terms. This parantheses correspond to the second line in the example above.

Lattice paths

The large Schröder numbers indicate the number of possible paths in a square grid of edge length to under the following conditions:

• Each path is from the lower left corner to the upper right corner.
• A step must only be to the right, up or diagonally up to the right.
• The diagonal from bottom left to top right must not be exceeded.

Such paths are also Schröder paths, or paths king named because they correspond to the possible moves of the king in chess. The small Schröder numbers correspond to the number of those paths where no portion of proceeds on the diagonal.

Equivalently, the large Schröder numbers, the number of paths in a grid of size to satisfy the following conditions:

• Each path is from the lower left corner to the lower right corner.
• A step may only obliquely upward to the right, diagonally down to the right or as a double step to the right.
• The zero line must not be exceeded.

These paths are created by rotation, extension and reflection of the respective paths in the square grid. A double step corresponds to the square lattice a diagonal stride and the two oblique steps are there steps each to the right and upwards. The small Schröder numbers also characterize those paths which have no vertex in.

Decompositions

The large Schröder numbers also count the number of ways to divide a regular polygon with corners under the following conditions:

• Each section runs through two non-adjacent vertices.
• The cut lines are allowed at the corners touch but inside not cut it.
• A previously selected corner may not be the end point of a section.

Schröder small numbers corresponding to the number of possible partitions of a regular pentagon, wherein no vertex is omitted.

Equivalent to rank the large Schröder numbers and the number of ways to divide a square of side length with cuts in rectangles under the following conditions:

• Inside the square are located the points.
• Each section runs horizontally or vertically by exactly one of these points.
• Each section is divided only 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 internal nodes are labeled or.
• The leaves remain unmarked.
• The right subtree of each internal node has a different sign than the node itself

Each such binary tree corresponds to a separable permutation of length. Separable permutations are those permutations that can be represented by direct or oblique sums of trivial permutations. They are also those permutations that avoid the two Permutationsmuster and. The small Schröder numbers indicate the number of trees in which the root node is positive.

Combinatorial equivalence

All these constructions are combinatorially equivalent, ie, there is a bijective mapping between each mutually corresponding objects. Each polygon decomposition may be assigned to an ordered tree, which corresponds to the dual graph of the decomposition. The surfaces of the separation corresponding to the internal nodes of the tree and its leaves the sides of the polygon. A previously selected page is thereby assigned to the root of the tree.

Each polygon decomposition corresponds to a permissible bracketing a sum of terms. For this, the number of sides of the polygon are selected according to the individual terms, with a previously selected page again omitted. Each corner of the polygon corresponds to a point at which a brace can be set and each cut line accurately a pair of brackets.

All constructions listed by the large numbers Schröder, have a basic symmetry. Your objects fall into two disjoint classes, which are equally powerful and are enumerated in each case by the little Schröder numbers.

Properties

Recurrences

A linear second-order difference equation for the large Schröder numbers by

Given. Looking at the figures, the linear recurrence

Suffice to be said and on set, then there are the large Schröder numbers on the diagonal, ie

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

They arise for the sum

Explicit formulas

The large Schröder numbers have the explicit representations

Being a hypergeometric function,

Being and a Gegenbauer polynomial of degree, and

Said Legendre polynomial of degree.

Generating functions

The generating function of the large Schröder numbers is

Accordingly and the small Schröder numbers

The generating functions satisfy the identities

As well as