Números de Catalan

Números de Catalan
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. 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.

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