En matemática combinatoria , el triángulo catalán es un triángulo numérico cuyas entradasIndique el número de cadenas que constan de n X y k Y de manera que ningún segmento inicial de la cadena tenga más Y que X. Es una generalización de los números catalanes y lleva el nombre de Eugène Charles Catalan . Bailey [1] muestra que satisfacen las siguientes propiedades:
- .
- .
- .
La fórmula 3 muestra que la entrada en el triángulo se obtiene de forma recursiva sumando números a la izquierda y arriba del triángulo. La primera aparición del triángulo catalán junto con la fórmula de recursividad se encuentra en la página 214 del tratado de cálculo publicado en 1800 [2] por Louis François Antoine Arbogast .
Shapiro [3] introduce otro triángulo que él llama el triángulo catalán que es distinto del triángulo que estamos discutiendo aquí.
Formula general
La fórmula general para viene dado por [1] [4]
donde n y k son números enteros no negativos y n ! denota el factorial . Por tanto, para k > 0,.
La diagonal C ( n , n ) es el n -ésimo número catalán . La suma de filas de la n -ésima fila es el ( n + 1) -ésimo número catalán .
Algunos valores vienen dados por [5]
- knorte
0 1 2 3 4 5 6 7 8 0 1 1 1 1 2 1 2 2 3 1 3 5 5 4 1 4 9 14 14 5 1 5 14 28 42 42 6 1 6 20 48 90 132 132 7 1 7 27 75 165 297 429 429 8 1 8 35 110 275 572 1001 1430 1430
Generalización
Los trapezoides de Catalán son un conjunto contable de trapezoides numéricos que generalizan el triángulo de Catalán. El trapezoide catalán de orden m = 1, 2, 3, ... es un trapezoide numérico cuyas entradasIndique el número de cadenas que constan de n X y k Y de modo que en cada segmento inicial de la cadena el número de Y no exceda el número de X en m o más. [6] Por definición, el trapezoide catalán de orden m = 1 es el triángulo catalán, es decir,.
Algunos valores del trapezoide catalán de orden m = 2 vienen dados por
- knorte
0 1 2 3 4 5 6 7 8 0 1 1 1 1 2 2 2 1 3 5 5 3 1 4 9 14 14 4 1 5 14 28 42 42 5 1 6 20 48 90 132 132 6 1 7 27 75 165 297 429 429 7 1 8 35 110 275 572 1001 1430 1430
Algunos valores del trapezoide catalán de orden m = 3 vienen dados por
- knorte
0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 2 3 3 2 1 3 6 9 9 3 1 4 10 19 28 28 4 1 5 15 34 62 90 90 5 1 6 21 55 117 207 297 297 6 1 7 28 83 200 407 704 1001 1001 7 1 8 36 119 319 726 1430 2431 3432 3432
Nuevamente, cada elemento es la suma del de arriba y el de la izquierda.
Una fórmula general para es dado por
( n = 0, 1, 2, ... , k = 0, 1, 2, ... , m = 1, 2, 3, ... ).
Pruebas de la fórmula general para [[Categoría: artículos a los que les faltan identificadores de escala de magnitud]] (n, k)" data-section="3" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-wikimedia-edit-base20 edit-page mw-ui-icon-flush-right">Editar
Prueba 1
Esta prueba implica la extensión del método Andrés Reflexión como se utilizó en la segunda prueba para el número catalán . A continuación se muestra cómo cada camino desde la parte inferior izquierda arriba a la derecha del diagrama que cruza la restricción también se puede reflejar en el punto final .
Consideramos tres casos para determinar el número de caminos desde a que no cruzan la restricción:
(1) cuando la restricción no se puede cruzar, por lo que todos los caminos desde a son válidos, es decir .
(2) cuando es imposible formar un camino que no cruce la restricción, es decir .
(3) cuando , luego es el número de caminos 'rojos' menos el número de rutas 'amarillas' que cruzan la restricción, es decir .
Así, el número de caminos desde a que no cruzan la restricción es como se indica en la fórmula del apartado anterior " Generalización ".
Prueba 2
En primer lugar, confirmamos la validez de la relación de recurrencia rompiendo en dos partes, la primera para las combinaciones XY que terminan en X y la segunda para las que terminan en Y. Por lo tanto, el primer grupo tiene combinaciones válidas y el segundo tiene . La prueba 2 se completa verificando que la solución satisface la relación de recurrencia y obedece las condiciones iniciales para y .
Ver también
Referencias
- ↑ a b Bailey, DF (1996). "Contando arreglos de 1 y -1". Revista de Matemáticas . 69 (2): 128-131. doi : 10.1080 / 0025570X.1996.11996408 .
- ^ Arbogast, LFA (1800). Du Calcul des Derivations . pag. 214 .
- ^ Shapiro, LW (1976). "Un triángulo catalán" . Matemáticas discretas . 14 (1): 83–90. doi : 10.1016 / 0012-365x (76) 90009-1 .
- ^ Eric W. Weisstein. "Triángulo catalán" . MathWorld: un recurso web de Wolfram . Consultado el 28 de marzo de 2012 .
- ^ Sloane, N. J. A. (ed.). "Secuencia A009766 (triángulo catalán)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS . Consultado el 28 de marzo de 2012 .
- ^ Reuveni, Shlomi (2014). "Trapezoides catalanes". Probabilidad en Ingeniería y Ciencias de la Información . 28 (3): 4391–4396. doi : 10.1017 / S0269964814000047 .