Problema de Catalan

En matemàtiques discretes, el problema de Catalan consistix en determinar el número de formes C_n en que es pot calcular el producte de n factors ordenats, realisant les operacions per parelles.

Per eixemple, si n=4, el producte abcd pot calcular-se de les següents cinc formes:

$[(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]$ .

Aixina, per a calcular el producte $2 \cdot 3 \cdot 4 \cdot 5$ es podria procedir:

Segons la primera forma: multiplicant primer 2·3=6, després efectuant 6·4=24 i finalment 24·5=120.
Segons la segona forma, primer es multiplica 3·4=12 i després es multiplica 2 pel resultat anterior per a obtindre 2·12=24. Finalment, el resultat obtingut es multiplica per 5 i s'obté 24·5=120.
Segons la tercera forma: multiplicant primer 2·3=6 i després multiplicant lo anterior pel resultat de 4·5=20 per a obtindre finalment 6·20=120.

El següent quadro ilustra els primers valors de C_n

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

Els valors de C_n es denominen números de Catalan en honor a Eugène Charles Catalan qui va presentar una solució a dit problema en 1838 en el Journal de Mathématiques.

Solució del problema

L'anàlisis del problema revela que l'últim pas involucra multiplicar dos números, els quals poden haver segut calculats de moltes formes. De eta forma, l'última etapa sempre té l'estructura

$(...) \cdot (...)$

Per eixemple, els 5 productes de la secció inicial serien (afegint paréntesis extres per a claritat):

$((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)$ .

En general, el primer grup (en blau) pot tindre des d'un fins a n-1 térmens (en l'eixemple, des d'1 fins a 3), mentres que el segon grup necessàriament tindrà els restants. Si representem per k el número de térmens del primer grup, el segon grup tindrà llavors n-k.

Pero el número de formes d'agrupar els k térmens de la primera part, és precisament C_k mentres que el número de formes d'agrupar els n-k térmens de la segona part és C_n-k.

D'esta forma, tenim la relació de recurrencia

(1) $C_{n} = C_{1} C_{n - 1} + C_{2} C_{n - 2} + C_{3} C_{n - 3} + \dots + C_{n - 2} C_{2} + C_{n - 1} C_{1}$ ,

és dir

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

Retornant a l'eixemple, el sumant $C_{1} C_{3} = 1 \cdot 2 = 2$ estaria contant les últimes dos formes de multiplicar, el sumant $C_{2} C_{2} = 1 \cdot 1 = 1$ referix a la tercera forma, mentres que $C_{3} C_{1} = 2 \cdot 1 = 2$ correspon a les dos primeres. La suma de les opcions possibles en cada pas és el total: C₄=2+1+2 = 5.

Finalment, observem que si es té només un factor, hi ha només una forma de realisar la multiplicació (puix l'únic factor és el resultat). En este punt de partida i la relació de recurrencia podem trobar els demés valors de C_n:

$C_{2} = C_{1} \cdot C_{1} = 1 \cdot 1 = 1$ (només hi ha 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$ ,
i aixina successivament.

També és possible obtindre una fòrmula directa per a calcular C_n a partir de la fòrmula recursiva (1) per mig de manipulacions més elaborades (per eixemple, relacionant-la en la série de números del problema de Euler sobre divisió de polígons o fent us de tècniques més recents com el método de funcions generadores, tenint com a resultat:

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

Vore també

Bibliografia

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

Este artícul conté una traducció derivada de «Problema de Catalan» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.