Números de Catalan

Fue el gran Leonhard Euler (1707-1783) la primera persona en calcular los denominados números de Catalan. Le comunicó los primeros valores a Johann Segner (1704-1777), pero no le dijo la técnica que utilizó para calcularlos. Segner obtiene estos números, por recurrencia,  al estudiar las posibles triangulación de un polígono.

Una triángulación de un polígono es una forma de descomponerlo como una unión disjunta de triángulos cuyos vértices coinciden con los del polígono. Es fácil ver que para triangular un polígono de n+2 vértices se necesitan n triángulos y viceversa.

Sea Cn el número de maneras de descomponer un polígono utilizando exactamente en triángulos. Como se observa en la imagen: $$C_1=1, C_2=2, C_3=5, C_4=14 $$

La fórmula de recurrencia, dada por Signer en 1758, para obtener los números de catalán es: $$C_{n+1}=C_0·C_n+C_1·C_{n-1}+C_2·C_{n-2}+\cdots+C_{n-1}·C_1+C_n·C_0$$ siendo $$C_0=1$$
Demostración por inducción:

Si sabemos triangular los polígonos de n+2 lados, entonces podemos triangular un polígono de n+3 lados.

El polígono tiene los vértices 1,2,3,...n+3 y escogemos un 'lado favorito': el lado de vértices 1 y n+3, que pertenece a un triángulo Ti de la triangulación, siendo i el tercer vértice que pertenece al conjunto {2,3,...n+2}.

En la figura se observa que sería el triángulo de vértices 1,4 y 8.

En general, si se elimina ese triángulo Ti, resultan dos polígonos:

• Vértices 1,2,...i que puede ser triangulado de Ci-2 maneras.
• Vértices i,i+1,,...n+3 que puede ser triangulado de Cn-i+2 maneras.

Ambas elecciones son independientes, por tanto la manera de triangular el polígono que contiene al triángulo Ti es:
$$C_{i-2}·C_{n-i+2}$$
Al variar Ti sobre todos los valores posibles {2,3...n+2} se obtiene la fórmula.

Alrededor de un siglo después Eugène Catalan (1814-1894), volverá a calcular el número de maneras de triangular un polígono. En su memoria, esos números  llevan  su nombre.

Es una fórmula que evita la recurrencia y permite obtener directamente los números:

$$C_n=\frac{1}{n+1} \binom{2n}{n}=\frac{(2n)!}{(n+1)!·n!} \wedge n\geq 0$$
A partir de esta fórmula se puede obtener una fórmula de recurrencia más sencilla:
$$\frac{C_{n+1}}{C_n}=\frac{(2n+2)!}{(n+2)!(n+1)!}:\frac{(2n)!}{(n+1)!n!}=\frac{2(2n+1)}{n+2}$$
$$C_{n+1}=\frac{2(2n+1)}{n+2}{C_n}\wedge n\geq 1$$

Existen infinidad de situaciones en las que aparecen los números de Catalan. Una de ellas es el número de caminos monótonos crecientes a través de una retícula de tamaño nxn y que no atraviesen la diagonal:

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:

En su página de internet Richard Stanley, nos reta con 95 familias de objetos enumerados por los números de Catalan.