La expresión Cn = C(2n,n)/(n+1).
Los números de Catalan, que escribimos como $C_n$, forman una sucesión de números naturales que aparecen por todos lados en la combinatoria. Te dan la solución a un montón de problemas de conteo que tienen estructuras recursivas, como contar cuántas expresiones de paréntesis válidas hay de longitud $2n$, el número de árboles binarios completos con $n+1$ hojas, o de cuántas formas puedes triangular un polígono convexo de $n+2$ lados. Aunque puedes definir la sucesión de forma recursiva, la Fórmula de los Números de Catalan te da una expresión cerrada muy potente usando coeficientes binomiales, lo que te permite calcularlos directamente sin tener que pasar por todos los términos anteriores.
Esta fórmula es clave en matemáticas de competencia (como el AIME y la USAMO) porque convierte problemas complejos de conteo estructural en simples manipulaciones algebraicas. La mejor forma de entender la intuición detrás de la fórmula es con la interpretación de "Caminos en una Cuadrícula". Si te fijas en los caminos en una cuadrícula que van de $(0,0)$ a $(n,n)$ y que no suben más allá de la línea $y=x$, el número de Catalan $C_n$ representa cuántos de estos caminos "válidos" existen. La fórmula sale de tomar el total de caminos monótonos y restarle los caminos "inválidos" (los que cruzan la diagonal), usando una técnica que se conoce como el Principio de Reflexión.
La expresión cerrada principal para el $n$-ésimo número de Catalan es: $$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$$ para $n \ge 0$. Los primeros números de Catalan son $1, 1, 2, 5, 14, 42, 132, \dots$
Otra forma equivalente que suele ser muy útil para hacer cálculos, y que sale del principio de reflexión, es: $$C_n = \binom{2n}{n} - \binom{2n}{n-1}$$
La sucesión también cumple con la relación de recurrencia fundamental (la recurrencia de Segner): $$C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$$ con el caso base $C_0 = 1$.
Aquí tienes la demostración de la fórmula $C_n = \frac{1}{n+1}\binom{2n}{n}$ usando el André's Reflection Principle aplicado a caminos en cuadrículas.
Paso 1: Planteamiento del problema Imagina que $C_n$ es el número de "caminos de Dyck" en un plano cartesiano. Un camino de Dyck es un camino de $(0,0)$ a