Números de Catalan
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. Obtienen su nombre del 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:
La secuencia catalana 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 catalana 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.
Una expresión alternativa para Cn es
Esta otra expresión muestra que Cn es un número natural, lo cual no resulta obvio a priori mirando la primera fórmula dada.
Una forma curiosa de generar Cn derivada de las fórmulas anteriores es a partir del factorial de cualquier número entero par . Se dividen todos los términos situados a la izquierda del factor , 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:
Y también satisfacen:
que puede ser una forma más eficiente de calcularlos.
La expresión en forma de recursión sería:
Asintóticamente, los números de Catalan crecen como:
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).
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 C3 = 5.