Polígonos convexos: triangulaciones y el número de Catalan

Triangulaciones de un polígono convexo

Una triangulación de un polígono convexo de $n$ lados (un $n$-ágono) es una descomposición de su interior en triángulos no solapados usando únicamente diagonales que no se cruzan dentro del polígono. Los lados del polígono pueden utilizarse, pero las diagonales deben ser internas.

Para empezar, fijemos un lado del polígono — digamos el lado $\overline{v_1 v_n}$ — y razonemos recursivamente. Cualquier triángulo que contenga la arista $\overline{v_1 v_n}$ tiene un tercer vértice $v_k$ con $2 \leq k \leq n-1$. Al escoger $v_k$, la triangulación del polígono original se reduce a triangular el subpolígono $v_1 v_2 \cdots v_k$ (de $k$ lados) y el subpolígono $v_k v_{k+1} \cdots v_n$ (de $n-k+1$ lados).

Sea $T_n$ el número de triangulaciones de un $n$-ágono convexo. Entonces $T_2 = 1$ (un segmento, trivial), $T_3 = 1$ (el triángulo ya es una triangulación), y la recurrencia es: $T_n = \sum_{k=2}^{n-1} T_k \cdot T_{n-k+1}$ para $n \geq 3$.

Calculando los primeros valores: $T_3 = 1$, $T_4 = T_2 T_3 + T_3 T_2 = 1 + 1 = 2$, $T_5 = T_2 T_4 + T_3 T_3 + T_4 T_2 = 2 + 1 + 2 = 5$, $T_6 = 14$. Reconocemos $1, 1, 2, 5, 14, \ldots$: ¡son los números de Catalan!

Más precisamente, $T_n = C_{n-2}$ donde $C_k$ es el $k$-ésimo número de Catalan. Para $n = 3$: $C_1 = 1$; para $n = 4$: $C_2 = 2$; para $n = 5$: $C_3 = 5$; para $n = 6$: $C_4 = 14$.

El número de Catalan: fórmula y recurrencia

Los números de Catalan $C_0, C_1, C_2, \ldots$ se definen por la recurrencia $C_0 = 1$ y $C_{n+1} = \sum_{k=0}^{n} C_k C_{n-k}$ para $n \geq 0$.

La fórmula explícita es: $C_n = \frac{1}{n+1}\binom{2n}{n}$.

Los primeros valores son $C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42, C_6 = 132$.

Derivación de la fórmula: Usando funciones generatrices, sea $f(x) = \sum_{n=0}^{\infty} C_n x^n$. La recurrencia da $f(x) = 1 + x f(x)^2$, ecuación cuadrática en $f$ con solución $f(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$. Expandiendo con la fórmula binomial generalizada $\sqrt{1-4x} = \sum_{n=0}^{\infty} \binom{1/2}{n}(-4x)^n$, se obtiene el coeficiente $[x^n]f(x) = \frac{1}{n+1}\binom{2n}{n}$.

Fórmula alternativa: $C_n = \binom{2n}{n} - \binom{2n}{n+1}$. Esta representación como diferencia de coeficientes binomiales se usa frecuentemente en las demostraciones combinatorias mediante caminos celosía.

Otros objetos contados por el número de Catalan

Una de las maravillas de los números de Catalan es que cuentan decenas de familias combinatorias distintas. Las más importantes para olimpiadas:

Caminos de Dyck: Un camino de Dyck de semilongitud $n$ es una trayectoria en $\mathbb{Z}^2$ desde $(0,0)$ hasta $(2n,0)$ usando pasos $(+1,+1)$ y $(+1,-1)$ que nunca baja por debajo del eje $x$. El número de tales caminos es $C_n$.

Parentesizaciones: El número de maneras de colocar paréntesis en el producto de $n+1$ factores (para determinar el orden de las operaciones) es $C_n$. Por ejemplo, para 4 factores $abcd$: $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, $a(b(cd))$ — son $C_3 = 5$ maneras.

Árboles binarios completos: El número de árboles binarios completos (donde cada nodo interno tiene exactamente 2 hijos) con $n+1$ hojas es $C_n$.

Secuencias de paréntesis balanceados: El número de secuencias de $n$ pares de paréntesis correctamente balanceadas es $C_n$. Para $n=3$: $()()()$, $(())()$, $()(())$, $((()))$, $(()())$ — son $C_3 = 5$.

Triangulaciones: Como vimos, el número de triangulaciones de un $(n+2)$-ágono convexo es $C_n$.

La biyección más útil entre estos objetos es entre triangulaciones y caminos de Dyck: a cada diagonal de la triangulación se le asocia un paso "arriba" o "abajo" del camino. Este vínculo permite trasladar resultados entre los distintos contextos.

Propiedades y cálculo de $C_n$ en competencias

En olimpiadas, los números de Catalan aparecen cuando se cuentan estructuras con la propiedad de "no cruzarse" o "mantenerse sobre un umbral". Saber reconocerlos es clave.

Señales de Catalan: El enunciado involucra triangulaciones de polígonos; parentesizaciones; caminos que no cruzan una línea; estructuras anidadas (paréntesis, corchetes); o la recurrencia de convolución $a_n = \sum_{k} a_k a_{n-k}$.

Cálculo rápido: Para $n$ pequeño (hasta $n = 7$ o $8$), conviene calcular $C_n$ directamente con la recurrencia $C_{n+1} = \frac{2(2n+1)}{n+2} C_n$, que se obtiene de la fórmula explícita:

$C_{n+1} = \frac{1}{n+2}\binom{2n+2}{n+1} = \frac{(2n+2)!}{(n+1)!(n+2)!} = \frac{(2n+2)(2n+1)}{(n+2)(n+1)} \cdot \frac{(2n)!}{n! \cdot n!} \cdot \frac{1}{n+1} \cdot \frac{n+1}{1} = \frac{2(2n+1)}{n+2} C_n$.

Divisibilidad: $C_n$ es impar si y solo si $n = 2^k - 1$ para algún $k \geq 0$ (es decir, $n = 0, 1, 3, 7, 15, \ldots$). Esta propiedad de paridad se usa en problemas de módulo.

Cota asintótica: $C_n \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}$, lo que indica que $C_n$ crece aproximadamente como $4^n / n^{3/2}$.

Problema trabajado: triangulaciones con restricciones

Problema (estilo olímpico): Sea $P$ un hexágono convexo cuyos vértices se etiquetan $v_1, v_2, v_3, v_4, v_5, v_6$ en orden. ¿Cuántas triangulaciones de $P$ no usan la diagonal $\overline{v_1 v_4}$?

Solución: El total de triangulaciones de un hexágono es $C_4 = 14$. Contamos las que sí usan $\overline{v_1 v_4}$: si fijamos $\overline{v_1 v_4}$ como diagonal, el hexágono se divide en dos cuadriláteros: $v_1 v_2 v_3 v_4$ y $v_1 v_4 v_5 v_6$. Cada cuadrilátero tiene $C_2 = 2$ triangulaciones independientes, así que hay $2 \times 2 = 4$ triangulaciones del hexágono que contienen $\overline{v_1 v_4}$.

Por complemento, el número de triangulaciones que no usan $\overline{v_1 v_4}$ es $14 - 4 = \mathbf{10}$.

Generalización: Para un $n$-ágono, el número de triangulaciones que contienen una diagonal fija $\overline{v_i v_j}$ (donde $j - i = k$ con $2 \leq k \leq n-2$) es $C_{k-1} \cdot C_{n-k-1}$ (producto de los Catalan de los dos subpolígonos creados). El total de triangulaciones que contienen esa diagonal es $T_{k+1} \cdot T_{n-k+1} = C_{k-1} \cdot C_{n-k-1}$.

Conclusión: La idea de "contar por complemento" o "contar las que contienen un elemento fijo y restar" es una herramienta estándar para problemas de Catalan. La clave es siempre identificar cómo una diagonal fija divide el polígono en subpolígonos más pequeños.

Conexión con caminos reticulares y la reflexión de Lindström

Una de las demostraciones más elegantes de $C_n = \frac{1}{n+1}\binom{2n}{n}$ usa el método de reflexión para caminos en el plano entero.

Los caminos desde $(0,0)$ hasta $(n,n)$ usando pasos $\to$ y $\uparrow$ son $\binom{2n}{n}$ en total. Los caminos que cruzan la diagonal $y = x+1$ (es decir, que en algún momento tienen $y > x$) son caminos "malos". Por reflexión respecto a $y = x + 1$, cada camino malo corresponde biyectivamente a un camino desde $(-1, 1)$ hasta $(n,n)$, que equivale a uno desde $(0,0)$ hasta $(n+1, n-1)$, de los cuales hay $\binom{2n}{n-1}$.

Los caminos "buenos" (que no cruzan $y = x+1$, es decir que siempre tienen $y \leq x$) son: $\binom{2n}{n} - \binom{2n}{n-1} = \binom{2n}{n} - \binom{2n}{n+1} = C_n$.

Esta demostración geométrica ilustra la conexión profunda entre caminos reticulares y los números de Catalan. La reflexión de Lindström–Gessel–Viennot (LGV) es la generalización multivariable de este argumento, usada en combinatoria avanzada para calcular determinantes de matrices de conteo de caminos.

Aplicación a olimpiadas: La interpretación de caminos es útil para resolver preguntas como "¿cuántos caminos de $(0,0)$ a $(n,n)$ no pasan por encima de la diagonal?". La respuesta es siempre un número de Catalan, obtenido directamente de la fórmula o del argumento de reflexión.