HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Schröder number S_n, also called a ''large Schröder number'' or ''big Schröder number'', describes the number of
lattice path In combinatorics, a lattice path in the -dimensional integer lattice of length with steps in the set , is a sequence of vectors such that each consecutive difference v_i - v_ lies in . A lattice path may lie in any lattice in , but the int ...
s from the southwest corner (0,0) of an n \times n grid to the northeast corner (n,n), using only single steps north, (0,1); northeast, (1,1); or east, (1,0), 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 S_0=1 and S_1=2. They were named after the German mathematician Ernst Schröder.


Examples

The following figure shows the 6 such paths through a 2 \times 2 grid:


Related constructions

A Schröder path of length n is a
lattice path In combinatorics, a lattice path in the -dimensional integer lattice of length with steps in the set , is a sequence of vectors such that each consecutive difference v_i - v_ lies in . A lattice path may lie in any lattice in , but the int ...
from (0,0) to (2n,0) with steps northeast, (1,1); east, (2,0); and southeast, (1,-1), that do not go below the x-axis. The nth Schröder number is the number of Schröder paths of length n. 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 In Euclidean plane geometry, a rectangle is a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that all of its angles are equal (360°/4 = 90°); or a parallelogram containi ...
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 (i.e., the number of structurally-different guillotine partitions). This is similar to the process of
triangulation In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points. Applications In surveying Specifically in surveying, triangulation involves only angle me ...
, 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 S_n also counts the
separable permutation In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3 ...
s of length n-1.


Related sequences

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 (0,0) to (n,n) with steps (1,1), (2,0), and (1,-1) 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. * Just as there are (large) Schröder paths, a little Schröder path is a Schröder path that has no horizontal steps on the x-axis. * If S_n is the nth Schröder number and s_n is the nth little Schröder number, then S_n = 2s_n for n>0 (S_0 = s_0 = 1). Schröder paths are similar to
Dyck path In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...
s but allow the horizontal step instead of just diagonal steps. Another similar path is the type of path that the
Motzkin number In mathematics, the th Motzkin number is the number of different ways of drawing non-intersecting chords between points on a circle (not necessarily touching every point by a chord). The Motzkin numbers are named after Theodore Motzkin and have d ...
s count; the Motzkin paths allow the same diagonal paths but allow only a single horizontal step, (1,0), and count such paths from (0,0) to (n,0). There is also a
triangular array In mathematics and computing, a triangular array of numbers, polynomials, or the like, is a doubly indexed sequence in which each row is only as long as the row's own index. That is, the ''i''th row contains only ''i'' elements. Examples Notable ...
associated with the Schröder numbers that provides a
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
(though not just with the Schröder numbers). The first few terms are :1, 1, 2, 1, 4, 6, 1, 6, 16, 22, .... . It is easier to see the connection with the Schröder numbers when the sequence is in its triangular form: Then the Schröder numbers are the diagonal entries, i.e. S_n = T(n,n) where T(n,k) is the entry in row n and column k. The recurrence relation given by this arrangement is : T(n,k) = T(n,k-1) + T(n-1,k-1) + T(n-1,k) with T(1,k)=1 and T(n,k)=0 for k>n. Another interesting observation to make is that the sum of the nth row is the (n+1)st little Schröder number; that is, :\sum_^n T(n,k) = s_.


Recurrence relations

With S_0 = 1, S_1 = 2, :S_ = 3S_ + \sum_^S_ S_ for n \geq 2 and also :S_ =\fracS_ - \fracS_ for n \geq 2


Generating function

The
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
G(x) of (S_n) is :G(x) = \frac = \sum_^\infty S_n x^n.


Uses

One topic of
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
is
tiling Tiling may refer to: *The physical act of laying tiles *Tessellations Computing *The compiler optimization of loop tiling *Tiled rendering, the process of subdividing an image by regular grid *Tiling window manager People *Heinrich Sylvester The ...
shapes, and one particular instance of this is domino tilings; the question in this instance is, "How many dominoes (that is, 1 \times 2 or 2 \times 1 rectangles) can we arrange on some shape such that none of the dominoes overlap, the entire shape is covered, and none of the dominoes stick out of the shape?" The shape that the Schröder numbers have a connection with is the
Aztec diamond In combinatorial mathematics, an Aztec diamond of order ''n'' consists of all squares of a square lattice whose centers (''x'',''y'') satisfy , ''x'', + , ''y'', ≤ ''n''. Here ''n'' is a fixed integer, and the square lattice consists of unit s ...
. Shown below for reference is an Aztec diamond of order 4 with a possible domino tiling. It turns out that the
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
of the (2n-1)\times(2n-1)
Hankel matrix In linear algebra, a Hankel matrix (or catalecticant matrix), named after Hermann Hankel, is a square matrix in which each ascending skew-diagonal from left to right is constant, e.g.: \qquad\begin a & b & c & d & e \\ b & c & d & e & f \\ c & d & ...
of the Schröder numbers, that is, the square matrix whose (i,j)th entry is S_, is the number of domino tilings of the order n Aztec diamond, which is 2^. That is, : \begin S_1 & S_2 & \cdots & S_n \\ S_2 & S_3 & \cdots & S_ \\ \vdots & \vdots & \ddots & \vdots \\ S_n & S_ & \cdots & S_ \end = 2^. For example: :* \begin 2 \end = 2 = 2^ :* \begin 2 & 6 \\ 6 & 22 \end = 8 = 2^ :* \begin 2 & 6 & 22 \\ 6 & 22 & 90 \\ 22 & 90 & 394 \end = 64 = 2^


See also

*
Delannoy number In mathematics, a Delannoy number D describes the number of paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (''m'', ''n''), using only single steps north, northeast, or east. The Delannoy numbers are named aft ...
*
Motzkin number In mathematics, the th Motzkin number is the number of different ways of drawing non-intersecting chords between points on a circle (not necessarily touching every point by a chord). The Motzkin numbers are named after Theodore Motzkin and have d ...
*
Narayana number In combinatorics, the Narayana numbers \operatorname(n, k), n \in \mathbb^+, 1 \le k \le n form a triangular array of natural numbers, called the Narayana triangle, that occur in various counting problems. They are named after Canadian mathemati ...
*
Schröder–Hipparchus number In combinatorics, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of di ...
*
Catalan number In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...


References


Further reading

* * Stanley, Richard P.
Catalan addendum
to ''Enumerative Combinatorics, Volume 2'' {{DEFAULTSORT:Schroder number Integer sequences Enumerative combinatorics