Cuenta formas válidas de poner paréntesis.
Una secuencia de paréntesis se considera balanceada (o válida) si tiene $n$ paréntesis de apertura ( y $n$ paréntesis de cierre ) de tal forma que, en cada prefijo de la secuencia, el número de paréntesis de apertura sea mayor o igual al número de paréntesis de cierre. La longitud total de esta secuencia es $2n$. Este problema es la interpretación combinatoria fundamental de los números de Catalan.
Este concepto aparece por todos lados en las matemáticas de competencia porque sirve como una biyección para muchísimas otras estructuras combinatorias. Por ejemplo, contar paréntesis balanceados de longitud $2n$ es equivalente a contar caminos de Dyck de longitud $2n$ (caminos en una cuadrícula de $(0,0)$ a $(2n,0)$ que nunca bajan del eje x), contar el número de formas de triangular un polígono convexo de $n+2$ vértices, o contar el número de árboles binarios distintos con $n$ nodos. Entender los paréntesis balanceados te da las herramientas necesarias para resolver un montón de problemas que involucran estructuras recursivas y restricciones de no cruce.
La intuición clave depende de la "propiedad del prefijo". Si le asignas el valor $+1$ a ( y $-1$ a ), una secuencia está balanceada si y solo si la suma acumulada de estos valores nunca se vuelve negativa y la suma final es exactamente cero. Esto convierte el problema en uno de contar caminos en una cuadrícula, que puedes resolver de forma elegante usando el Reflection Principle para restar los caminos "inválidos" del total de permutaciones posibles.
El número de secuencias de paréntesis balanceados que tienen $n$ pares de paréntesis está dado por el $n$-ésimo número de Catalan, que escribimos como $C_n$.
Fórmula Explícita: $$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$$
Fórmula Recursiva: $$C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$$ con el caso base $C_0 = 1$.
Aproximación Asintótica: $$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$
Permutaciones Totales vs. Permutaciones Válidas: El número de secuencias válidas es el total de formas de acomodar $n$ paréntesis izquierdos y $n$ derechos, menos el número de acomodos inválidos: $$C_n = \binom{2n}{n} - \binom{2n}{n-1}$$
Teorema: El número de secuencias de paréntesis balanceados de longitud $2n$ es $C_n = \frac{1}{n+1}\binom{2n}{n}$.
Demostración (usando el Reflection Principle de André):
Imagina la secuencia de paréntesis como un camino en el plano cartesiano que empieza en $(0,0)$. Por cada carácter en la secuencia, te mueves 1 unidad a la derecha. Si el carácter es (, subes 1 unidad ($+1$ en $y$). Si el carácter es ), bajas 1 unidad ($-1$ en $y$).
Caminos Totales: Una secuencia tiene longitud $2n$ con $n$ pasos hacia arriba y $n$ hacia abajo. El camino tiene que terminar en las coordenadas $(2n, 0)$. El número total de estos caminos (sin importar si están balanceados o no) es la cantidad de formas de elegir $n$ posiciones para los pasos hacia arriba de entre los $2n$ pasos totales: $$N_{\text{total}} = \binom{2n}{n}$$
La Condición de Invalidez: Un camino representa una secuencia balanceada si y solo si nunca baja del eje x. Por lo tanto, un camino "inválido" es uno que empieza en $(0,0)$, termina en $(2n, 0)$, pero toca o cruza la línea $y = -1$ en algún punto.
Principio de Reflexión: Toma cualquier camino inválido. Sea $K$ el primer punto donde el camino toca la línea $y = -1$. Vamos a definir un nuevo camino reflejando la parte del camino original que está después del punto $K$ respecto a la línea $y = -1$.
Como el camino original terminaba en $y=0$ y la línea de reflexión es $y=-1$, el nuevo punto final estará en $y = -2$. Así, cada camino inválido se mapea a un único camino que va de $(0,0)$ a $(2n, -2)$. Al revés, cualquier camino que vaya de $(0,0)$ a $(2n, -2)$ tiene que cruzar $y=-1$ forzosamente, y puedes reflejarlo de vuelta para formar un único camino inválido que termine en $(2n, 0)$. Esto establece una biyección.
Contando Caminos Inválidos: Un camino de $(0,0)$ a $(2n, -2)$ tiene $2n$ pasos. Si $u$ es el número de pasos hacia arriba y $d$ el de pasos hacia abajo, tienes este sistema: $$u + d = 2n$$ $$u - d = -2$$ Al resolver esto obtienes $2u = 2n - 2 \implies u = n-1$. Entonces, el número de caminos inválidos es la cantidad de formas de elegir $n-1$ pasos hacia arriba: $$N_{\text{invalid}} = \binom{2n}{n-1}$$
Cálculo Final: El número de caminos válidos es el total de caminos menos los caminos inválidos: $$C_n = \binom{2n}{n} - \binom{2n}{n-1}$$
Desarrollando los coeficientes binomiales: $$C_n = \frac{(2n)!}{n!n!} - \frac{(2n)!}{(n-1)!(n+1)!}$$
Factoriza $\frac{(2n)!}{n!(n+1)!}$: $$C_n = \frac{(2n)!}{n!(n+1)!} \left[ (n+1) - n \right]$$ $$C_n = \frac{(2n)!}{n!(n+1)!} \cdot 1$$ $$C_n = \frac{1}{n+1} \binom{2n}{n}$$
$\square$