Triángulo de Catalan

En matemáticas combinatorias , el triángulo de Catalan es un triángulo numérico cuyas entradas${\displaystyle C(n,k)}$da el número de cadenas que constan de n X y k Y tales 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 ]} muestra que${\displaystyle C(n,k)}$Satisfacer las siguientes propiedades:

1. ${\displaystyle C(n,0)=1{\text{ para }}n\geq 0}$.
2. ${\displaystyle C(n,1)=n{\text{ para }}n\geq 1}$.
3. ${\displaystyle C(n+1,k)=C(n+1,k-1)+C(n,k){\text{ para }}1<k<n+1}$
4. ${\displaystyle C(n+1,n+1)=C(n+1,n){\text{ para }}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 en el 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 sobre cálculo publicado en 1800 ^{[ 2 ]} por Louis François Antoine Arbogast .

Shapiro ^{[ 3 ]} introduce otro triángulo que él llama triángulo catalán que es distinto del triángulo que se está discutiendo aquí.

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

${\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${\displaystyle k=n}$, la diagonal C ( n , n ) es el n - ésimo número de Catalan .

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

Algunos valores se dan en ^{[ 5 ]}

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

${\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 superior y también la suma parcial de la columna de la izquierda (excepto la entrada de la diagonal).

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

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

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

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${\displaystyle C_{m}(n,k)}$dar el número de cadenas que constan de n Xs y k Ys tales que en cada segmento inicial de la cadena el número de Ys ​​no excede el número de Xs 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_{1}(n,k)=C(n,k)}$.

Algunos valores del trapecio de Catalan de orden m = 2 vienen dados por

Algunos valores del trapecio de Catalan de orden m = 3 vienen dados por

De nuevo, cada elemento es la suma del que está arriba y el que está a la izquierda.

Una fórmula general para${\displaystyle C_{m}(n,k)}$es dado por

${\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, ... ).