🔢 Números de Catalan

Un (n+2)-gono convexo puede dividirse en triángulos trazando n–1 diagonales que no se cruzan; el número de formas de hacerlo es Cₙ. Para un cuadrilátero (n = 2): dos triangulaciones. Para un pentágono (n = 3): cinco triangulaciones. La biyección con las cadenas de paréntesis funciona fijando una arista del polígono como la "raíz" y observando que el triángulo sobre esa arista divide el resto del polígono en dos polígonos más pequeños, reflejando la recurrencia de Catalan Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ Cₙ₋₁₋ᵢ. Las triangulaciones surgen en geometría computacional (triangulación óptima de polígonos, triangulación de Delaunay), en métodos numéricos (mallado de elementos finitos), y en el diseño de compiladores (árboles de sintaxis).

Un diagrama de cuerdas no cruzadas consta de 2n puntos en un círculo conectados por n cuerdas que no se intersectan. Las C₃ = 5 formas de conectar 6 puntos con 3 cuerdas no cruzadas son exactamente los cinco objetos de Catalan para n = 3. Estos diagramas aparecen en la predicción de estructuras secundarias de ARN (los pares de bases son cuerdas no cruzadas sobre la secuencia), en teoría de nudos (álgebras de Temperley–Lieb), y en probabilidad libre (las particiones no cruzadas definen los cumulantes libres de las distribuciones de probabilidad). El número de particiones no cruzadas de {1, …, n} también es Cₙ.

Los números de Catalan satisfacen la recurrencia C₀ = 1 y Cₙ₊₁ = Σᵢ₌₀ⁿ Cᵢ Cₙ₋ᵢ. Esta fórmula refleja la estructura de "dividir en la raíz" común a las cinco familias biyectivas: para una cadena de paréntesis, el paréntesis raíz "(" se cierra en alguna posición, dividiendo la cadena en dos subcadenas balanceadas independientes de longitudes 2i y 2(n–i). Sumar sobre todas las posiciones de división da la recurrencia. La función generadora C(x) = Σ Cₙ xⁿ satisface x C(x)² – C(x) + 1 = 0, con solución C(x) = (1 – √(1 – 4x)) / (2x).

La razón unificadora es que todas las familias de Catalan comparten la misma estructura recursiva: un objeto de tamaño n puede construirse de manera única eligiendo una "raíz" que divide los datos restantes en dos subobjetos independientes de tamaños i y n–1–i (o similar), sumando sobre todas las divisiones. Esto es exactamente la recurrencia de Catalan. Las biyecciones entre estas familias suelen ser elegantes: un "(" en una cadena de paréntesis se convierte en una arista de hijo izquierdo en un árbol binario y en un paso hacia arriba en un camino de Dyck, así que los datos combinatorios son literalmente el mismo objeto con tres disfraces distintos.

Los números de Catalan crecen exponencialmente: según la aproximación de Stirling, Cₙ ~ 4ⁿ / (n^(3/2) √π). La razón Cₙ₊₁/Cₙ = 2(2n+1)/(n+2) converge a 4, así que cada número de Catalan sucesivo es aproximadamente cuatro veces el anterior. C₁₀ = 16,796; C₂₀ ≈ 6.56 × 10¹⁰; C₅₀ ≈ 1.37 × 10²⁸. Para n = 8 (el máximo en esta simulación) C₈ = 1,430 — suficiente para dibujar todos los objetos individualmente. Más allá de n ≈ 10 se vuelve poco práctico enumerarlos todos y debe usarse muestreo aleatorio.

Un árbol binario completo es un árbol con raíz en el que cada nodo interno tiene exactamente dos hijos (nunca uno). El número de árboles binarios completos con n+1 hojas es Cₙ. Para n = 3: C₃ = 5 árboles con 4 hojas. La biyección con las cadenas de paréntesis envía cada hoja a ")" y cada nodo interno a "(", leyendo el árbol de izquierda a derecha en preorden. Los árboles binarios completos son la estructura del análisis de expresiones, la codificación de Huffman y el árbol de Stern–Brocot para fracciones. También cuentan el número de formas de parentetizar completamente un producto de n+1 factores — la formulación original del problema por Euler (1751).

Euler contó las triangulaciones de polígonos en 1751 y encontró la sucesión 1, 2, 5, 14, 42, … pero no tenía la forma cerrada. Segner encontró la recurrencia en 1758. El matemático belga Eugène Charles Catalan dio la fórmula cerrada Cₙ = (2n)!/((n+1)!n!) en 1838, y la sucesión ahora lleva su nombre. Sin embargo, la sucesión había sido descubierta incluso antes por el matemático chino Ming Antu alrededor de 1730 en relación con fórmulas de expansión trigonométrica. La historia de sus descubrimientos simultáneos e independientes es un vívido ejemplo de la universalidad matemática.

Los números de Catalan aparecen en informática (número de permutaciones ordenables con pila, número de árboles binarios de búsqueda distintos con n claves, número de funciones booleanas monótonas en 2 variables), bioinformática (estructuras secundarias de ARN contadas por su estructura de paréntesis no cruzados), física (diagramas de Feynman no cruzados en teoría cuántica de campos planar, momentos de la ley del semicírculo de Wigner en teoría de matrices aleatorias), y lingüística (número de árboles de análisis para una gramática libre de contexto ambigua con una estructura de reglas específica). El libro "Catalan Numbers" de Stanley (2015) enumera 214 interpretaciones combinatorias distintas.