Números de Catalan

El problema de los paréntesis

¿De cuántas maneras se pueden colocar $n$ pares de paréntesis de forma que la secuencia resultante sea válida? Una secuencia es válida si en todo prefijo el número de paréntesis abiertos es mayor o igual al de cerrados, y al final son iguales.

Para $n=1$: solo "()". Para $n=2$: "(())" y "()()". Para $n=3$: "((())) ", "(()()) ", "(())()", "()(())", "()()()". Son 5 secuencias.

La secuencia $1, 1, 2, 5, 14, 42, 132, \ldots$ se llama sucesión de Catalan. Aparece con sorprendente frecuencia en combinatoria: triangulaciones de polígonos, árboles binarios, caminos en cuadrículas, el problema de la montaña rusa. Cuando cuentes algo y obtengas $1, 2, 5, 14$..., es muy probable que estés contando objetos de Catalan.

La fórmula cerrada

El $n$-ésimo número de Catalan ($n \ge 0$) es:

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\, n!}$$

Verificación: $C_0 = 1$, $C_1 = 1$, $C_2 = 2$, $C_3 = 5$, $C_4 = 14$. La fórmula combina el coeficiente binomial central $\binom{2n}{n}$ dividido por $n+1$.

Derivación (estrategia): consideramos todos los caminos desde $(0,0)$ hasta $(n,n)$ en una cuadrícula usando pasos derecha (D) y arriba (A). Hay $\binom{2n}{n}$ caminos en total. Los caminos válidos son aquellos que nunca suben por encima de la diagonal $y=x$ — equivalen a secuencias de paréntesis válidas. Contando los caminos inválidos por reflexión (el "truco de la reflexión de André"), se obtiene que hay $\binom{2n}{n+1}$ caminos inválidos. Por lo tanto:

$$C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}$$

Cuatro interpretaciones del mismo número

Los números de Catalan cuentan varios tipos de objetos aparentemente distintos; todos dan la misma sucesión. Conocer varias interpretaciones permite reconocerlos rápidamente en competencia.

Secuencias de paréntesis: $C_n$ cuenta las secuencias de $n$ pares de paréntesis bien formadas. Es la interpretación canónica.

Caminos de Dyck: $C_n$ cuenta los caminos desde $(0,0)$ hasta $(2n, 0)$ usando pasos $(+1, +1)$ y $(+1, -1)$ que nunca bajan de la línea $y = 0$. Son los caminos de una "bolsa de valores" que nunca va al rojo.

Triangulaciones: $C_n$ cuenta el número de triangulaciones de un polígono convexo de $n+2$ vértices (las maneras de dividirlo en triángulos con diagonales no cruzadas). Para un hexágono ($n=4$) hay $C_4 = 14$ triangulaciones.

Árboles binarios completos: $C_n$ cuenta el número de árboles binarios con $n+1$ hojas (o equivalentemente, con $n$ nodos internos). Esta interpretación conecta con la estructura de expresiones aritméticas.

La recurrencia de Catalan

Los números de Catalan satisfacen la recurrencia:

$$C_n = \sum_{k=0}^{n-1} C_k \cdot C_{n-1-k}, \quad C_0 = 1$$

Derivación para secuencias de paréntesis: en toda secuencia válida de $n$ pares, el paréntesis abierto inicial tiene un paréntesis cerrado correspondiente en alguna posición $2k+2$ ($k = 0, 1, \ldots, n-1$). La parte entre estos dos paréntesis forma una secuencia válida de $k$ pares ($C_k$ formas), y la parte posterior forma una secuencia válida de $n-1-k$ pares ($C_{n-1-k}$ formas). Sumando sobre $k$:

Esta recurrencia permite calcular $C_n$ iterativamente: $C_0=1$, $C_1=C_0C_0=1$, $C_2=C_0C_1+C_1C_0=2$, $C_3=C_0C_2+C_1C_1+C_2C_0=5$. Más lento que la fórmula cerrada, pero revela la estructura recursiva subyacente.

El problema de la votación (conexión olímpica)

Problema: En una votación, el candidato A obtiene $n$ votos y el candidato B obtiene $n$ votos. ¿Cuántas maneras hay de escrutar los votos de modo que A nunca vaya perdiendo en el conteo (es decir, en todo momento parcial, los votos de A son mayores o iguales a los de B)?

Esta situación es exactamente un camino de Dyck de longitud $2n$: cada voto para A es un paso $(+1, +1)$ y cada voto para B es un paso $(+1, -1)$. Las condiciones del problema exigen que el camino nunca baje de $y=0$.

La respuesta es $C_n = \frac{1}{n+1}\binom{2n}{n}$. Para $n = 3$: $C_3 = 5$ maneras de escrutar 3 votos para A y 3 para B sin que B tome la delantera.

Conexión con la ONEM: en competencias regionales suele aparecer esta pregunta disfrazada de "escaleras", "monedas" o "apilamiento de bloques". Reconocer el patrón de Catalan inmediatamente ahorra tiempo precioso.