Números de Catalan
# Números de Catalan

| n | $C_{n}\,$ |
| - | - |
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
| 5 | 42 |
| 6 | 132 |
| 7 | 429 |
| 8 | 1.430 |
| 9 | 4.862 |
| 10 | 16.796 |
| 11 | 58.786 |
| 12 | 208.012 |
| 13 | 742.900 |
| 14 | 2.674.440 |
| 15 | 9.694.845 |
| 16 | 35.357.670 |
| 17 | 129.644.790 |
| 18 | 477.638.700 |
| 19 | 1.767.263.190 |
| 20 | 6.564.120.420 |
| 21 | 24.466.267.020 |
| 22 | 91.482.563.640 |
| 23 | 343.059.613.650 |
| 24 | 1.289.904.147.324 |
| 25 | 4.861.946.401.452 |

En combinatoria, los números de Catalan forman una secuencia de números naturales que aparece en varios problemas de conteo que habitualmente son recursivos. Su nombre hace referencia al matemático belga Eugène Charles Catalan (1814-1894).

El n-ésimo número de Catalan se obtiene, aplicando coeficientes binomiales, a partir de la siguiente fórmula:

    $C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ con }}n\geq 0.$

## Historia

La secuencia de números de Catalan fue descrita en el siglo XVIII por Leonhard Euler. La secuencia lleva el nombre de Eugène Charles Catalan, quien descubrió la conexión con las expresiones entre paréntesis durante su exploración del rompecabezas de las torres de Hanói.

En 1988, salió a la luz que la secuencia numérica de Catalan había sido utilizada en China por el matemático mongol Minggatu hacia 1730. Fue cuando comenzó a escribir su libro Ge Yuan Mi Lu Jie Fa [El método rápido para obtener la relación precisa de división de un círculo], que fue completado por su alumno Chen Jixin en 1774, pero publicado sesenta años después.

## Propiedades

Una expresión alternativa para $C_n$ es

    $C_{n}={2n \choose n}-{2n \choose n-1}\quad {\mbox{ con }}n\geq 1.$

Esta otra expresión muestra que $C_n$ es un número natural, lo cual no resulta obvio a priori observando la primera fórmula dada.

Una forma curiosa de generar $C_n,$ derivada de las fórmulas anteriores, es a partir del factorial de cualquier número entero par $(2n)!$. Se dividen todos los términos situados a la izquierda del factor $n+1$, entre todos los términos situados a su derecha y el resultado será el n-ésimo número de Catalan.

Los números de Catalan satisfacen la siguiente relación de recurrencia:

    $C_{0}=1\quad {\mbox{y}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\mbox{con }}n\geq 0.$

Y también satisfacen:

    $C_{0}=1\quad {\mbox{y}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},$

que puede ser una forma más eficiente de calcularlos.

La expresión en forma de recursión sería:

    $C_{n}={\begin{cases}{\mbox{si }}n=0&\Rightarrow 1\\{\mbox{si }}n>0&\Rightarrow {\cfrac {2(2n-1)}{n+1}}\,C_{n-1}\end{cases}}$

Asintóticamente, los números de Catalan crecen como:

    $C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$

considerando que el cociente entre el n-ésimo número de Catalan y la expresión de la derecha tiende hacia 1 cuando n → ∞ (esto puede probarse usando la fórmula de Stirling).

## Aplicaciones en combinatoria

Existen múltiples problemas de combinatoria cuya solución la dan los números de Catalan. El libro Enumerative Combinatorics: Volume 2, de Richard P. Stanley contiene un conjunto de ejercicios que describen 66 interpretaciones distintas de los números de Catalan. Aquí se muestran algunos ejemplos, con ilustraciones para el caso $C_3$ = 5.

* $C_n$ es el número de palabras de Dyck de longitud 2n. Una palabra de Dyck es una cadena de caracteres que consiste en n X's y n Y's de forma que no haya ningún segmento inicial que tenga más Y's que X's. Por ejemplo, lo siguiente son las palabras de Dyck de longitud 6:
* Reinterpretando el símbolo X como un paréntesis abierto y la Y como un paréntesis cerrado, $C_n$ cuenta el número de expresiones que contienen n pares de paréntesis correctamente colocados:
* $C_n$ es el número de formas distintas de agrupar n + 1 factores mediante paréntesis (o el número de formas de asociar n aplicaciones de un operador binario). Para n = 3 por ejemplo, tenemos las siguientes cinco formas distintas de agrupar los cuatro factores:

$((ab)c)d\quad (a(bc))d\quad (ab)(cd)\quad a((bc)d)\quad a(b(cd))$

* Las aplicaciones sucesivas de un operador binario pueden representarse con un árbol binario. En este caso, $C_n$ es el número de árboles binarios de n + 1 hojas, en los que cada nodo tiene cero o dos hijos:
* $C_n$ es el número de caminos monótonos que se pueden trazar a través de las líneas de una malla de n × n celdas cuadradas, de forma que nunca se cruce la diagonal. Un camino monótono es aquel que empieza en la esquina inferior izquierda y termina en la esquina superior derecha, y consiste únicamente en tramos que apuntan hacia arriba o hacia la derecha. El recuento de estos caminos es equivalente a contar palabras de Dyck: X significa "moverse a la derecha" e Y significa "moverse hacia arriba". Los siguientes diagramas muestran el caso n = 3:
* $C_n$ es el número de formas distintas de dividir un polígono convexo de n + 2 lados en triángulos conectando vértices con diagonales sin que ninguna se corte. La siguiente figura ilustra el caso de las $c_{4}$ = 14 posibles triangulaciones para un polígono de 6 lados:
