Catalan
Páginas: 19 (4651 palabras)
Publicado: 1 de septiembre de 2010
Bolet´ de la Asociaci´n Matem´tica Venezolana, Vol. X, No. 1 (2003) ın o a
43
Los N´meros de (Euler)-Catalan. u
Mercedes H. Rosas
A Rafa´l S´nchez Lamoneda e a Fue el gran Leonhard Euler (1707–1783) la primera persona en calcular los n´meros de Catalan. Esto nos lo relata su contempor´neo Johann Segner (1704u a 1777) en su art´ ıculo: Enumeratio modorum, quibus figurae planae rectilineaeper diagonales dividuntur in triangula, Novi Commentarii Acad. Sci. Petropolitanae, 7 (1758-59) 203-209. Segner nos cuenta que los primeros valores para los n´meros de Catalan le u fueron comunicados por Euler, quien, sin embargo, le escondi´ la t´cnica que o e utiliz´ para calcularlos. “quos numeros mecum benevolus communicavit summus o 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´n de este art´ o ıculo. En un art´ ıculo posterior, y del mismo t´ ıtulo, Segner conjetur´ correctamente la f´rmula cerrada para los o o n´meros de Catalan, m´s no logr´ demostrarla. u a o Euler responde a los art´ ıculos de Segner sacando sus garras. En su “Summarium, NoviComentarii academiae scientiarum Petropolitanae 7, (1758/59), 13–15.” Reimpreso en su “Opera Omnia (1) 26 (1953), xvi-xviii,” Euler calcula la funci´n generatriz de Catalan, y de ella deriva la f´rmula cerrada de Catalan o o utilizando las ideas descritas en la secci´n 3 de este trabajo. La genialidad de o Euler para atacar este problema, as´ como sus famosos trabajos en la teor´ de ı ıa particiones,inician el estudio de las funciones generatrices y con ´l una larga y e fruct´ ıfera uni´n entre el an´lisis y la combinatoria, [1]. o a Alrededor de un siglo despu´s Eugene Catalan (1814-1894), volver´ a cale a cular el n´mero de maneras de triangular un pol´ u ıgono. En su memoria, los n´meros de Catalan llevan hoy en dia su nombre. u En su p´gina en la internethttp://www-math.mit.edu/~rstan/ec, a Richard Stanley nos reta con 95 familias de objetos enumerados por los n´meros u de Catalan. Las primeras 66 familias constituyen el famoso problema 6.19 de su libro EC2 [5]. Las restantes 29 (en la versi´n del 14 de Abril del 2003) o conforman el “Catalan Addendum” que es actualizado frecuentemente. Mi objetivo es recorrer junto al lector uno de los cap´ ıtulos m´s simp´ticos de a a laCombinatoria Enumerativa y luego remitirlo a la p´gina de Richard Stanley, a
44
M. H. Rosas
para que se divierta con las muy diferentes interpretaciones de los n´meros de u Catalan que all´ se encuentran, y quiz´s descubra la verdadera raz´n por la ı a o cu´l los n´meros de Catalan aparecen con tanta frecuencia, y en situaciones tan a u diversas, en las matem´ticas. a
1
La recurrenciade Catalan
Una triangulaci´n de un pol´ o ıgono es una manera de descomponerlo como una uni´n disjunta de tri´ngulos, cuyos v´rtices coinciden con los del pol´ o a e ıgono. Es f´cil ver que para triangular un pol´ a ıgono con n + 2 v´rtices se necesitan exace tamente n tri´ngulos (y viceversa). a Por ejemplo, en la Figura 1 ilustramos las cinco triangulaciones de un pent´gono, cada una de ellasconstruida utilizando exactamente tres tri´ngulos. a a
Figura 1: Las cinco triangulaciones de un pent´gono. a Un sencillo c´lculo convencer´ al lector que podemos triangular un tri´ngulo a a a de una unica manera, un cuadrado de dos, un pent´gono de cinco, y un hex´gono ´ a a de catorce maneras diferentes. El problema se complica cada vez que aumentamos el n´mero de lados del pol´ u ıgono. Enesta secci´n presentaremos una o recurrencia que nos permite calcular estos valores f´cilmente. a Sea Cn el n´mero de maneras de descomponer un pol´ u ıgono utilizando exactamente n tri´ngulos. Procedemos por inducci´n en n para calcular Cn . a o Supongamos que sabemos triangular todos los pol´ ıgonos con un m´ximo de a n + 2 lados, y con esta informaci´n triangulemos un pol´ o ıgono con n + 3...
43
Los N´meros de (Euler)-Catalan. u
Mercedes H. Rosas
A Rafa´l S´nchez Lamoneda e a Fue el gran Leonhard Euler (1707–1783) la primera persona en calcular los n´meros de Catalan. Esto nos lo relata su contempor´neo Johann Segner (1704u a 1777) en su art´ ıculo: Enumeratio modorum, quibus figurae planae rectilineaeper diagonales dividuntur in triangula, Novi Commentarii Acad. Sci. Petropolitanae, 7 (1758-59) 203-209. Segner nos cuenta que los primeros valores para los n´meros de Catalan le u fueron comunicados por Euler, quien, sin embargo, le escondi´ la t´cnica que o e utiliz´ para calcularlos. “quos numeros mecum benevolus communicavit summus o 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´n de este art´ o ıculo. En un art´ ıculo posterior, y del mismo t´ ıtulo, Segner conjetur´ correctamente la f´rmula cerrada para los o o n´meros de Catalan, m´s no logr´ demostrarla. u a o Euler responde a los art´ ıculos de Segner sacando sus garras. En su “Summarium, NoviComentarii academiae scientiarum Petropolitanae 7, (1758/59), 13–15.” Reimpreso en su “Opera Omnia (1) 26 (1953), xvi-xviii,” Euler calcula la funci´n generatriz de Catalan, y de ella deriva la f´rmula cerrada de Catalan o o utilizando las ideas descritas en la secci´n 3 de este trabajo. La genialidad de o Euler para atacar este problema, as´ como sus famosos trabajos en la teor´ de ı ıa particiones,inician el estudio de las funciones generatrices y con ´l una larga y e fruct´ ıfera uni´n entre el an´lisis y la combinatoria, [1]. o a Alrededor de un siglo despu´s Eugene Catalan (1814-1894), volver´ a cale a cular el n´mero de maneras de triangular un pol´ u ıgono. En su memoria, los n´meros de Catalan llevan hoy en dia su nombre. u En su p´gina en la internethttp://www-math.mit.edu/~rstan/ec, a Richard Stanley nos reta con 95 familias de objetos enumerados por los n´meros u de Catalan. Las primeras 66 familias constituyen el famoso problema 6.19 de su libro EC2 [5]. Las restantes 29 (en la versi´n del 14 de Abril del 2003) o conforman el “Catalan Addendum” que es actualizado frecuentemente. Mi objetivo es recorrer junto al lector uno de los cap´ ıtulos m´s simp´ticos de a a laCombinatoria Enumerativa y luego remitirlo a la p´gina de Richard Stanley, a
44
M. H. Rosas
para que se divierta con las muy diferentes interpretaciones de los n´meros de u Catalan que all´ se encuentran, y quiz´s descubra la verdadera raz´n por la ı a o cu´l los n´meros de Catalan aparecen con tanta frecuencia, y en situaciones tan a u diversas, en las matem´ticas. a
1
La recurrenciade Catalan
Una triangulaci´n de un pol´ o ıgono es una manera de descomponerlo como una uni´n disjunta de tri´ngulos, cuyos v´rtices coinciden con los del pol´ o a e ıgono. Es f´cil ver que para triangular un pol´ a ıgono con n + 2 v´rtices se necesitan exace tamente n tri´ngulos (y viceversa). a Por ejemplo, en la Figura 1 ilustramos las cinco triangulaciones de un pent´gono, cada una de ellasconstruida utilizando exactamente tres tri´ngulos. a a
Figura 1: Las cinco triangulaciones de un pent´gono. a Un sencillo c´lculo convencer´ al lector que podemos triangular un tri´ngulo a a a de una unica manera, un cuadrado de dos, un pent´gono de cinco, y un hex´gono ´ a a de catorce maneras diferentes. El problema se complica cada vez que aumentamos el n´mero de lados del pol´ u ıgono. Enesta secci´n presentaremos una o recurrencia que nos permite calcular estos valores f´cilmente. a Sea Cn el n´mero de maneras de descomponer un pol´ u ıgono utilizando exactamente n tri´ngulos. Procedemos por inducci´n en n para calcular Cn . a o Supongamos que sabemos triangular todos los pol´ ıgonos con un m´ximo de a n + 2 lados, y con esta informaci´n triangulemos un pol´ o ıgono con n + 3...
Leer documento completo
Regístrate para leer el documento completo.