Los números de (Euler)-Catalan

Bolet´ın de la Asociaci´on Matem´atica Venezolana, Vol. X, No. 1 (2003) 43 Los N´umeros de (Euler)-Catalan. Mercedes H. Rosas A Rafa´el S´anchez Lamoneda Fue el gran Leonhard Euler (1707–1783) la primera persona en calcular los n´umeros de Catalan. Esto nos lo relata su contempor´aneo Johann Segner (1704- 1777) en su art´ıculo: Enumeratio modorum, quibus figurae planae rectilineae per diagonales dividuntur in triangula, Novi Commentarii Acad. Sci. Petropolitanae, 7 (1758-59) 203-209. Segner nos cuenta que los primeros valores para los n´umeros de Catalan le fueron comunicados por Euler, quien, sin embargo, le escondi´o la t´ecnica que utiliz´o para calcularlos. “quos numeros mecum benevolus communicavit summus Eulerus; modo, quo eos reperit, atque progressionis ordine, celatis.” En el trabajo mencionado Segner obtiene la recurrencia de Catalan, tal como la presentamos en la primera secci´on de este art´ıculo. En un art´ıculo posterior, y del mismo t´ıtulo, Segner conjetur´o correctamente la f´ormula cerrada para los n´umeros de Catalan, m´as no logr´o demostrarla. Euler responde a los art´ıculos de Segner sacando sus garras. En su “Summarium, Novi Comentarii academiae scientiarum Petropolitanae 7, (1758/59), 13–15.” Reimpreso en su “Opera Omnia (1) 26 (1953), xvi-xviii,” Euler calcula la funci´on generatriz de Catalan, y de ella deriva la f´ormula cerrada de Catalan utilizando las ideas descritas en la secci´on 3 de este trabajo. La genialidad de Euler para atacar este problema, as´ı como sus famosos trabajos en la teor´ıa de particiones, inician el estudio de las funciones generatrices y con ´el una larga y fruct´ıfera uni´on entre el an´alisis y la combinatoria, [1]. Alrededor de un siglo despu´es Eugene Catalan (1814-1894), volver´a a calcular el n´umero de maneras de triangular un pol´ıgono. En su memoria, los n´umeros de Catalan llevan hoy en dia su nombre. En su p´agina en la internet http://www-math.mit.edu/~rstan/ec, Richard Stanley nos reta con 95 familias de objetos enumerados por los n´umeros de Catalan. Las primeras 66 familias constituyen el famoso problema 6.19 de su libro EC2 [5]. Las restantes 29 (en la versi´on del 14 de Abril del 2003) conforman el “Catalan Addendum” que es actualizado frecuentemente. Mi objetivo es recorrer junto al lector uno de los cap´ıtulos m´as simp´aticos de la Combinatoria Enumerativa y luego remitirlo a la p´agina de Richard Stanley, 44 M. H. Rosas para que se divierta con las muy diferentes interpretaciones de los n´umeros de Catalan que all´ı se encuentran, y quiz´as descubra la verdadera raz´on por la cu´al los n´umeros de Catalan aparecen con tanta frecuencia, y en situaciones tan diversas, en las matem´aticas. 1 La recurrencia de Catalan Una triangulaci´on de un pol´ıgono es una manera de descomponerlo como una uni´on disjunta de tri´angulos, cuyos v´ertices coinciden con los del pol´ıgono. Es f´acil ver que para triangular un pol´ıgono con n+ 2 v´ertices se necesitan exactamente ntri´angulos (y viceversa). Por ejemplo, en la Figura 1 ilustramos las cinco triangulaciones de un pent´agono, cada una de ellas construida utilizando exactamente tres tri´angulos. Figura 1: Las cinco triangulaciones de un pent´agono. Un sencillo c´alculo convencer´a al lector que podemos triangular un tri´angulo de una ´unica manera, un cuadrado de dos, un pent´agono de cinco, y un hex´agono de catorce maneras diferentes. El problema se complica cada vez que aumentamos el n´umero de lados del pol´ıgono. En esta secci´on presentaremos una recurrencia que nos permite calcular estos valores f´acilmente. Sea Cnel n´umero de maneras de descomponer un pol´ıgono utilizando exactamente ntri´angulos. Procedemos por inducci´on en npara calcular Cn. Supongamos que sabemos triangular todos los pol´ıgonos con un m´aximo de n+ 2 lados, y con esta informaci´on triangulemos un pol´ıgono con n+ 3 lados. (El problema es trivial si tenemos un s´olo tri´angulo.) Procedemos de la siguiente manera. Primero escogemos a nuestro lado favorito del pol´ıgono de v´ertices 1,2,···, n + 3. En lo que sigue, el lado favorito del lector siempre ser´a el que une a los v´ertices 1 y n+ 3. Este lado pertenece a un ´unico tri´angulo en nuestra triangulaci´on, Ti, cuyo tercer v´ertice ipertenece al conjunto {2,3,···, n + 2}. Ver Figura 2. Eliminando al tri´angulo Tide nuestro pol´ıgono, obtenemos dos nuevos pol´ıgonos que se encuentran triangulados. El primero de ellos tiene como v´ertices a los n´umeros 1,2,···i, y en consecuencia, puede ser triangulado de Ci−2maneras diferentes. El segundo pol´ıgono tiene como v´ertices a los n´umeros i, i+1,···, n+ 3, y en consecuencia puede ser triangulado de Cn−i+2 maneras distintas. Ambas Los N´ umeros de (Euler)-Catalan 45 Figura 2: La disecci´on de un pol´ıgono con un lado favorito, y cuyo tercer v´ertice es i. elecciones son independientes. As´ı que el n´umero de maneras de triangular al pol´ıgono (que contienen al tri´angulo Ti) es Ci−2Cn−i+2. Al variar al tercer v´ertice del tri´angulo Tisobre todos los valores posibles, 2,3,···, n + 2, obtenemos la recurrencia de Catalan; Cn+1 =C0Cn+C1Cn−1+···+Cn−1C1+CnC0, (Note que estamos suponiendo que C0= 1.) La recurrencia de Catalan nos permite calcular r´apidamente los primeros valores de la sucesi´on de Catalan: 1,1,2,5,14,42, 132,429,1430,4862,16796,58786, 208012,742900,2674440,9694845,35357670,··· Para convencer al lector del poder de las recurrencias le dejar´e un par de tareas. La estructura recursiva que acabamos de hallar nos permite generar todas las triangulaciones de un pol´ıgono. La primera tarea consiste en escribir un programa de computaci´on que genere todas las triangulaciones de un pol´ıgono de manera recursiva. La recurrencia de Catalan tambi´en nos permite demostrar que otros conjuntos se pueden contar con los n´umeros de Catalan. Una segunda tarea para el lector consiste en demostrar que las siguientes familias obedecen a la recurrencia de Catalan: Maneras (legales) de colocar parejas de par´entesis, caminos de Dyck, y escrutinios electorales, donde el candidato ganador siempre va a la cabeza (o empatado) y termina con exactamente un voto m´as que el perdedor. Las cinco maneras de colocar 3 parejas de par´entesis son ((())), ()(()), (())(), (()()) y ()()(). Un camino de Dyck es el resultado de una caminata con pasos de longitud constante y en las direcciones noreste y sureste, y de manera tal que nunca nos 46 M. H. Rosas encontramos en un punto con altura menor a la altura que ten´ıamos al inicio del recorrido. Los cinco caminos de Dyck de longitud 2 ·3 est´an ilustrados en la Figura 3. Figura 3: Los cinco caminos de Dyck de longitud 2 ·3. Finalmente, los cinco resultados electorales donde el candidato ganador, en todo momento se encuentra a la cabeza o empatado con el candidato perdedor (y donde el candidato ganador recibe un voto m´as que el perdedor) son: aaabb, aabab,aabba,abaab yababa. A pesar de no ser particularmente elegante, es com´un deducir a la f´ormula cerrada de Catalan utilizando la recurrencia que acabamos de encontrar. El lector interesado puede consultar para esto al segundo ap´endice de este trabajo. 2 La f´ormula cerrada de los n´umeros de Catalan. Una manera particularmente elegante para derivar a la f´ormula cerrada para los n´umeros de Catalan fue encontrada por Alfred R´enyi. Los n´umeros de Catalan enumeran a la familia de los ´arboles binarios. Esta afirmaci´on le queda de tarea al lector, quien podr´a ver facilmente que la familia de los ´arboles binarios satisface a la recurrencia de Catalan. Imaginemos que nuestros ´arboles son como los ´arboles geneal´ogicos, donde cada padre tiene exactamente 2 hijos, uno derecho y el otro izquierdo. (Los ´arboles vienen dibujados en el plano, as´ı que podemos hablar de izquierda, derecha, arriba y abajo) Figura 4: Los cinco ´arboles binarios con 3 padres. Los N´ umeros de (Euler)-Catalan 47 Sea B(n) el n´umero de ´arboles binarios con npadres. Nuestra tarea consiste en demostrar que los ´arboles binarios satisfacen la recurrencia: (n+ 1)B(n) = 2(2n−1)B(n−1) (n > 1) El lector deber´a demostrar que un ´arbol binario con nni˜nos (un ni˜no es un v´ertice sin descendientes) tiene exactamente n−1 padres, y en consecuencia 2n−1 v´ertices. Figura 5: La biyecci´on de Alfred Renyi. Para demostrar la recurrencia procedemos como sigue. Construimos un ´arbol con npadres (de B(n) maneras) y seleccionamos en ´el al hijo menos favorito. Los eliminamos a ´el y a su padre y promovemos al hermano al lugar del padre. Obtenemos as´ı un ´arbol con nv´ertices, donde uno de ellos, el que corresponde al hermano reci´en promovido, est´a marcado. Para que este procedimiento sea una biyecci´on, necesitamos recordar si el hijo menos favorito era el derecho o era el izquierdo. Tenemos dos posibilidades, y aparece entonces un factor de dos en el lado derecho de nuestra ecuaci´on. Tenemos entonces que B(n) = 2 (2n−1) n+ 1 B(n−1) = 2 (2n−1) n+ 1 2 (2n−3) nB(n−2) =2 (2n−1) n+ 1 2 (2n−3) n···2 (2n−2k+ 1) n−k+ 1 ···3·1 =2n(2n−1)2(n−1) ···3·2·1 (n+ 1)! n! =1 n+ 12n n El lector demostr´o que B(n) = Cn. De manera que los n´umeros de Catalan vienen dados por la f´ormula cerrada: Cn=1 n+ 12n n 48 M. H. Rosas 3 Funciones Generatrices no conmutativas En esta secci´on describimos una manera elegante de hallar a la funci´on generatriz de Catalan. Es interesante mencionar que este fue el enfoque originalmente utilizado por Euler. La secci´on esta basada en el excelente libro de Flajolet y Sedgewick [2]. 3.1 Triangulaciones. Sea Tel conjunto formado por los poligonos triangulados. Figura 6: Los elementos de T. En la primera secci´on observamos que cualquier pol´ıgono triangulado pod´ıa ser descompuesto, univocamente y de manera can´onica, como una sucesi´on consistente en un pol´ıgono triangulado, un tri´angulo (el que corresponde a nuestro lado favorito), y luego otro pol´ıgono triangulado. Obtenemos entonces a la siguiente ecuaci´on: T=T∆T Al escribir a una sucesi´on kconjuntos de manera consecutiva estamos definiendo un nuevo conjunto cuyos elementos se obtienen juxtaponiendo los elementos de estos conjuntos. Por ejemplo, {a, b}{a, c}{d}={(a, a, d),(a, c, d),(b, a, d),(b, c, d)} Si definimos de manera can´onnica al lado favorito de un pol´ıgono triangulado, entonces cualquier triangulaci´on puede ser descompuesta de manera ´unica, tal y como se indica en La Figura 7. Definimos el peso de un pol´ıgono triangulado como el resultado de elevar a la indeterminada zal n´umero de tri´angulos que se encuentran en ella. Por ejemplo, los pesos de los pol´ıgonos triangulados que aparecen en la figura 7 son z7,z3,zyz3, respectivamente. M´as a´un, la igualdad descrita en la figura se traduce en z7=z3·z·z3. Sea Tla funci´on generatr´ız que se obtiene al sumar los pesos de todos los elementos de T. La descomposici´on que hemos descrito se traduce en la ecuaci´on cuadr´atica de Catalan: T(z) = 1 + T(z)·z·T(z) Los N´ umeros de (Euler)-Catalan 49 Figura 7: Descomposicion de una tri´angulaci´on. En particular, el coeficiente de znen el desarrollo en serie de T(z) es el n-´esimo n´umero de Catalan, Cn. (Ver secci´on 1). Utilizando la f´ormula del discriminante, obtenemos dos posibles soluciones de la ecuaci´on cuadr´atica de Catalan: T(z) = 1 + √1−4z 2z T(z) = 1−√1−4z 2z. Verificando que limx→0 1−√1−4x 2x=1=T(0) y que por otra parte la otra alternativa a de ser descartada ya que el limx→0 1+√1−4x 2x=∞obtenemos que la funci´on generatriz de Catalan: T(z) = X n≥0 Cnzn=1−√1−4z 2z Por cierto, es posible evitar calcular este l´ımite desarrollando ambas soluciones como series de potencias, y observando entonces cu´al de ellas salisface nuestras condiciones iniciales, tal como lo indicamos en el primer ap´endice de este trabajo. Si el lector est´a familiarizado con el teorema del binomio de Newton, ya lo que queda es rutina. En caso contrario, lo invito a leer en este momento el primer ap´endice de este trabajo. Desarrollando a la funci´on generatriz de Catalan como una serie de potencias 50 M. H. Rosas conseguimos una vez mas a la f´ormula cerrada de Catalan: T(z) = 1−√1−4z 2z =X n≥0 1 n+ 12n nzn = 1 + z+ 2z2+ 5z3+ 14z4+ 42z5+··· 3.2 Arboles de Catalan. Definimos a un ´arbol de Catalan como un ´arbol plano, con ra´ız, y sin etiquetas. Para aclarar los t´erminos nada mejor que un dibujo. En la Figura 8 se encuentran los cinco ´arboles de Catalan con 3 + 1 v´ertices. Figura 8: Los cinco ´arboles de Catalan con 3 + 1 v´ertices. Sea Gel conjunto de todos los ´arboles de Catalan. Se deja al lector la tarea de ver que G2es el conjunto de los pares ordenados de ´arboles de Catalan, que G3es el conjunto de todos los triples ordenados de Catalan, y en general que Gkes el conjunto de todas las k-uplas ordenadas de Catalan. Ahora viene el paso crucial. Cualquier ´arbol de Catalan puede ser descompuesto como un punto, (que corresponde a la ra´ız y que denotaremos por o), seguido por una sucesi´on de ´arboles de Catalan, que bien podr´ıa ser vac´ıa. G=o·1 + G+G2+G3+···=o 1−G Un ejemplo de esta correspondencia se encuentra ilustrado en la Figura 9. Como en la secci´on anterior, le asociamos un peso a cada ´arbol de Catalan. En este caso, el peso de un ´arbol de Catalan se calcula elevando la indeterminada zal n´umero de v´ertices que conforman el ´arbol. Sea G(z) la funci´on generatr´ız obtenida sumando a todos los pesos de todos los ´arboles en el conjunto G. La ecuaci´on anterior entre el conjunto Gse traduce en la siguiente ecuaci´on algebraica que satisface su funci´on generatr´ız . G(z) = z 1−G(z) Los N´ umeros de (Euler)-Catalan 51 Figura 9: La descomposici´on de un ´arbol como la uni´on de su ra´ız y una sucesi´on ordenada de ´arboles. Un razonamiento similar al utilizado en la seccion 3.1 y que se dej´o al lector nos permitir´a desarrollar a la funci´on generatr´ız G(z) como serie de potencias: G(z) = X n≥1 1 n2(n−1) n−1zn y concluir que Gn=Cn−1. 3.3 Polidominos Un polidomino es una colecci´on de cuadrados del mismo tama˜no donde cada uno de estos cuadrados est´a conectado con sus vecinos a trav´es de sus lados y con los que constituye una sola pieza. En la Figura 10 se encuentra dibujado un polidomino que consiste en 13 cuadrados. En la Figura 11, se encuentran dibujados tres configuraciones que no son polidominos. Figura 10: Un polidomino formado con 13 cuadrados. A pesar de ser una pregunta que intriga a muchos matem´aticos, nadie conoce una f´ormula cerrada que permita calcular el n´umero de polidominos que existen de un ´area dada, ni de un per´ımetro dado. Ahora, si imponemos la condici´on adicional que sea posible recorrer la frontera del polidomino caminando pasos norte (o este) y luego regresarse con pasos hacia el sur (u oeste) al punto de 58 M. H. Rosas Mercedes H. Rosas Departamento de Matem´ aticas Universidad Sim´ on Bol´ ıvar [email protected]e http://www.ma.usb.ve/˜mrosas