Números de Catalan

Números de Catalan
n
01
11
22
35
414
542
6132
7429
81.430
94.862
1016.796
1158.786
12208.012
13742.900
142.674.440
159.694.845
1635.357.670
17129.644.790
18477.638.700
191.767.263.190
206.564.120.420
2124.466.267.020
2291.482.563.640
23343.059.613.650
241.289.904.147.324
254.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. 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:

Propiedades

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).

Other Languages