Historia DE LOS Números DE Catalán PDF

Preview

Summary

informe de la historia de los numeros catalan...

Description

HISTORIA DE LOS NÚMEROS DE CATALÁN INTRODUCCIÓN Estos números se utilizan en una gran variedad de problemas de combinatoria. Tienen varias aplicaciones; por ejemplo, determinar el número de formas en que un polígono con n+2 lados se pueden descomponer en n triángulos. En combinatoria los números de catalán forman una secuencia de números naturales. Obtienen su nombre del matemático belga Eugéne Charles Catalán El

enésimo

número

de

catalán

se

obtiene

con

la

formula

con n>=0 La ley de la eponimia de Stigler (1980) afirma que “ningún descubrimiento científico recibe el nombre de quien lo descubrió en primer lugar.” El matemático belga Eugène Charles Catalan (1814-1894) no fue el descubridor de los números de Catalan. Se llamaron números de Segner o números de Euler–Segner hasta 1901, cuando Eugen Netto (1848–1919) los renombró en el capítulo sobre el trabajo de Catalan de su libro “Lehrbuch der Combinatorik.” Sin embargo, el nombre “números de Catalan” no se popularizó y generalizó hasta 1968, gracias al famoso libro “Combinatorial Identities” de John Riordan (19031988). El nombre lo usó Henry Gould en 1971 en su completa bibliografía sobre estos números y también en 1973 Neil Sloane en su libro “A Handbook of Integer Sequences.” Todo el mundo pareció olvidar que siempre se llamaron números de Euler–Segner. Los números de Catalan fueron introducidos en 1751 por Leonhard Euler (17071783) que se lo comunicó por carta (que se conserva) a Christian Goldbach (16901764). Euler no logró demostrar su fórmula hasta 1759 gracias a su asistente Johann Andreas von Segner (1704-1777). Por ello, durante mucho tiempo los números de Catalan se llamaron números de Euler–Segner.

Sin embargo, la primera aparición histórica de los números de Catalan fue en la matemática del lejano oriente. Luo Jianjin descubrió en 1988 que los números de Catalan fueron introducidos por primera vez por el matemático chino Ming Antu (c.1692-c.1763), nacido en Mongolia, en su libro “Quick Methods for Accurate Values of Circle Segments” (escrito en la década de los 1730 y publicado de forma póstuma en 1839). En su trabajo original de 1751, Euler definió los números de Catalan número de triangulaciones de un polígono de

como el

lados. Euler calculó a mano

los ocho primeros números de Catalan, una labor de chinos, ya que

.

Gracias a ello sugirió la fórmula (correcta)

, y su función generatriz En 1758 Euler le propuso a Segner el problema de contar las triangulaciones de polígonos, pero sólo le mostró el valor de los siete primeros números de Catalan. Segner descubrió la siguiente fórmula de recurrencia , que le permitió calcular los primeros 18 números de Catalan. Gracias a esta fórmula de recurrencia, Euler demostró su fórmula de tipo producto y calculó los primeros 23 números de Catalan. Varios colegas de Euler trabajaron sobre los números de Catalan. Como el ruso Semën Kirillovich Kotelnikow (1723-1806) en 1766 y el suizo Nicolas Fuss (17551826) en 1795 (que introdujo los ahora llamados números de Fuss–Catalan generalizando la fórmula de Segner).

En 1838 el francés Joseph Liouville (1809-1882), editor del Journal de Mathématiques Pures et Appliquées, retó a los matemáticos franceses a demostrar de forma sencilla las fórmulas de Euler y Segner. El francés Gabriel Lamé (1795-1870) lo logró ese mismo año. Inspirado por este trabajo, en 1738, un belga estudiante de Liouville llamado Eugène logró obtener la fórmula que aparece en la figura que abre esta entrada, la que le llevó a la gloria (en la actualidad). CONCEPTOS BÁSICOS: ¿QUÉ ES RECURSIÓN? La recursión o recursividad es un concepto amplio, con muchas variantes. Aparece en numerosas actividades de la vida diaria; por ejemplo, en una fotografía donde se

observa

otra

fotografía.

La recursión es un recurso muy poderoso que permite expresar soluciones simples y naturales a ciertos tipos de problemas. Es importante considerar que no todos

los

problemas

son

naturalmente

recursivos.

Un objeto recursivo es aquel que aparece en la definición de sí mismo, así como el que se llama a sí mismo. “Foto triple” ¿QUÉ ES LA ITERACIÓN? La iteración es la repetición de una secuencia de instrucciones o eventos por un cierto número de veces. COMPLEJIDAD COMPUTACIONAL La complejidad computacional de este problema es P ya que puede ser resuelto en un tiempo polinómico por una maquina Turing Determinista y que puede ser tratable.

LA FÓRMULA CERRADA DE LOS NÚMEROS CATALÁN: Una manera para derivar a la fórmula cerrada para los números de catalán fue encontrada por Alfred Rényi. Los números de Catalán enumeran a la familia de los árboles binarios. Esta afirmación nos ayuda a ver fácilmente que la familia de los árboles binarios satisface a la recurrencia de Catalán. Imaginemos que nuestros árboles son como los árboles genealógicos, donde cada padre tiene exactamente 2 hijos, uno derecho y el otro izquierdo. (Los árboles vienen dibujados en el plano, así que podemos hablar de izquierda, derecha, arriba y abajo)

Figura 3: Los cinco árboles binarios con 3 padres.

Sea B(n) el número de árboles binarios con n padres. Nuestra tarea consiste en demostrar que los árboles binarios satisfacen la recurrencia:

(n + 1)B(n) = 2(2n − 1) B(n − 1)

(n > 1)...