View source for Schröder number

{{Short description|Mathematical integer sequence}}
{{more footnotes|date=January 2016}}
{{Infobox integer sequence
| named_after = Ernst Schröder
| terms_number = [[infinity]]
| first_terms = [[1]], [[2]], [[6]], [[22 (number)|22]], [[90 (number)|90]], [[394 (number)|394]], [[1806 (number)|1806]]
| OEIS = A006318
| OEIS_name = Large Schröder
}}
In [[mathematics]], the '''Schröder number''' <math>S_n,</math> also called a ''large Schröder number'' or ''big Schröder number'', describes the number of [[lattice path]]s from the southwest corner <math>(0,0)</math> of an <math>n \times n</math> grid to the northeast corner <math>(n,n),</math> using only single steps north, <math>(0,1);</math> northeast, <math>(1,1);</math> or east, <math>(1,0),</math> that do not rise above the SW&ndash;NE diagonal.<ref name="A006318" />

The first few Schröder numbers are

:1, 2, 6, 22, 90, 394, 1806, 8558, ... {{OEIS|id=A006318}}.

where <math>S_0=1</math> and <math>S_1=2.</math> They were named after the German mathematician [[Ernst Schröder (mathematician)|Ernst Schröder]].

==Examples==
The following figure shows the 6 such paths through a <math>2 \times 2</math> grid:

[[File:Schroeder number 2x2.svg]]

==Related constructions==
A Schröder path of length <math>n</math> is a [[lattice path]] from <math>(0,0)</math> to <math>(2n,0)</math> with steps northeast, <math>(1,1);</math> east, <math>(2,0);</math> and southeast, <math>(1,-1),</math> that do not go below the <math>x</math>-axis. The <math>n</math>th Schröder number is the number of Schröder paths of length <math>n</math>.<ref name="Ardila methods" /> The following figure shows the 6 Schröder paths of length 2.

[[File:Schroeder paths.svg]]

Similarly, the Schröder numbers count the number of ways to divide a [[rectangle]] into <math>n+1</math> smaller rectangles using <math>n</math> cuts through <math>n</math> 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]]s). This is similar to the process of [[triangulation]], 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:

[[File:Schroeder rectangulation 3.svg]]

Pictured below are the 22 dissections of a rectangle into 4 rectangles using three cuts:

[[File:Schroeder rectangulation 4.svg]]

The Schröder number <math>S_n</math> also counts the [[separable permutation]]s of length <math>n-1.</math>

==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 number]]s or the ''super-Catalan numbers''. The connections between these paths can be seen in a few ways:

* Consider the paths from <math>(0,0)</math> to <math>(n,n)</math> with steps <math>(1,1),</math> <math>(2,0),</math> and <math>(1,-1)</math> 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.<ref name="A001003" />
* 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 <math>x</math>-axis.<ref name="Bijections with Dyck paths" />
* If <math>S_n</math> is the <math>n</math>th Schröder number and <math>s_n</math> is the <math>n</math>th little Schröder number, then <math>S_n = 2s_n</math> for <math>n>0</math> <math>(S_0 = s_0 = 1).</math><ref name="Bijections with Dyck paths" />

Schröder paths are similar to [[Dyck path]]s but allow the horizontal step instead of just diagonal steps. Another similar path is the type of path that the [[Motzkin number]]s count; the Motzkin paths allow the same diagonal paths but allow only a single horizontal step, (1,0), and count such paths from <math>(0,0)</math> to <math>(n,0)</math>.<ref name="Catalan, Motzkin, and Schröder numbers" />

There is also a [[triangular array]] associated with the Schröder numbers that provides a [[recurrence relation]]<ref name="A033877" /> (though not just with the Schröder numbers). The first few terms are

:1, 1, 2, 1, 4, 6, 1, 6, 16, 22, .... {{OEIS|id=A033877}}.

It is easier to see the connection with the Schröder numbers when the sequence is in its triangular form:

{| class="wikitable" style="text-align:right;"
|-
! {{diagonal split header|{{mvar|n}}|{{mvar|k}}}}
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
|-
! 0
|  1  ||  ||  ||  ||  ||  || 
|-
! 1
|  1  ||  2  ||   ||   ||   ||   ||  
|-
! 2
|  1  || 4 || 6 ||   ||   ||   ||  
|-
! 3
|  1  || 6 || 16 || 22 ||   ||   ||  
|-
! 4
|  1  || 8 || 30 || 68 || 90 ||   ||  
|-
! 5
| 1 || 10 || 48 || 146 || 304 || 394 ||  
|-
! 6
| 1 || 12 || 70 || 264 || 714 || 1412 || 1806
|}

Then the Schröder numbers are the diagonal entries, i.e. <math>S_n = T(n,n)</math> where <math>T(n,k)</math> is the entry in row <math>n</math> and column <math>k</math>. The recurrence relation given by this arrangement is
: <math>T(n,k) = T(n,k-1) + T(n-1,k-1) + T(n-1,k) </math> 
with <math>T(1,k)=1</math> and <math>T(n,k)=0</math> for <math>k>n</math>.<ref name="A033877" /> Another interesting observation to make is that the sum of the <math>n</math>th row is the <math>(n+1)</math>st [[Schröder-Hipparchus number|little Schröder number]]; that is,
:<math>\sum_{k=0}^n T(n,k) = s_{n+1}</math>.

==Recurrence relations==

With <math>S_0 = 1</math>, <math>S_1 = 2</math>, <ref name="Schröder number formulas" />
:<math>S_{n} = 3S_{n-1} + \sum_{k=1}^{n-2}S_{k} S_{n-k-1} </math> for <math>n \geq 2</math> 
and also <ref name="IMC2019Prob4" />
:<math>S_{n} =\frac{6n-3}{n+1}S_{n-1} - \frac{n-2}{n+1}S_{n-2} </math> for <math>n \geq 2</math>

==Generating function==
The [[generating function]] <math>G(x)</math> of the sequence <math>(S_n)_{n\geq0}</math> is
:<math>G(x) = \frac{1 - x - \sqrt{1 - 6x + x^2}}{2x} = \sum_{n=0}^\infty S_n x^n</math>.<ref name="Schröder number formulas" />
It can be expressed in terms of the generating function for [[Catalan number]]s <math>C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}</math> as
:<math>G(x) = \frac1{1-x} C\big(\frac{x}{(1-x)^2}\big).</math>

==Uses==
One topic of [[combinatorics]] is [[Tessellation|tiling]] shapes, and one particular instance of this is [[domino tiling]]s; the question in this instance is, "How many dominoes (that is, <math>1 \times 2 </math> or <math>2 \times 1 </math> 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]]. Shown below for reference is an Aztec diamond of order 4 with a possible domino tiling.

[[File:Diamant azteque plein.svg]]

It turns out that the [[determinant]] of the <math>(2n-1)\times(2n-1)</math> [[Hankel matrix]] of the Schröder numbers, that is, the square matrix whose <math>(i,j)</math>th entry is <math>S_{i+j-1},</math> is the number of domino tilings of the order <math>n</math> Aztec diamond, which is <math>2^{n(n+1)/2}.</math><ref name="Eu Fu" /> That is,

:<math>
\begin{vmatrix}
S_1 & S_2 & \cdots & S_n \\
S_2 & S_3 & \cdots & S_{n+1} \\
\vdots & \vdots & \ddots & \vdots \\
S_n & S_{n+1} & \cdots & S_{2n-1}
\end{vmatrix}
= 2^{n(n+1)/2}.
</math>

For example:
:*<math>
\begin{vmatrix}
2
\end{vmatrix}
= 2 = 2^{1(2)/2}
</math>

:*<math>
\begin{vmatrix}
2 & 6 \\
6 & 22
\end{vmatrix}
= 8 = 2^{2(3)/2}
</math>

:*<math>
\begin{vmatrix}
2 & 6 & 22 \\
6 & 22 & 90 \\
22 & 90 & 394
\end{vmatrix}
= 64 = 2^{3(4)/2}
</math>

==See also==
*[[Delannoy number]]
*[[Motzkin number]]
*[[Narayana number]]
*[[Narayana polynomials]]
*[[Schröder–Hipparchus number]]
*[[Catalan number]]

== References ==
{{Reflist|refs=
<ref name="A006318">{{cite OEIS|1=A006318|2=Large Schröder numbers (or large Schroeder numbers, or big Schroeder numbers). |access-date=5 March 2018}}</ref>

<ref name="Ardila methods">{{cite book|last1=Ardila|first1=Federico|title=Handbook of enumerative combinatorics|date=2015|publisher=CRC Press|location=Boca Raton, FL|pages=3–172|chapter=Algebraic and geometric methods in enumerative combinatorics}}</ref>

<ref name="A001003">{{cite OEIS|1=A001003|2=Schroeder's second problem (generalized parentheses); also called super-Catalan numbers or little Schroeder numbers|access-date=5 March 2018}}</ref>

<ref name = "Bijections with Dyck paths">{{cite arXiv |last=Drake |first=Dan |year=2010 |title=Bijections from weighted Dyck paths to Schröder paths |class=math.CO |eprint=1006.1959}}</ref>

<ref name="Catalan, Motzkin, and Schröder numbers">{{cite journal|last1=Deng|first1=Eva Y. P.|last2=Yan|first2=Wei-Jun|title=Some identities on the Catalan, Motzkin, and Schröder numbers|journal=Discrete Applied Mathematics|date=2008|volume=156|issue=166–218X|pages=2781–2789|doi=10.1016/j.dam.2007.11.014|doi-access=free}}</ref>

<ref name="A033877">{{cite web|last1=Sloane|first1=N. J. A.|title=Triangular array associated with Schroeder numbers|url=https://oeis.org/A033877|website=The On-Line Encyclopedia of Integer Sequences|access-date=5 March 2018}}</ref>

<ref name="Schröder number formulas">{{cite journal|last1=Oi|first1=Feng|last2=Guo|first2=Bai-Ni|title=Some explicit and recursive formulas of the large and little Schröder numbers|journal=Arab Journal of Mathematical Sciences|date=2017|volume=23|issue=1319–5166|pages=141–147|doi=10.1016/j.ajmsc.2016.06.002|doi-access=free}}</ref>

<ref name="Eu Fu">{{cite journal|last1=Eu|first1=Sen-Peng|last2=Fu|first2=Tung-Shan|title=A simple proof of the Aztec diamond theorem|journal=Electronic Journal of Combinatorics|date=2005|volume=12|issue=1077–8926|page=Research Paper 18, 8|doi=10.37236/1915 |s2cid=5978643 |url=http://www.combinatorics.org/Volume_12/Abstracts/v12i1r18.html|doi-access=free}}</ref>

<ref name="IMC2019Prob4">{{cite web
|url=https://www.imc-math.org.uk/?year=2019&section=problems&item=prob4s
|title=Problem 4 (Solution)
|publisher=IMC
|website=IMC Problems 2019
|access-date=2024-08-27}}</ref>

}}

==Further reading==
*{{MathWorld|title=Schröder Number|urlname=SchroederNumber}}
* [[Richard P. Stanley|Stanley, Richard P.]]: [http://www-math.mit.edu/~rstan/ec/catadd.pdf Catalan addendum] to ''Enumerative Combinatorics, Volume 2''

{{Classes of natural numbers}}

{{DEFAULTSORT:Schroder number}}
[[Category:Integer sequences]]
[[Category:Enumerative combinatorics]]