número de Schröder

Secuencia matemática de números enteros

En matemáticas , el número de Schröder , también llamado número de Schröder grande o número de Schröder grande , describe el número de caminos de red desde la esquina suroeste de una cuadrícula hasta la esquina noreste usando solo pasos individuales hacia el norte, noreste o este, que no se elevan por encima. 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 Deben su nombre al matemático alemán Ernst Schröder . ${\displaystyle S_{0}=1}$ ${\displaystyle S_{1}=2.}$

Ejemplos

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

Construcciones relacionadas

Un camino de longitud de Schröder es un camino de celosía de a con pasos al noreste, este y sureste, que no descienden por debajo del eje -. El número de Schröder 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 el número de formas de dividir un rectángulo en rectángulos más pequeños usando cortes a través de puntos dados dentro del rectángulo en su posición general, cada corte interseca uno de los puntos y divide solo un rectángulo en dos (es decir, el número de tabiques de guillotina estructuralmente diferentes ). Esto es similar al proceso de triangulación , en el que una forma 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 usando 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 usando tres cortes:

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

Secuencias relacionadas

A los números de Schröder a veces se les llama números de Schröder grandes o grandes 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 supercataleños . Las conexiones entre estos caminos se pueden ver de varias maneras:

• Considere los caminos de a con escalones y que no se eleven 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 números de Schröder (grandes) cuentan ambos tipos de caminos, y los números de Schröder pequeños cuentan sólo los caminos que sólo 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 hay caminos de Schröder (grandes), un camino de Schröder pequeño es un camino de Schröder que no tiene escalones horizontales en el eje -. ^[4] ${\displaystyle x}$
• Si es el enésimo número de Schröder y es el ené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 caminos de Dyck , pero permiten pasos horizontales 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 hay 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 el OEIS ).

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

Entonces los números de Schröder son las entradas diagonales, es decir, ¿ dónde está la entrada en fila y columna ? La relación de recurrencia dada por este arreglo 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 es el primer número pequeño de Schröder ; eso es, ${\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

${\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 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, rectángulos ) podemos colocar en una forma tal que ninguna de las fichas se superponga, toda la forma quede cubierta y ninguna de las fichas sobresalga de la forma?" La forma con la que tienen conexión los números de Schröder 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 enésima es es el número de teselas de dominó del orden diamante azteca, que es ^[8] 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}}$

Ver también

• 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

Referencias

1. Sloane, Nueva Jersey (ed.). "Secuencia A006318 (Números de Schröder grandes (o números de Schroeder grandes, o números de Schroeder grandes))". La enciclopedia en línea de secuencias enteras . 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 Ratón, FL: CRC Press. págs. 3–172.
3. Sloane, Nueva Jersey (ed.). "Secuencia A001003 (segundo problema de Schroeder (paréntesis generalizados); también llamados números supercataleños o números pequeños de Schroeder)". La enciclopedia en línea de secuencias enteras . Fundación OEIS . Consultado el 5 de marzo de 2018 .
4. Drake, Dan (2010). "Biyecciones de caminos ponderados de Dyck a caminos de Schröder". arXiv : 1006.1959 [matemáticas.CO].
5. Deng, Eva YP; Yan, Wei-Jun (2008). "Algunas identidades sobre los números de Catalan, Motzkin y Schröder". Matemática Aplicada Discreta . 156 (166–218X): 2781–2789. doi : 10.1016/j.dam.2007.11.014 .
6. Sloane, NJA "Matriz triangular asociada con números de Schroeder". La enciclopedia en línea de secuencias enteras . Consultado el 5 de marzo de 2018 .
7. , Feng; Guo, Bai-Ni (2017). "Algunas fórmulas explícitas y recursivas de los números grandes y pequeños de Schröder". Revista Árabe de Ciencias Matemáticas . 23 (1319–5166): 141–147. doi : 10.1016/j.ajmsc.2016.06.002 .
8. UE, Sen-Peng; Fu, Tung-Shan (2005). "Una prueba sencilla del teorema del diamante azteca". Revista Electrónica de Combinatoria . 12 (1077–8926): Trabajo de investigación 18, 8. doi : 10.37236/1915 . S2CID  5978643.

Otras lecturas

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