Números de Catalan

Teoría

Los números de Catalan forman una de las sucesiones más importantes en combinatoria y aparecen en una variedad increíble de problemas de conteo. El $n$-ésimo número de Catalan, que escribimos como $C_n$, cuenta estructuras que puedes descomponer de forma recursiva de manera binaria.

La sucesión empieza así: $1, 1, 2, 5, 14, 42, 132, 429, \ldots$

Los números de Catalan cuentan:

• Cadenas de paréntesis balanceados con $n$ pares
• Árboles binarios con $n+1$ hojas
• Caminos de $(0,0)$ a $(n,n)$ que no cruzan la diagonal
• Formas de triangular un polígono convexo de $n+2$ lados
• Particiones no cruzadas del conjunto ${1, \ldots, n}$
• Árboles binarios completos con $n$ nodos internos

Fórmulas Clave

Forma cerrada: $$C_n = \frac{1}{n+1}\binom{2n}{n}$$

Forma alternativa: $$C_n = \binom{2n}{n} - \binom{2n}{n+1}$$

Recurrencia: $$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}, \quad C_0 = 1$$

Función generatriz: $$C(x) = \sum_{n=0}^{\infty} C_n x^n = \frac{1 - \sqrt{1-4x}}{2x}$$

Asintótica: $$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$

Primeros valores: | $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |-----|---|---|---|---|---|---|---|---| | $C_n$ | 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 |

Demostración

Demostración de la forma cerrada (Principio de reflexión):

La idea es contar caminos en una cuadrícula desde $(0,0)$ hasta $(2n, 0)$ usando pasos $U = (1,1)$ (arriba) y $D = (1,-1)$ (abajo), que nunca bajen del eje $x$.

Caminos totales: $\binom{2n}{n}$ (elige $n$ posiciones para $U$ de entre los $2n$ pasos).

Caminos malos: Son los caminos que tocan $y = -1$ en algún punto.

Para cada camino malo, busca el primer punto donde toca $y = -1$. Refleja todos los pasos después de ese punto respecto a la recta $y = -1$.

Esto crea un camino de $(0,0)$ a $(2n, -2)$: este tiene $n+1$ pasos hacia abajo y $n-1$ pasos hacia arriba.

Esta reflexión es una biyección entre los caminos malos y los caminos que llegan a $(2n, -2)$.

Caminos malos: $\binom{2n}{n+1}$

Caminos buenos: $$C_n = \binom{2n}{n} - \binom{2n}{n+1} = \binom{2n}{n} - \frac{n}{n+1}\binom{2n}{n} = \frac{1}{n+1}\binom{2n}{n}$$ $\square$

Demostración de la recurrencia:

Considera paréntesis balanceados con $n$ pares. Fíjate en el primer '(' y en el ')' que le corresponde.

Si el ')' correspondiente está en la posición $2k+2$ (para $k = 0, 1, \ldots, n-1$):

• Entre ellos: $k$ pares de paréntesis (tienen que estar balanceados).
• Después de ellos: $n-1-k$ pares (tienen que estar balanceados).

La primera parte la puedes elegir de $C_k$ formas. La segunda parte la puedes elegir de $C_{n-1-k}$ formas.

Total: $$C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$$ $\square$

Demostración con función generatriz:

A partir de la recurrencia $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$ para $n \geq 1$:

La convolución sugiere que $C(x) = 1 + x \cdot C(x)^2$ (el 1 es por $C_0$).

Al resolver: $xC^2 - C + 1 = 0$

$$C = \frac{1 \pm \sqrt{1-4x}}{2x}$$

Si tomas el signo menos (para que $C(0) = 1$): $$C(x) = \frac{1 - \sqrt{1-4x}}{2x}$$ $\square$