Funciones Generadoras - Capítulo 4

Matemáticas Discretas
Profesora Ing. Rina Maria Familia
Funciones Generadoras
Capítulo 4
Emilio Jose De los santos // 21-0843

Manuel Alberto Diaz // 21-0113
Universidad Iberoamericana (UNIBE)
Definición:
es una serie formal de potencias cuyos coeficientes codifican
información sobre una sucesión an cuyo índice corre sobre los
enteros no negativos.Hay varios tipos de funciones generadoras:
funciones generadoras ordinarias, funciones generadoras
exponenciales, la serie de Lambert, la serie de Bell y la serie de
Dirichlet; Cada sucesión tiene una función generadora de cierto
tipo. El tipo de función generadora que es apropiada en un contexto
dado depende de la naturaleza de la sucesión y los detalles del
problema que se analiza.
Las funciones generadoras son expresiones cerradas en un
argumento formal x. A veces, una función generadora se «evalúa»
en un valor específico x=a pero hay que tener en cuenta que las
funciones generadoras son series formales de potencias, por lo que
no se considera ni se analiza el problema de la convergencia en
todos los valores de x.
Aplicaciones:
Si bien las funciones generadoras son una herramienta usada

ampliamente en combinatoria, no existen métodos detallados que
proporcionen solución a los problemas en cada situación. Sin
embargo existen ideas generales que pueden ser modificadas y
adaptadas en las diferentes situaciones que se presentan. A
continuación se ilustran varios usos de las funciones generadoras
junto con la idea general que se está usando.
Ecuaciones de recurrencia
Una ecuación de recurrencia es una expresión finita que define
implícitamente una sucesión, en la cual un elemento de la sucesión se
determina por medio de otros elementos más sencillos, que incluyen
casos iniciales o básicos. La conexión con el análisis de algoritmos
estriba en que la forma que se ha adoptado para medir las
complejidades, utiliza funciones cuyo dominio son los números
naturales, o en otras palabras, sucesiones. Si el algoritmo es
recurrente, es de esperarse que las complejidades, como funciones
que estiman la demanda de recursos a lo largo de la ejecución, sean
sucesiones que satisfacen ciertas ecuaciones de recurrencia.
Solucionar una ecuación de recurrencia consiste en encontrar
una expresión cerrada para una sucesión que satisfaga la
ecuación, i.e., una expresión en la que los valores de los
elementos de la sucesión no dependan de otros valores de la
sucesión. Para el caso del análisis de algoritmos, es deseable
contar con esta clase de expresiones cerradas, puesto que, a
partir de formulaciones recurrentes para funciones de
complejidad, resulta difícil establecer órdenes de crecimiento
asintótico correspondientes.
La solución de ecuaciones de recurrencia es de suyo importante
para la informática, si se piensa en que las matemáticas que esta
disciplina utiliza son eminentemente constructivas. Muchos
objetos informáticos son definidos de manera recurrente y los
razonamientos inductivos son piedra angular para desarrollos
teóricos y prácticos, utilizados de forma natural y, en ocasiones,
incluso inconscientemente. En este capítulo se estudiarán
métodos para solucionar algunas clases sencillas de ecuaciones
de recurrencia, como son la mayoría que ocurren en el análisis de
algoritmos.
Números Combinatorios
Las agrupaciones combinatorias que sólo consideran la esencia de los
grupos formados y no su orden, llamadas combinaciones, han
constituido una rama específica dentro de la especialidad del análisis
combinatorio, con múltiples usos en diversos campos. La expresión
numérica de tales combinaciones recibe el nombre de número
combinatorio o coeficiente binómico.
Lo único a tener en cuenta, además de que deben ser números enteros

positivos, es que el número de arriba no puede ser más pequeño que el
de abajo, es decir que debe ser siempre
Para escribirlos utilizaremos la pestaña de matrices en el editor de
fórmulas, de manera que insertamos siempre una matriz que tenga 1
columna y 2 filas.
RECURRENCIAS LINEALES
Definiciones Una relacion o formula de recurrencia de orden k ≥ 1 para

una sucesión {a0, a1, a2, ..., an, ...} es una expresión que relaciona
cada término con sus k términos anteriores: an = f (an−1, an−2, ...,
an−k) , para todo n ≥ k
ECUACIONES DE RECURRENCIA LINEALES Y HOMOGENEAS DE

SEGUNDO ORDEN Dada la relación de recurrencia con condiciones
iniciales: ½ an = c1an−1 + c2an−2∀n ≥ 2, (∗) a0 = b0 a1 = b1 ¾
Bibliografía
https://www.hiru.eus/es/matematicas/numeros-combinatorios
https://www.sangakoo.com/es/temas/numeros-combinatorios
https://www.cartagena99.com/recursos/alumnos/apuntes/MD_Tema5_Recurrencias.pdf
http://www.dma.fi.upm.es/docencia/grado_ii/matematica_discreta_1/resumen/recurrencias_lineales.
pdf
https://es.wikipedia.org/wiki/Función_generadora
https://www.cartagena99.com/recursos/alumnos/apuntes/capitulo10.pdf
https://www.youtube.com/watch?v=gvcazicmIK4
http://www.kramirez.net/Discretas/Material/Presentaciones/Ecuaciones_de_recurrencia_02-03.pdf
https://profesores.virtual.uniandes.edu.co/~isis1105/dokuwiki/lib/exe/fetch.php?media=enlaces:2-
ecurecu.pdf

Funciones Generadoras - Capítulo 4

Cargado por

Copyright:

Formatos disponibles

Funciones Generadoras - Capítulo 4

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Funciones Generadoras - Capítulo 4

Cargado por

Copyright:

Formatos disponibles

Matemáticas Discretas

Profesora Ing. Rina Maria Familia

Emilio Jose De los santos // 21-0843

Si bien las funciones generadoras son una herramienta usada

Lo único a tener en cuenta, además de que deben ser números enteros

Definiciones Una relacion o formula de recurrencia de orden k ≥ 1 para

ECUACIONES DE RECURRENCIA LINEALES Y HOMOGENEAS DE

También podría gustarte