1. ¿Qué son los números de Catalan?
Los números de Catalan forman una sucesión de números enteros que aparece en numerosos problemas de enumeración. Su definición comienza con C0 = 1 y continúa:
1, 1, 2, 5, 14, 42, 132, 429, ...
El término Cn cuenta diferentes estructuras combinatorias con tamaño n.
2. Fórmula directa
El n-ésimo número de Catalan puede calcularse mediante:
Cn = 1/(n + 1) · C(2n, n)
También puede escribirse como:
Cn = (2n)! / ((n + 1)! n!)
La forma con coeficientes binomiales conecta Catalan con los contenidos estudiados anteriormente.
3. Recurrencia de Catalan
Una definición recursiva muy importante es:
C0 = 1
Cn = C0Cn-1 + C1Cn-2 + ... + Cn-1C0
De forma compacta, Cn = Σ CiCn-1-i, para i entre 0 y n - 1.
4. Interpretación de la recurrencia
La suma separa una estructura en dos partes. Si la primera parte tiene tamaño i, la segunda tiene tamaño n - 1 - i. Hay Ci formas de construir la primera y Cn-1-i formas de construir la segunda.
Por el principio del producto, las posibilidades de ese corte son CiCn-1-i; luego se suman todos los cortes posibles.
5. Paréntesis correctamente balanceados
Cn cuenta las formas de colocar n pares de paréntesis de modo que toda expresión sea válida. Para n = 3 aparecen:
((())), (()()), (())(), ()(()), ()()()
En ningún prefijo puede haber más paréntesis de cierre que de apertura, y al final ambos tipos deben tener la misma cantidad.
6. Implementación con recurrencia
La recurrencia puede implementarse con programación dinámica. Se calculan los términos desde C0 hasta Cn y se reutilizan los valores obtenidos.
function catalanRecurrencia(n) {
const catalan = Array(n + 1).fill(0);
catalan[0] = 1;
for (let tam = 1; tam <= n; tam++) {
for (let izquierda = 0; izquierda < tam; izquierda++) {
catalan[tam] += catalan[izquierda] * catalan[tam - 1 - izquierda];
}
}
return catalan[n];
}
console.log(catalanRecurrencia(5)); // 427. Árboles binarios completos
El número Cn cuenta árboles binarios completos con n nodos internos. La raíz divide el árbol en un subárbol izquierdo y uno derecho, y la distribución de los nodos produce exactamente la recurrencia de Catalan.
Esta interpretación resulta útil para estudiar distintas formas de organizar expresiones y estructuras jerárquicas.
8. Formas de parentizar expresiones
La cantidad de maneras de colocar paréntesis en una secuencia de n + 1 elementos, manteniendo asociaciones binarias válidas, es Cn.
Por ejemplo, una expresión con cuatro operandos tiene C3 = 5 parentizaciones posibles. Esto es relevante al comparar diferentes formas de evaluar una expresión.
9. Caminos que no cruzan una diagonal
Otra interpretación utiliza caminos sobre una cuadrícula. Un camino de (0, 0) a (n, n), compuesto por pasos hacia la derecha y hacia arriba, puede restringirse para no pasar por encima de la diagonal.
La cantidad de caminos que respetan esa condición es Cn. La restricción elimina los recorridos no válidos de la cuenta total.
10. Triangulaciones de polígonos
Un polígono convexo de n + 2 lados puede dividirse en triángulos mediante diagonales que no se cruzan de Cn formas.
Por ejemplo, un cuadrilátero tiene C2 = 2 triangulaciones y un pentágono tiene C3 = 5.
11. Relación con el coeficiente binomial
La fórmula de Catalan parte del coeficiente C(2n, n), que cuenta caminos o selecciones sin restricciones. El factor 1/(n + 1) refleja la proporción de configuraciones que cumplen el balance requerido.
12. Cálculo mediante factoriales
Para valores pequeños puede utilizarse la fórmula directa con factoriales. En aplicaciones reales, los factoriales crecen rápidamente y conviene controlar el tamaño de los números o emplear aritmética de precisión adecuada.
function factorial(n) {
let resultado = 1;
for (let i = 2; i <= n; i++) resultado *= i;
return resultado;
}
function catalanFormula(n) {
return factorial(2 * n) / (factorial(n + 1) * factorial(n));
}
console.log(catalanFormula(4)); // 1413. Generación de paréntesis válidos
Para construir todas las secuencias válidas se puede agregar un paréntesis de apertura cuando todavía quedan disponibles y uno de cierre solo cuando no rompe el balance.
function parentesisValidos(n) {
const resultado = [];
function generar(texto, abiertos, cerrados) {
if (texto.length === 2 * n) {
resultado.push(texto);
return;
}
if (abiertos < n) generar(texto + "(", abiertos + 1, cerrados);
if (cerrados < abiertos) generar(texto + ")", abiertos, cerrados + 1);
}
generar("", 0, 0);
return resultado;
}
console.log(parentesisValidos(3));La cantidad de elementos generados debe coincidir con Cn.
14. Simulación: números de Catalan
Indica un valor de n para calcular varios términos. La tabla compara la recurrencia con la fórmula directa y muestra una interpretación mediante paréntesis balanceados.
| n | Cn por recurrencia | Cn por fórmula |
|---|
15. Aplicaciones en informática
Los números de Catalan aparecen al contar árboles de expresión, formas de parentizar operaciones, estructuras jerárquicas, caminos restringidos y triangulaciones. Conocerlos permite identificar rápidamente una familia de problemas y elegir una recurrencia o una técnica de programación dinámica.
16. Resumen
Los números de Catalan comienzan con 1, 1, 2, 5, 14, 42, ... y cuentan estructuras que se dividen naturalmente en dos partes. Sus aplicaciones incluyen paréntesis balanceados, árboles binarios, parentizaciones, caminos restringidos y triangulaciones. La recurrencia de Catalan es una herramienta central para resolver estos problemas de conteo.