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 celosía desde la esquina suroeste de una cuadrícula en la esquina noreste usando solo pasos hacia el norte, Noreste, o al este, que no se elevan por encima de la diagonal SW-NE. [1]
Lleva el nombre de | Ernst Schröder |
---|---|
No. de términos conocidos | infinito |
Primeros términos | 1 , 2 , 6 , 22 , 90 , 394 , 1806 |
Índice OEIS |
|
Los primeros números de Schröder son
dónde y Fueron nombrados en honor al matemático alemán Ernst Schröder .
Ejemplos de
La siguiente figura muestra los 6 caminos de este tipo a través de un red:
Construcciones relacionadas
Un largo camino de Schröder es un camino de celosía desde a con escalones al noreste, este, y sureste, que no vayan por debajo de la -eje. LaEl número de Schröder es el número de trayectorias de Schröder de longitud . [2] La siguiente figura muestra los 6 trayectos de Schröder de longitud 2.
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 corta a través puntos dados dentro del rectángulo en posición general, cada corte intersecta uno de los puntos y divide solo un 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 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:
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
Secuencias relacionadas
Los números de Schröder a veces se denominan números de Schröder grandes o grandes porque hay 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 súper catalanes . Las conexiones entre estos caminos se pueden ver de varias maneras:
- Considere los caminos de a 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 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]
- Así como hay (grandes) caminos de Schröder, un pequeño camino de Schröder es un camino de Schröder que no tiene escalones horizontales en el -eje. [4]
- Si es el el número de Schröder y es el el pequeño número de Schröder, luego por [4]
Las rutas de Schröder son similares a las 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 permiten un solo paso horizontal, (1,0), y cuentan tales caminos desde a . [5]
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
Es más fácil ver la conexión con los números de Schröder cuando la secuencia está en forma triangular:
k norte | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
0 | 1 | ||||||
1 | 1 | 2 | |||||
2 | 1 | 4 | 6 | ||||
3 | 1 | 6 | dieciséis | 22 | |||
4 | 1 | 8 | 30 | 68 | 90 | ||
5 | 1 | 10 | 48 | 146 | 304 | 394 | |
6 | 1 | 12 | 70 | 264 | 714 | 1412 | 1806 |
Entonces los números de Schröder son las entradas diagonales, es decir dónde es la entrada en fila y columna . La relación de recurrencia dada por este arreglo es
con y por . [6] Otra observación interesante a hacer es que la suma de losla fila es la st pequeño número de Schröder ; es decir,
- .
Relación de recurrencia
- por con , . [7]
Función generadora
La función generadora de es
- . [7]
Usos
Un tema de la combinatoria son las formas de mosaico , 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 organizar en alguna forma tal que ninguna de las fichas de dominó se superponen, la forma entera está cubierta, y ninguna de las fichas de dominó se adhieren a cabo de la forma?" La forma en que los números de Schröder tienen una conexión con es el diamante azteca . Mostrado a continuación, como referencia, hay un diamante azteca de orden 4 con un posible mosaico de dominó.
Resulta que el determinante de la Matriz de Hankel de los números de Schröder, es decir, la matriz cuadrada cuyala entrada es es el número de fichas de dominó de la orden Diamante azteca, que es [8] Es decir,
Por ejemplo:
Ver también
- Número de Delannoy
- Número de Motzkin
- Número de Narayana
- Número de Schröder – Hipparchus
- Número catalán
Referencias
- ^ Sloane, N. J. A. (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 de enteros . Fundación OEIS . Consultado el 5 de marzo de 2018 .
- ^ Ardila, Federico (2015). "Métodos algebraicos y geométricos en combinatoria enumerativa". Manual de combinatoria enumerativa . Boca Raton, FL: CRC Press. pag. 3-172.
- ^ Sloane, N. J. A. (ed.). "Secuencia A001003 (segundo problema de Schroeder (paréntesis generalizado); también llamados números super-catalanes o números pequeños de Schroeder)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS . Consultado el 5 de marzo de 2018 .
- ^ a b Drake, Dan (2010). "Biyecciones de caminos Dyck ponderados a caminos Schröder". arXiv : 1006.1959 [ math.CO ].
- ^ Deng, Eva YP; Yan, Wei-Jun (2008). "Algunas identidades en los números de Catalán, Motzkin y Schröder". Matemáticas aplicadas discretas . 156 (166–218X): 2781–2789. doi : 10.1016 / j.dam.2007.11.014 .
- ^ a b Sloane, NJA " Matriz triangular asociada con números de Schroeder" . La enciclopedia en línea de secuencias de enteros . Consultado el 5 de marzo de 2018 .
- ^ a b Oi, Feng; Guo, Bai-Ni (2017). "Algunas fórmulas explícitas y recursivas de los grandes y pequeños números de Schröder" . Revista Árabe de Ciencias Matemáticas . 23 (1319-5166): 141-147. doi : 10.1016 / j.ajmsc.2016.06.002 .
- ^ Eu, Sen-Peng; Fu, Tung-Shan (2005). "Una simple prueba del teorema del diamante azteca" . Revista electrónica de combinatoria . 12 (1077–8926): Documento de investigación 18, 8.
Otras lecturas
- Weisstein, Eric W. "Número de Schröder" . MathWorld .
- Stanley, Richard P .: Apéndice catalán a la combinatoria enumerativa, volumen 2