Número de Schröder

Sucesión matemática de números enteros

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

Los primeros números de Schröder son

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

donde y Fueron nombrados en honor al matemático alemán Ernst Schröder . ${\displaystyle S_{0}=1}$ ${\displaystyle S_{1}=2.}$

Ejemplos

La siguiente figura muestra las 6 rutas de este tipo a través de una cuadrícula: ${\displaystyle 2\times 2}$

Construcciones relacionadas

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

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

A continuación se muestran las 22 disecciones de un rectángulo en 4 rectángulos utilizando tres cortes:

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

Secuencias relacionadas

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

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

Los caminos de Schröder son similares a los de Dyck, pero permiten el paso horizontal en lugar de solo pasos diagonales. Otro camino similar es el tipo de camino que cuentan los números de Motzkin ; los caminos de Motzkin permiten los mismos caminos diagonales, pero solo permiten un paso horizontal (1,0), y cuentan dichos caminos desde hasta . ^[5] ${\displaystyle (0,0)}$ ${\displaystyle (n,0)}$

También existe una matriz triangular asociada con 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 la 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, donde es la entrada en la fila y la columna . La relación de recurrencia dada por esta disposición es ${\displaystyle S_{n}=T(n,n)}$ ${\displaystyle T(n,k)}$ ${\displaystyle n}$ ${\displaystyle k}$

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

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

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

Relaciones de recurrencia

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

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

Función generadora

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

${\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 generadora de números catalanes como ${\displaystyle C(x)={\frac {1-{\sqrt {1-4x}}}{2x}}}$

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

Usos

Un tema de la combinatoria es el mosaico de formas, y un ejemplo particular de esto son los mosaicos de dominó ; la pregunta en este caso es: "¿Cuántas fichas de dominó (es decir, o rectángulos) podemos colocar en alguna forma de manera que ninguna de las fichas de dominó se superponga, toda la forma esté cubierta y ninguna de las fichas de dominó sobresalga de la forma?" La forma con la que los números de Schröder tienen una conexión es el diamante azteca . A continuación se muestra como referencia un diamante azteca de orden 4 con un posible mosaico de dominó. ${\displaystyle 1\times 2}$ ${\displaystyle 2\times 1}$

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

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

Véase también

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

Referencias

1. Sloane, N. J. A. (ed.). «Secuencia A006318 (Grandes números de Schröder (o grandes números de Schroeder, o grandes números de Schroeder).)». La enciclopedia en línea de secuencias de números enteros . Fundación OEIS . Consultado el 5 de marzo de 2018 .
2. Ardila, Federico (2015). "Métodos algebraicos y geométricos en combinatoria enumerativa". Manual de combinatoria enumerativa . Boca Raton, FL: CRC Press. pp. 3–172.
3. Sloane, N. J. A. (ed.). «Secuencia A001003 (Segundo problema de Schroeder (paréntesis generalizados); también llamados números supercatalanos o pequeños números de Schroeder)». La enciclopedia en línea de secuencias de enteros . Fundación OEIS . Consultado el 5 de marzo de 2018 .
4. Drake, Dan (2010). "Biyecciones desde caminos de Dyck ponderados a caminos de Schröder". arXiv : 1006.1959 [math.CO].
5. Deng, Eva YP; Yan, Wei-Jun (2008). "Algunas identidades en los números de Catalan, Motzkin y Schröder". Matemáticas Aplicadas Discretas . 156 (166–218X): 2781–2789. doi : 10.1016/j.dam.2007.11.014 .
6. Sloane, NJA "Matriz triangular asociada con números de Schröder". La enciclopedia en línea de secuencias de números enteros . Consultado el 5 de marzo de 2018 .
7. Oi, Feng; Guo, Bai-Ni (2017). "Algunas fórmulas explícitas y recursivas de los números de Schröder grandes y pequeños". Revista Árabe de Ciencias Matemáticas . 23 (1319–5166): 141–147. doi : 10.1016/j.ajmsc.2016.06.002 .
8. "Problema 4 (solución)". Problemas de IMC 2019 . IMC . Consultado el 27 de agosto de 2024 .
9. Eu, Sen-Peng; Fu, Tung-Shan (2005). "Una prueba simple del teorema del diamante azteca". Revista electrónica de combinatoria . 12 (1077–8926): Documento de investigación 18, 8. doi : 10.37236/1915 . S2CID  5978643.

Lectura adicional

• Weisstein, Eric W. "El número de Schröder". MundoMatemático .
• Stanley, Richard P. : Adenda catalana a Combinatoria Enumerativa, Volumen 2