El triángulo catalán

En matemáticas combinatorias , el triángulo de Catalan es un triángulo numérico cuyas entradas dan el número de cadenas que constan de n X y k Y de modo que ningún segmento inicial de la cadena tiene más Y que X. Es una generalización de los números de Catalan y recibe su nombre de Eugène Charles Catalan . Bailey ^[1] demuestra que satisfacen las siguientes propiedades: ${\displaystyle C(n,k)}$ ${\displaystyle C(n,k)}$

1. ${\displaystyle C(n,0)=1{\text{ for }}n\geq 0}$.
2. ${\displaystyle C(n,1)=n{\text{ for }}n\geq 1}$.
3. ${\displaystyle C(n+1,k)=C(n+1,k-1)+C(n,k){\text{ for }}1<k<n+1}$
4. ${\displaystyle C(n+1,n+1)=C(n+1,n){\text{ for }}n\geq 1}$.

La fórmula 3 muestra que la entrada en el triángulo se obtiene recursivamente sumando números a la izquierda y arriba del triángulo. La primera aparición del triángulo de Catalan junto con la fórmula de recursión 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 llama triángulo catalán y que es distinto del triángulo que se analiza aquí.

Fórmula general

La fórmula general para está dada por ^{[1] [4]} ${\displaystyle C(n,k)}$

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

Entonces

${\displaystyle C(n,k)={\frac {n-k+1}{n+1}}{\binom {n+k}{k}}}$

Cuando , la diagonal C ( n , n ) es el n -ésimo número catalán . ${\displaystyle k=n}$

La suma de las filas de la n -ésima fila es el ( n + 1) -ésimo número catalán , utilizando la identidad del palo de hockey y una expresión alternativa para los números catalanes.

Tabla de valores

Algunos valores se dan mediante ^[5]

Propiedades

• La fórmula 3 de la primera sección se puede utilizar para demostrar ambos

${\displaystyle C(n,k)=\sum _{i=0}^{k}C(n-1,i)=\sum _{i=k}^{n}C(i,k-1)}$

Es decir, una entrada es la suma parcial de la fila anterior y también la suma parcial de la columna de la izquierda (excepto la entrada en la diagonal).

• Si , entonces en algún momento debe haber más Y que X , entonces . ${\displaystyle k>n}$ ${\displaystyle C(n,k)=0}$

• Una interpretación combinatoria del valor -ésimo es el número de particiones no decrecientes con exactamente n partes con una parte máxima k tal que cada parte es menor o igual que su índice. Así, por ejemplo, cuenta ${\displaystyle (n,k-1)}$ ${\displaystyle (4,2)=9}$

${\displaystyle 1111,1112,1113,1122,1123,1133,1222,1223,1233}$

Generalización

Los trapecios de Catalan son un conjunto numerable de trapecios numéricos que generalizan el triángulo de Catalan. El trapecio de Catalan de orden m = 1, 2, 3, ... es un trapecio numérico cuyas entradas dan el número de cadenas que constan de n X y k Y tales que en cada segmento inicial de la cadena el número de Y no excede el número de X en m o más. ^[6] Por definición, el trapecio de Catalan de orden m = 1 es el triángulo de Catalan, es decir, . ${\displaystyle C_{m}(n,k)}$ ${\displaystyle C_{1}(n,k)=C(n,k)}$

Algunos valores del trapezoide de Catalan de orden m = 2 están dados por

Algunos valores del trapezoide de Catalan de orden m = 3 están dados por

Nuevamente cada elemento es la suma del de arriba y el de la izquierda.

Una fórmula general para está dada por ${\displaystyle C_{m}(n,k)}$

${\displaystyle C_{m}(n,k)={\begin{cases}\left({\begin{array}{c}n+k\\k\end{array}}\right)&\,\,\,0\leq k<m\\\\\left({\begin{array}{c}n+k\\k\end{array}}\right)-\left({\begin{array}{c}n+k\\k-m\end{array}}\right)&\,\,\,m\leq k\leq n+m-1\\\\0&\,\,\,k>n+m-1\end{cases}}}$

( n = 0, 1, 2, ... , k = 0, 1, 2, ... , m = 1, 2, 3, ... ).

Pruebas de la fórmula general

Prueba 1

Esta prueba implica una extensión del método de reflexión de Andre , tal como se utilizó en la segunda prueba para el número de Catalan, a diferentes diagonales. A continuación se muestra cómo cada camino desde la parte inferior izquierda hasta la parte superior derecha del diagrama que cruza la restricción también se puede reflejar hasta el punto final . ${\displaystyle (0,0)}$ ${\displaystyle (k,n)}$ ${\displaystyle n-k+m-1=0}$ ${\displaystyle (n+m,k-m)}$

Consideramos tres casos para determinar el número de caminos desde hasta que no cruzan la restricción: ${\displaystyle (0,0)}$ ${\displaystyle (k,n)}$

(1) cuando la restricción no se puede cruzar, por lo que todos los caminos de a son válidos, es decir . ${\displaystyle m>k}$ ${\displaystyle (0,0)}$ ${\displaystyle (k,n)}$ ${\displaystyle C_{m}(n,k)=\left({\begin{array}{c}n+k\\k\end{array}}\right)}$

(2) cuando es imposible formar un camino que no cruce la restricción, es decir . ${\displaystyle k-m+1>n}$ ${\displaystyle C_{m}(n,k)=0}$

(3) cuando , entonces es el número de caminos 'rojos' menos el número de caminos 'amarillos' que cruzan la restricción, es decir . ${\displaystyle m\leq k\leq n+m-1}$ ${\displaystyle C_{m}(n,k)}$ ${\displaystyle \left({\begin{array}{c}n+k\\k\end{array}}\right)}$ ${\displaystyle \left({\begin{array}{c}(n+m)+(k-m)\\k-m\end{array}}\right)=\left({\begin{array}{c}n+k\\k-m\end{array}}\right)}$

Por lo tanto, el número de caminos de a que no cruzan la restricción es el indicado en la fórmula de la sección anterior " Generalización ". ${\displaystyle (0,0)}$ ${\displaystyle (k,n)}$ ${\displaystyle n-k+m-1=0}$

Prueba 2

En primer lugar, confirmamos la validez de la relación de recurrencia descomponiéndola en dos partes, la primera para las combinaciones XY que terminan en X y la segunda para las que terminan en Y. Por tanto, el primer grupo tiene combinaciones válidas y el segundo tiene . La demostración 2 se completa verificando que la solución satisface la relación de recurrencia y obedece las condiciones iniciales para y . ${\displaystyle C_{m}(n,k)=C_{m}(n-1,k)+C_{m}(n,k-1)}$ ${\displaystyle C_{m}(n,k)}$ ${\displaystyle C_{m}(n-1,k)}$ ${\displaystyle C_{m}(n,k-1)}$ ${\displaystyle C_{m}(n,0)}$ ${\displaystyle C_{m}(0,k)}$

Referencias

1. Bailey, DF (1996). "Disposiciones de conteo de 1 y -1". Revista de matemáticas . 69 (2): 128–131. doi :10.1080/0025570X.1996.11996408.
2. Arbogast, LFA (1800). Du Calcul des Derivations. Levrault. pag. 214.
3. Shapiro, LW (1976). "Un triángulo catalán". Matemáticas discretas . 14 (1): 83–90. doi : 10.1016/0012-365x(76)90009-1 .
4. Eric W. Weisstein. "Triángulo de Catalan". MathWorld − Un recurso web de Wolfram . Consultado el 28 de marzo de 2012 .
5. Sloane, N. J. A. (ed.). "Secuencia A009766 (triángulo de Catalan)". La enciclopedia en línea de secuencias de enteros . Fundación OEIS . Consultado el 28 de marzo de 2012 .
6. Reuveni, Shlomi (2014). "Trapecios de Catalán". Probabilidad en la Ingeniería y las Ciencias de la Información . 28 (3): 4391–4396. doi :10.1017/S0269964814000047. S2CID  122765015.