Problema de Catalan

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En matemáticas discretas, el problema de Catalan consiste en determinar el número de formas Cn en que se puede calcular el producto de n factores ordenados, realizando las operaciones por parejas.

Por ejemplo, si n=4, el producto abcd puede calcularse de las siguientes cinco formas:

  • [(a\cdot b)\cdot c]\cdot d,
  •  [a\cdot(b\cdot c)]\cdot d,
  •  (a\cdot b)\cdot(c\cdot d),
  • a\cdot[b\cdot(c\cdot d)],
  • a\cdot[(b\cdot c)\cdot d].

Así, para calcular el producto 2\cdot3\cdot 4\cdot 5 se podría proceder:

  • Según la primera forma: multiplicando primero 2·3=6, luego efectuando 6·4=24 y finalmente 24·5=120.
  • Según la segunda forma, primero se multiplica 3·4=12 y luego se multiplica 2 por el resultado anterior para obtener 2·12=24. Finalmente, el resultado obtenido se multiplica por 5 y se obtiene 24·5=120.
  • Según la tercera forma: multiplicando primero 2·3=6 y luego multiplicando lo anterior por el resultado de 4·5=20 para obtener finalmente 6·20=120.

El siguiente cuadro ilustra los primeros valores de Cn

n 1 2 3 4 5 6 7 8 9 10
Cn 1 1 2 5 14 42 132 429 1430 4862

Los valores de Cn se denominan números de Catalan en honor a Eugène Charles Catalan quien presentó una solución a dicho problema en 1838 en el Journal de Mathématiques.

Solución del problema[editar]

Análisis del problema revela que el último paso involucra multiplicar dos números, los cuales pueden haber sido calculados de muchas formas. De eta forma, la última etapa siempre tiene la estructura

{\color{Blue}(...)}\cdot{\color{Red}(...)}

Por ejemplo, los 5 productos de la sección inicial serían (añadiendo paréntesis extras para claridad):

  • {\color{Blue}((a\cdot b)\cdot c)}\cdot {\color{Red}(d)},
  • {\color{Blue} (a\cdot(b\cdot c))}\cdot {\color{Red}(d)},
  • {\color{Blue} (a\cdot b)}\cdot{\color{Red}(c\cdot d)},
  • {\color{Blue}(a)}\cdot{\color{Red}(b\cdot(c\cdot d))},
  • {\color{Blue}(a)}\cdot{\color{Red}((b\cdot c)\cdot d)}.

En general, el primer grupo (en azul) puede tener desde uno hasta n-1 términos (en el ejemplo, desde 1 hasta 3), mientras que el segundo grupo necesariamente tendrá los restantes. Si representamos por k el número de términos del primer grupo, el segundo grupo tendrá entonces n-k.

Pero el número de formas de agrupar los k términos de la primera parte, es precisamente Ck mientras que el número de formas de agrupar los n-k términos de la segunda parte es Cn-k.

De esta forma, tenemos la relación de recurrencia

(1)C_n = {\color{Blue}C_1}{\color{Red}C_{n-1}} +{\color{Blue}C_2}{\color{Red}C_{n-2}} + {\color{Blue}C_3}{\color{Red}C_{n-3}} + \cdots + {\color{Blue}C_{n-2}}{\color{Red}C_2} + {\color{Blue}C_{n-1}}{\color{Red}C_1},

es decir

C_n = \sum_{k=1}^{n-1} C_k C_{n-k}.

Regresando al ejemplo, el sumando {\color{Blue}C_1}{\color{Red}C_3}=1\cdot2=2 estaría contando las últimas dos formas de multiplicar, el sumando {\color{Blue}C_2}{\color{Red}C_2}=1\cdot1=1 refiere a la tercera forma, mientras que {\color{Blue}C_3}{\color{Red}C_1}=2\cdot1=2 corresponde a las dos primeras. La suma de las opciones posibles en cada paso es el total: C4=2+1+2 = 5.

Finalmente, observamos que si se tiene sólo un factor, hay sólo una forma de realizar la multiplicación (pues el único factor es el resultado). Con este punto de partida y la relación de recurrencia podemos hallar los demás valores de Cn:

  • C_2 = C_1\cdot C_1 = 1\cdot 1 = 1 (sólo hay una forma de multiplicar dos números),
  • C_3 = C_1 \cdot C_2 + C_2\cdot C_1 = 1\cdot 1 + 1\cdot 1 = 2,
  • C_4 = C_1 \cdot C_3+ C_2\cdot C_2+C_3\cdot C_1 = 1\cdot 2 + 1\cdot 1 + 2\cdot 1 = 5,
  • C_5 = C_1 \cdot C_4+ C_2\cdot C_3+C_3\cdot C_2+ C_4\cdot C_1 = 1\cdot 5 + 1\cdot 2 + 2\cdot 1 + 5\cdot 1 = 14,
  • C_6 = C_1 \cdot C_5+ C_2\cdot C_4+C_3\cdot C_3+ C_4\cdot C_2 + C_5\cdot C_1 = 14 +  5 +  4 + 5 + 14 = 42,
  • y así sucesivamente.

También es posible obtener una fórmula directa para calcular Cn a partir de la fórmula recursiva (1) mediante manipulaciones más elaboradas (por ejemplo, relacionándola con la serie de números del problema de Euler sobre división de polígonos o haciendo uso de técnicas más recientes como el método de funciones generadoras, teniendo como resultado:

C_n = \frac{1}{n+1} {2n \choose n}.

Véase también[editar]

Bibliografía[editar]

  • Dörrie, Heinrich (1965). «Capítulo 21: Euler's Problem of Polygon Division» (en Inglés). 100 Great Problems of Elementary Mathematics. Their History and Solution. Dover. pp. 23-27. ISBN 0486613488.