Uso de Función Generatriz
Prof: Rodrigo Arriagada
Departamento de Informática
Universidad Técnica Federico Santa María
Definición
• La función generatriz es una
transformación que permite condensar
todos los valores de una secuencia {a0,
a1, ..., an, ...} en una única función:
• Y dado a(z) podemos obtener an como:
Rodrigo Alejandro Arriagada Nuñez
Fundamentos de Informática II ILI-153
2
Algebra Generatriz básica
• Supongamos que sabemos que la
función generatriz para an es a(z).
¿Cual es la función generatriz para
an−1?. Esta sería:
donde hemos supuesto que la nueva
secuencia valdrá cero en la primera
componente.
Rodrigo Alejandro Arriagada Nuñez
Fundamentos de Informática II ILI-153
3
Identidades
Rodrigo Alejandro Arriagada Nuñez
Fundamentos de Informática II ILI-153
4
Transformaciones
Rodrigo Alejandro Arriagada Nuñez
Fundamentos de Informática II ILI-153
5
Ejemplo de aplicación
• Serie de Fibonacci
– aun no podemos aplicar funciones generatrices
porque la ecuación no es valida para todo n, por
ejemplo no esta definida para 0 y 1. Lo que
haremos será re-expresarla como:
Rodrigo Alejandro Arriagada Nuñez
Fundamentos de Informática II ILI-153
6
Ejemplo de aplicación
• ahora tomamos función generatriz de
ambos lados
• multiplicando por z^2 ambos lados
tenemos
Rodrigo Alejandro Arriagada Nuñez
Fundamentos de Informática II ILI-153
7
Ejemplo de aplicación
• es decir
• Con lo cual termina la primera etapa de la
solución. Hemos mostrado como convertimos
una recurrencia en una ecuación normal
acerca de la función generatriz. ¿Como
recuperar ahora la secuencia?. En este caso,
notemos que F(z) se puede expandir en
fracciones parciales
Rodrigo Alejandro Arriagada Nuñez
Fundamentos de Informática II ILI-153
8
Ejemplo de aplicación
• Ahora es fácil de invertir a partir de la
tabla, resultando
• Tarea: Determine usted los coeficientes de la
fracción parcial. Use numero aureo.
Rodrigo Alejandro Arriagada Nuñez
Fundamentos de Informática II ILI-153
9
Descargar

Semana 1