Números combinatorios clásicos · Definición

Número de Catalan

combinatoria enumerativanúmeros combinatorios clásicos

Los números de Catalan aparecen en problemas de conteo muy distintos entre sí. Su estudio se apoya en recurrencias y en un argumento de reflexión que relaciona caminos prohibidos con caminos libres.

Definición

El número de Catalan \(C_n\) cuenta, entre otras muchas estructuras, las formas de triangular un polígono convexo de \(n+2\) lados o los caminos de Dyck de longitud \(2n\).

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

Los números de Catalan satisfacen la recurrencia \(C_0=1\) y \(C_{n+1}=\sum_{k=0}^{n} C_k C_{n-k}\), y su generatriz ordinaria \(C(x)\) cumple la ecuación cuadrática \(xC(x)^2-C(x)+1=0\). Por el principio de reflexión, el número de caminos de Dyck de longitud \(2n\) que no descienden por debajo del eje coincide con \(\binom{2n}{n}-\binom{2n}{n+1}\), lo que da la fórmula cerrada.

Para \(n=3\), la fórmula da \(C_3=\frac{1}{4}\binom{6}{3}=5\). Este valor coincide con el número de formas de asociar cuatro factores en un producto \(x_1x_2x_3x_4\) o de triangular un pentágono convexo.

Un error típico es confundir \(C_n\) con \(\binom{2n}{n}\): para \(n=3\) el coeficiente binomial vale \(20\), mientras que \(C_3=5\). Otro error frecuente es olvidar el factor \(\frac{1}{n+1}\) al aplicar la fórmula cerrada.

Para pensar

¿Por qué la fórmula \(\binom{2n}{n}\) sin restricción no da directamente \(C_n\)?

Porque cuenta también los caminos que bajan por debajo del eje; el principio de reflexión resta los \(\binom{2n}{n+1}\) que lo hacen, dejando \(C_n\).

Ejercicios 10

  1. ¿Cuál es el valor de \(C_2\)?
  2. ¿Cuál es el valor de \(C_0\)?
  3. ¿Cuántas triangulaciones distintas admite un hexágono convexo, trazando diagonales que no se cruzan en su interior?
  4. ¿De cuántas formas distintas se pueden asociar los paréntesis en el producto \(x_1x_2x_3\)?
  5. ¿Cuál de las siguientes expresiones es igual a \(C_n\)?
  6. Calcula \(C_4\) usando la recurrencia \(C_{n+1}=\sum_{k=0}^{n} C_k C_{n-k}\) con \(C_0=1\), \(C_1=1\), \(C_2=2\), \(C_3=5\).
  7. Calcula \(\binom{10}{5}\) y úsalo para hallar \(C_5\) mediante \(C_n=\frac{1}{n+1}\binom{2n}{n}\).
  8. Calcula \(\frac{C_{n+1}}{C_n}\) para \(n=3\) a partir de \(C_3=5\) y \(C_4=14\).
  9. ¿Cuántos caminos de Dyck de longitud 6 existen?
  10. Usando la generatriz \(xC(x)^2-C(x)+1=0\), demuestra que \(C_4=14\) a partir de \(C_0=1\), \(C_1=1\), \(C_2=2\), \(C_3=5\), y verifica el resultado con la fórmula cerrada.

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.