Problema de Catalan

En matemáticas discretas, el problema de Catalan consiste en determinar el número de formas C_n 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\cdot 3\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 C_n

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

Los valores de C_n 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

El 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 C_k mientras que el número de formas de agrupar los n-k términos de la segunda parte es C_n-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\cdot 2=2$ estaría contando las últimas dos formas de multiplicar, el sumando ${\color {Blue}C_{2}}{\color {Red}C_{2}}=1\cdot 1=1$ refiere a la tercera forma, mientras que ${\color {Blue}C_{3}}{\color {Red}C_{1}}=2\cdot 1=2$ corresponde a las dos primeras. La suma de las opciones posibles en cada paso es el total: C₄=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 C_n:

$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 C_n 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». 100 Great Problems of Elementary Mathematics. Their History and Solution (en inglés). Dover. pp. 23-27. ISBN 0486613488. Consultado el 5 de marzo de 2011.

Datos: Q4818975