Número de Schröder

En matemáticas , el número de Schröder${\displaystyle S_{n},}$También llamado número de Schröder grande o número de Schröder grande , describe el número de caminos reticulares desde la esquina suroeste.${\displaystyle (0,0)}$de un${\displaystyle n\times n}$cuadrícula en la esquina noreste${\displaystyle (n,n),}$utilizando únicamente pasos individuales hacia el norte,${\displaystyle (0,1);}$nordeste,${\displaystyle (1,1);}$o hacia el este,${\displaystyle (1,0),}$que no se elevan por encima de la diagonal SO – NE. ^{[ 1 ]}

Los primeros números de Schröder son

1, 2, 6, 22, 90, 394, 1806, 8558, ... (secuencia A006318 en el OEIS ) .

dónde${\displaystyle S_{0}=1}$y${\displaystyle S_{1}=2.}$Recibieron su nombre en honor al matemático alemán Ernst Schröder .

La siguiente figura muestra los 6 caminos de este tipo a través de un${\displaystyle 2\times 2}$red:

Un camino de Schröder de longitud${\displaystyle n}$es un camino reticular desde${\displaystyle (0,0)}$a${\displaystyle (2n,0)}$con escalones hacia el noreste,${\displaystyle (1,1);}$este,${\displaystyle (2,0);}$y sureste,${\displaystyle (1,-1),}$que no bajan de la${\displaystyle x}$-eje. El${\displaystyle n}$El número de Schröder es el número de caminos de Schröder de longitud${\displaystyle n}$. ^{[ 2 ]} La siguiente figura muestra los 6 caminos de Schröder de longitud 2.

De manera similar, los números de Schröder cuentan el número de maneras de dividir un rectángulo en${\displaystyle n+1}$rectángulos más pequeños usando${\displaystyle n}$atraviesa${\displaystyle n}$Puntos dados dentro del rectángulo en posición general, cada corte interseca uno de los puntos y divide un único rectángulo en dos (es decir, el número de particiones de guillotina estructuralmente diferentes ). Esto es similar al proceso de triangulación , en el que una figura se divide en triángulos que no se superponen en lugar de rectángulos. La siguiente figura muestra las 6 disecciones de un rectángulo en 3 rectángulos mediante dos cortes:

En la imagen inferior se muestran las 22 disecciones de un rectángulo en 4 rectángulos utilizando tres cortes:

El número de Schröder${\displaystyle S_{n}}$también cuenta las permutaciones separables de longitud${\displaystyle n-1.}$

Los números de Schröder a veces se denominan números de Schröder grandes o de gran tamaño porque existe otra secuencia de Schröder: los números de Schröder pequeños , también conocidos como números de Schröder-Hipparchus o números supercatalanos . Las conexiones entre estas secuencias se pueden observar de varias maneras:

• Consideremos los caminos desde${\displaystyle (0,0)}$a${\displaystyle (n,n)}$con pasos${\displaystyle (1,1),}$${\displaystyle (2,0),}$y${\displaystyle (1,-1)}$que no se elevan por encima de la diagonal principal. Hay dos tipos de trayectorias: las que tienen movimientos a lo largo de la diagonal principal y las que no. Los números de Schröder (grandes) cuentan ambos tipos de trayectorias, y los números de Schröder pequeños cuentan solo las trayectorias que solo tocan la diagonal pero no tienen movimientos a lo largo de ella. ^{[ 3 ]}
• Así como existen caminos de Schröder (grandes), un pequeño camino de Schröder es un camino de Schröder que no tiene escalones horizontales en el${\displaystyle x}$eje -. ^{[ 4 ]}
• Si${\displaystyle S_{n}}$es el${\displaystyle n}$el número de Schröder y${\displaystyle s_{n}}$es el${\displaystyle n}$el pequeño número de Schröder, entonces${\displaystyle S_{n}=2s_{n}}$para${\displaystyle n>0}$${\displaystyle (S_{0}=s_{0}=1).}$^{[ 4 ]}

Las trayectorias de Schröder son similares a las de Dyck, pero permiten el paso horizontal en lugar de solo pasos diagonales. Otro tipo de trayectoria similar es la que cuentan los números de Motzkin ; las trayectorias de Motzkin permiten las mismas trayectorias diagonales, pero solo permiten un único paso horizontal, (1,0), y cuentan dichas trayectorias desde${\displaystyle (0,0)}$a${\displaystyle (n,0)}$. ^{[ 5 ]}

También existe una matriz triangular asociada a los números de Schröder que proporciona una relación de recurrencia ^{[ 6 ]} (aunque no solo con los números de Schröder). Los primeros términos son:

1, 1, 2, 1, 4, 6, 1, 6, 16, 22, .... (secuencia A033877 en el OEIS ) .

Es más fácil ver la conexión con los números de Schröder cuando la secuencia está en su forma triangular:

Entonces, los números de Schröder son las entradas diagonales, es decir${\displaystyle S_{n}=T(n,n)}$dónde${\displaystyle T(n,k)}$es la entrada en la fila${\displaystyle n}$y columna${\displaystyle k}$La relación de recurrencia dada por esta disposición es

${\displaystyle T(n,k)=T(n,k-1)+T(n-1,k-1)+T(n-1,k)}$

con${\displaystyle T(1,k)=1}$y${\displaystyle T(n,k)=0}$para${\displaystyle k>n}$. ^{[ 6 ]} Otra observación interesante que se puede hacer es que la suma de la${\displaystyle n}$La fila es la${\displaystyle (n+1)}$el pequeño número de Schröder ; es decir,

${\displaystyle \sum _{k=0}^{n}T(n,k)=s_{n+1}}$.

Con${\displaystyle S_{0}=1}$,${\displaystyle S_{1}=2}$, ^{[ 7 ]}

${\displaystyle S_{n}=3S_{n-1}+\sum _{k=1}^{n-2}S_{k}S_{n-k-1}}$para${\displaystyle n\geq 2}$

y también ^{[ 8 ]}

${\displaystyle S_{n}={\frac {6n-3}{n+1}}S_{n-1}-{\frac {n-2}{n+1}}S_{n-2}}$para${\displaystyle n\geq 2}$

La función generadora${\displaystyle G(x)}$de la secuencia${\displaystyle (S_{n})_{n\geq 0}}$es

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

Se puede expresar en términos de la función generatriz de los números de Catalan.${\displaystyle C(x)={\frac {1-{\sqrt {1-4x}}}{2x}}}$como

${\displaystyle G(x)={\frac {1}{1-x}}C{\big (}{\frac {x}{(1-x)^{2}}}{\big )}.}$

Un tema de la combinatoria es el teselado de formas, y un caso particular de esto son los teselados de dominó ; la pregunta en este caso es: "¿Cuántos dominós (es decir,${\displaystyle 1\times 2}$o${\displaystyle 2\times 1}$¿Podemos disponer las fichas de dominó en alguna forma de manera que ninguna se superponga, cubra toda la figura y ninguna sobresalga? La forma con la que se relacionan los números de Schröder es el diamante azteca . A continuación se muestra, a modo de referencia, un diamante azteca de orden 4 con una posible disposición de fichas de dominó.

Resulta que el determinante de la${\displaystyle (2n-1)\times (2n-1)}$matriz de Hankel de los números de Schröder, es decir, la matriz cuadrada cuya${\displaystyle (i,j)}$La entrada es${\displaystyle S_{i+j-1},}$es el número de fichas de dominó del orden${\displaystyle n}$Diamante azteca, que es${\displaystyle 2^{n(n+1)/2}.}$^{[ 9 ]} Es decir,

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

Por ejemplo:

• ${\displaystyle {\begin{vmatrix}2\end{vmatrix}}=2=2^{1(2)/2}}$

• ${\displaystyle {\begin{vmatrix}2&6\\6&22\end{vmatrix}}=8=2^{2(3)/2}}$

• ${\displaystyle {\begin{vmatrix}2&6&22\\6&22&90\\22&90&394\end{vmatrix}}=64=2^{3(4)/2}}$

• Número de Delannoy
• Número de Motzkin
• Número de Narayana
• Polinomios de Narayana
• Número de Schröder-Hiparco
• Número catalán

• Weisstein, Eric W. "El número de Schröder" . MundoMatemático .
• Stanley, Richard P .: Apéndice catalán a Combinatoria enumerativa, Volumen 2