Numeros De Catalan 72dt

UNIVERSIDAD NACIONAL “HERMILIO VALDIZAN” E.A.P INGENIERIA DE SISTEMAS

NUMEROS DE CATALAN

    

PROFESOR

:

ING. MIGUEL ANGEL CRUZ V.

CICLO

:

II

INTEGRANTES : FIRMA LOYOLA, Cristhian Omar BARRA ESPINOZA, Anthony PALOMINO PEREZ, Pier MINAYA CCOPACONDORI, Ellery RAMOS PICOY, Jhonatan

Huánuco - Perú 2015

Dedicado a todos los profesores de la EAP de Ingeniería de Sistemas de la Universidad Nacional Hermilio Valdizán, por su contribución y compromiso en nuestra formación profesional.

INTRODUCCION

Los números de catalán, deben su nombre al matemático belga Eugene Charles Catalan, pero es un hecho que se remontan a Euler en el siglo XVIII, son particularmente interesantes por su multiplicidad de interpretaciones. En este trabajo se explora la obtención de los números de Catalan a partir de problemas planteados, y algunas maneras prácticas para generarlos mediante el empleo de arreglos triangulares, conjeturando propiedades. Además, para su enseñanza permiten la exploración, la experimentación y el establecer conjeturas, sirviendo para modelar problemas de combinatoria en disciplinas como el álgebra, la informática, la teoría de grafos y la geometría.

El desarrollo de este tema es muy importante porque nos brinda un conocimiento base, para comprender mejor los temas posteriores que desarrollaremos en el transcurso de nuestra carrera.

Contenido

I.- Generalidades Antecedentes Función de Euler en los números de Catalan Descubridor de los números de Catalan II.- Números de Catalan Definición Propiedades III.- Problemas de Triangulación y de sucesiones El Problema de triangulación de polígonos convexos El problema de las sucesiones bien formadas por paréntesis IV.- Formula cerrada a partir de la Recurrencia Formula de recurrencia Hallando triangulaciones de polígonos V.- Triangulo de Pascal y números de Catalan Otra forma para hallar los números de Catalan VI.- Ejemplos Aplicados en Combinatoria VII.- Conclusiones XIII.- Bibliografía

I.- Generalidades Antecedentes (historia) de los números de catalán 1. PRIMER CONCEPTO Los números de catalán fueron introducidos en 1751 por Leonard Euler (1707-1783) que se lo comunicó por carta (que se conserva) a Christian Gold Bach (1690-1764). 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 catalán se llamaron números de Euler–Segner.

2. SEGUNDO CONCEPTO El nombre “números de Catalán” no se popularizó y generalizó hasta 1968, gracias al famoso libro “Combinatoria Identities” de John Riordan (1903-1988). 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 LA FUNCION DE EULER EN LOS NUMEROS DE CATALAN

En su trabajo original de 1751, Euler definió los números de catalán como el número de triangulaciones de un polígono de lados. Euler calculó a mano los ocho primeros números de Catalán, 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 catalán. Segner descubrió la siguiente fórmula de recurrencia , Permitió calcular los primeros 18 números de catalán. Gracias a esta fórmula de recurrencia, Euler demostró su fórmula de tipo producto y calculó los primeros 23 números de catalán.

DESCUBRIDOR DE LOS NUMEROS DE CATALAN PRIMER DESCUBRIDOR: “MING ANTU” Luo Jianjin descubrió en 1988 que los números de Catalán 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). 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 Catalán (1814-1894) no fue el descubridor de los números de catalán. Los números de catalán fueron introducidos en 1751 por Leonhard Euler (17071783)

II.- Números de Catalan DEFINICION Los números de catalán forman una secuencia de números naturales que aparece en varios problemas de conteo que habitualmente son recursivos. El n-ésimo número de catalán se obtiene, aplicando coeficientes binomiales, a partir de la siguiente fórmula:

PROPIEDADES Una expresión alternativa para Cn es

Esta otra expresión muestra que Cn es un número natural, lo cual no resulta obvio a priori mirando la primera fórmula dada. Los números de catalán satisfacen la siguiente relación de recurrencia:

Y también satisfacen:

Que puede ser una forma más eficiente de calcularlos. La expresión en forma de recursión, seria:

III.- Problemas de Triangulación y de sucesiones EL PROBLEMA DE LA TRIANGULACIÓN DE POLÍGONOS CONVEXOS Dado un polígono convexo, podemos trazar diagonales que no se corten entre sí para que quede dividido en triángulos. A esto se le llama triangular un polígono. Si tomamos los polígonos regulares y llamamos Cn al número de triangulaciones de un polígono convexo con n+2 lados: 

Triángulo equilátero: ya está triangularizado. Hay 1 forma. C1 = 1



Cuadrado: tiene 4 vértices, luego podemos trazar 2 diagonales. Hay 2 formas. C2 = 2



Pentágono: 5 vértices, 2 diagonales. Hay 5 formas de triangularizarlo. C3 = 5



Hexágo diagonales y 14 formas de triangularizar. C4 = 14



Heptágono: 42 formas. C5 = 42



Octógono: 132 formas. C6 = 132

Estos números forman la sucesión de Catalan: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,…

no:

6

vértices,

3

EL PROBLEMA DE LAS SUCESIONES BIEN FORMADAS DE PARÉNTESIS Tenemos n letras dispuestas en forma de palabra en un cierto orden. Deseamos añadir n-1 pares de paréntesis en esta palabra de forma que dentro de cada par de paréntesis caigan dos términos. Estos dos términos pueden ser dos letras juntas, una letra junto con un grupo encerrado ya entre paréntesis o dos grupos contiguos. ¿De cuántas formas podemos realizar esta tarea? Veamos la solución de los primeros casos: 

Para dos letras , solo 1 forma:

(ab)



Para tres letras , 2 formas:

((ab)c) y (a(bc))



Para cuatro letras , 5 formas: ((a(bc))d)

Obtenemos la misma sucesión: 1, 2, 5, 14, 42,…

((ab)(cd)), (((ab)c)d), (a(b(cd))), (a((bc)d)) y

IV.- FÓRMULA DE RECURRENCIA DE LOS NÚMEROS DE CATALAN Sabemos que C1 = 1, y vamos a tomar C0 = 1. Por inducción, supongamos conocidos los valores de los primeros Cn. Intentaremos hallar Cn+1. Esto equivale a suponer conocidas las triangulaciones de polígonos hasta (n+2) lados e intentar conocer las del polígono de (n+3) lados.

Sea P un polígono de (n+3) lados, que numeraremos 1, 2, 3, …, n+2, n+3. Elegimos uno de los lados, el que tiene como vértices {1, (n+3)}. Una vez elegido este lado, tomamos uno de los vértices restantes (que llamaremos vértice i) para formar un triángulo. (En rosa, el triángulo Ti en la figura). Dicho triángulo divide al polígono P en tres partes: un subpolígono P1 de vértices {1,2,3,…,i}; el propio triángulo Ti y otro subpolígono P2 de vértices {i,i+1,i+2,…n+2,n+3}. P1 tiene obviamente i vértices. P2 tiene (n-i+4) vértices. Esto quizás no es tan fácil de ver. Se comprende mejor al ver que la suma de los vértices de P1 y P2 debe ser una unidad superior a los vértices de P, puesto que el vértice i lo tomamos dos veces, una para cada subpolígono. Así pues deben sumar entre ambos (n+4) vértices, y por lo tanto P2 tendrá (n-i+4) vértices. Sabiendo el número de vértices de P1 y P2, sabemos automáticamente sus respectivos números de triangulaciones: Ci-2 y Cn-i+2 respectivamente. Así que para el triángulo Ti escogido tenemos Ci-2 · Cn-i+2 posibles triangulaciones. Resulta que el vértice i lo podemos elegir desde i = 2 hasta i = (n+2) para formar el triángulo Ti, luego tendremos tenemos que las posibles triangulaciones del polígono P, de (n+3) lados, será dicho producto Ci-2 · Cn-i+2 extendido a todos los posibles

valores de i: Esto es:

Que es la fórmula de recurrencia deseada. Dado que conocíamos los primeros casos, ahora podemos fácilmente ir hallando los siguientes. Ejemplo: Triangulaciones de un hexágono

V.- TRIÁNGULO DE PASCAL Y NÚMEROS DE CATALAN El triángulo de Pascal o Triángulo de Tartaglia es una representación de los coeficientes binomiales ordenados en forma triangular. Se construye poniendo unos en los extremos y colocando en las posiciones intermedias la suma de los números de la fila superior.

Tomamos el triángulo de Pascal y nos quedamos con la columna central, esto es, 1, 2, 6, 20,... Ahora restamos a cada número de esa columna central el número que tiene al lado en el triángulo. Así también se obtienen los números de Catalan.

VI.- EJEMPLOS Los números de Catalan aparecen en diversos problemas de enumeración aparentemente inconexos. Ya se explicaron 2 problemas: la enumeración de las maneras en que un polígono con n lados se puede cortar en n triángulos y el número de formas de colocar parejas de paréntesis. También existen más ejemplos de donde surgen los números Catalan, a continuación algunos de ellos: Ejemplo 1 : Supongamos que tenemos una cantidad infinita de monedas y que deseamos acomodarlas en filas, sujetas a las siguientes condiciones.   

La fila de abajo consiste de n monedas, cada una en o con las 1. dos más próximas a sus lados, excepto las 2 de los extremos. n Una moneda que no pertenece a un renglón se sitúa entre las dos monedas debajo de ellas. No se hace distinción entre cara o cruz.

Ejemplo 2: Encuentre el número de maneras en que 2n personas, sentadas alrededor de una mesa redonda, pueden saludarse sin que sus manos se crucen. Para n 0 Solución: La figura muestra los varios posibles saludos para 0

n

4

Ejemplo 3: Encuentre el número de trayectorias en que una torre se puede mover desde la esquina superior izquierda hasta la esquina inferior derecha en un tablero de ajedrez de n n sin cruzar la diagonal principal. Solución; La figura muestra las posibles trayectorias para 1

n

5

VII.- CONCLUSIONES Existen diferentes formas de generar los números de Catalan, siendo una de ellas a partir del Triángulo de Pascal, llegar a la fórmula del desarrollo del binomio y obtener los números de Catalan.

El Triángulo de Pascal es uno de los modelos numéricos más famosos en la historia de la Matemática, el cual se construye de forma sencilla pero proveer una fuente, aparentemente inagotable de propiedades. XII.- BIBLIOGRAFIA 1. 2. 3. 4. 5.

“Matemática Discreta” NORMAN L. Biggs “Números de Catalan ”, Armando Alcalá Vallejo “Los números de Catalan ”, de Miguel Ángel Morales para Gaussianos “Recurrencia de Catalan”. “El triángulo de Pascal y la sucesión de Fibonacci ”, de Miguel Ángel Morales para Gaussianos