Schröder Number
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, 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 (mathematics), set , is a sequence of Vector (mathematics and physics), vectors such that each consecutive difference v_i - v_ lies in . A l ...
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 (mathematics), set , is a sequence of Vector (mathematics and physics), vectors such that each consecutive difference v_i - v_ lies in . A l ...
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 geometry, Euclidean plane geometry, a rectangle is a Rectilinear polygon, rectilinear convex polygon or a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that a ...
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 partition Guillotine partition is the process of partitioning a rectilinear polygon, possibly containing some holes, into rectangles, using only guillotine-cuts. A guillotine-cut (also called an edge-to-edge cut) is a straight bisecting line going from one ...
s). 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 m ...
, 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 combinatorics, combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by Direct sum of permutations, direct sums and Skew sum of permutations, skew sums. Separable permutations may ...
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 The Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after Eugène Catalan, though they were previously discovered in the 1730s by Minggatu ...
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 ...
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 representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...
G(x) of the sequence (S_n)_ is :G(x) = \frac = \sum_^\infty S_n x^n. It can be expressed in terms of the generating function for
Catalan number The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...
s C(x) = \frac as :G(x) = \frac1 C\big(\frac\big).


Uses

One topic of
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
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 tiling In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by domino (mathematics), dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a matching (graph theory), ...
s; 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 combinatorics, 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 co ...
. 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 (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
of the (2n-1)\times(2n-1)
Hankel matrix In linear algebra, a Hankel matrix (or catalecticant matrix), named after Hermann Hankel, is a rectangular matrix in which each ascending skew-diagonal from left to right is constant. For example, \qquad\begin a & b & c & d & e \\ b & c & d & e & ...
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 counts the 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 after French army ...
*
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 ...
*
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 Combinatorial enumeration, counting problems. They are named ...
*
Narayana polynomials Narayana polynomials are a class of polynomials whose coefficients are the Narayana numbers. The Narayana numbers and Narayana polynomials are named after the Canadian mathematician T. V. Narayana (1930–1987). They appear in several combinatorial ...
* Schröder–Hipparchus number *
Catalan number The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...


References


Further reading

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