Función generadora

En matemáticas, una función generadora o función generatriz es una serie formal de potencias cuyos coeficientes codifican información sobre una sucesión a_n 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; de las cuales abajo se ofrecen definiciones y ejemplos. 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.

Por lo mismo es importante observar que las funciones generadoras no son realmente funciones en en el sentido usual de ser mapeos entre un dominio y un codominio; el nombre es únicamente el resultado del desarrollo histórico de su estudio.

Una función generadora es una cuerda de tender en la que colgamos una sucesión de números para mostrarla

Herbert Wilf^[1]

Función generadora ordinaria

La función generadora ordinaria de una sucesión (a_n) = a₀, a₁, a₂, a₃ ... se define como

$A(x)=\sum_{n=0}^{\infty}a_nx^n=a_0+a_1x+a_2x^2+a_3x^3+\cdots$

Es común usar la expresión función generadora sin mayor calificativo, para referirse a este tipo de función.

Ejemplo.: La sucesión de Fibonacci definida por la recurrencia

$f_{n+1}=f_{n}+f_{n-1},\quad n>0,\qquad f_0=0, f_1= 1$

es la sucesión 0,1,1,2,3,5,8,13,21,...

Su función generadora es

$F(x)=\frac{x}{1-x-x^2}$

puesto que el desarrollo en serie de potencias de tal función es

$\frac{x}{1-x-x^2} = 0 + 1\cdot x + 1\cdot x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7+\cdots$ .

y los coeficientes de tal desarrollo son precisamente 0,1,1,2,3,5,8,13,...

Es posible definir funciones generadoras sobre varias variables. Por ejemplo, la función generadora ordinaria en 2 variables de (a_m,n) donde n y m son índices que recorren los enteros no negativos, es

$A(x,y)=\sum_{m,n=0}^{\infty}a_{m,n}x^my^n= a_{0,0} + a_{1,0}x + a_{0,1}y + a_{2,0}x^2+a_{1,1}xy + a_{0,2}y^2 + a_{3,0}x^3 + a_{2,1}x^2y + \cdots$

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.

Determinación de la función generadora a partir de una recurrencia

En esta situación lo que se hace es multiplicar ambos lados de la recurrencia por x^n y sumar sobre todos los índices. Después se efectúan transformaciones para que la igualdad entre sumas que se obtiene se convierta en una ecuación que involucra la función generadora y se procede a resolverla.

Como ilustración, considere la recurrencia

$\ a_{n+1} = 3a_n + 2,\qquad a_0 = 1$ .

que da origen a la sucesión (a_n)=1,5,17,53,161,485,1457...

Multiplicando ambos lados por xⁿ y sumando sobre todos los valores de n se obtiene:

$\sum_{n=0}^\infty a_{n+1}x^n = a_1 + a_2x+a_3x^2 + a_4x^3 + \cdots = \sum_{n=0}^\infty (3a_n+2)x^n$ .

El lado izquierdo es casi la función generadora, pero los índices están desfasados. Pero notando que

$a_1 + a_2x+a_3x^2 + a_4x^3 + \cdots =\frac{(a_0 + a_1x + a_2x^2 + a_3x^3+\cdots)-a_0}{x}$ ,

se deduce que el lado izquierdo es

$\frac{A(x)-a_0}{x} = \frac{A(x)-1}{x}$ .

El lado derecho se desarrolla como

$\sum_{n=0}^\infty (3a_n+2)x^n= 3 \sum_{k=0}^\infty a_nx^n + 2\sum_{k=0}^\infty x^n=3A(x) + 2(1+x+x^2+x^3+\cdots) =3A(x) + \frac{2}{1-x}$ .

Al final, se aplicó la fórmula para sumar una serie geométrica:^[2]

$1 + x + x^2 + x^3 + x^4 + \cdots = \frac{1}{1-x}$ .

Igualando ambas simplificaciones, se obtiene la ecuación

$\frac{A(x)-1}{x} = 3 A(x) + \frac{2}{1-x},$

que al resolverse arroja por resultado

$A(x) = \frac{x+1}{3x^2-4x+1}.$

Ejemplo de aplicación práctica

Si c_n es el número de formas en que se puede pagar n pesos usando monedas de 1, 2 y 5 pesos, entonces la función generadora de la sucesión (c_n) es

$C(x) = \frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x^5} =(1+x+x^2+x^3+\cdots)(1+x^2+x^4+x^6+\cdots)(1+x^5 +x^{10}+x^{15}+\cdots)$ .

ya que el coeficiente de xⁿ es igual al número de formas de escoger a, b, c tales que

$x^n = x^a x^{2b}x^{5c}=x^{a+2b+5c},\$

y que corresponen a usar a monedas de 1 peso, b monedas de 2 pesos y c monedas de 5 pesos.

La aplicación de la fórmula de Taylor es demasiado compleja en este caso, por lo que aplicaremos el siguiente artificio debido a Ronald Graham.

Cada uno de los denominadores (1-x), (1-x²) y (1-x⁵) son divisores de (1-x¹⁰), por lo que podemos reescribir

$C(x)= \frac{A(x)}{(1-x^{10})^3}$

para un A(x) en donde:

$\begin{array}{rcl}A(x)&=&A_1(x)\cdot A_2(x)\cdot A_3(x) = \left(\frac{1-x^{10}}{1-x}\right) \left(\frac{1-x^{10}}{1-x^2}\right) \left(\frac{1-x^{10}}{1-x^5}\right)\\ \ &=& x^{22}+x^{21}+2x^{20}+2x^{19}+3x^{18}+4x^{17}+5x^{16}+6x^{15}+7x^{14}+8x^{13}+7x^{12}+8x^{11}\\ \ &\ &\quad+7x^{10}+8x^9+7x^8+6x^7+5x^6+4x^5+3x^4+2x^3+2x^2+x+1 \end{array}$

Finalmente, desarrollando la función generadora

$\frac{1}{(1-x^{10})^3} = \sum_{k\ge0} {2+k \choose k} x^{10k}={2\choose 2}+{3\choose 2}x^{10}+{4\choose 2}x^{20} + {5\choose 2}x^{30}+\cdots$

obtenemos

$C(x) = A(x) \sum_{k\ge0} {2+k \choose k} x^{10k}$ .

De la expresión anterior se puede leer con detalle el valor exacto del coeficiente de xⁿ, es decir, el número c_n de formas de pagar n pesos con monedas de 1,2 y 5 pesos. Por ejemplo, el número de formas de pagar 77 pesos se obtiene calculando el término correspondiente a x⁷⁷:

$(6x^7)\cdot {9\choose 2} x^{70} + (4x^{17})\cdot {8\choose 2}x^{60} = \left( 6{9\choose 2}+4{8 \choose 2}\right)x^{77} = (6\cdot 36 + 4\cdot 28 )x^{77} =328x^{77}$

y se concluye que hay 328 formas de pagar 77 pesos con monedas de 1, 2 o 5 pesos.

Otras funciones generadoras

Función generadora exponencial

La función generadora exponencial de una sucesión a_n es

$EG(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}.$

Función generadora de Poisson

La función generadora de Poisson de una sucesión a_n es

$PG(a_n;x)=\sum _{n=0}^{\infty} a_n e^{-x} \frac{x^n}{n!}.$

Serie de Lambert

La serie de Lambert de una sucesión a_n es

$LG(a_n;x)=\sum _{n=1}^{\infty} a_n \frac{x^n}{1-x^n}.$

Nótese que en una serie de Lambert, el índice n comienza en el 1, no en 0.

Serie de Bell

La serie de Bell de una función aritmética f(n) y un número primo p es

$f_p(x)=\sum_{n=0}^\infty f(p^n)x^n.$

Función generadora de la serie de Dirichlet

Las series de Dirichlet a menudo se clasifican como funciones generadoras, aunque no son estrictamente series formales de potencias. La función generadora de la serie de Dirichlet de una sucesión a_n es

$DG(a_n;s)=\sum _{n=1}^{\infty} \frac{a_n}{n^s}.$

La función generadora de la serie de Dirichlet es especialmente útil cuando a_n es una función multiplicativa, cuando tiene una expresión de producto de Euler en términos de la serie de Bell de la función

$DG(a_n;s)=\prod_{p} f_p(p^{-s})\,.$

Si a_n es un carácter de Dirichlet, entonces su función generadora de la serie de Dirichlet se llama serie L de Dirichlet.

Funciones generadoras de sucesiones polinómicas

El concepto de funciones generadoras puede extenderse a sucesiones de otros objetos. Así, por ejemplo, las sucesiones polinómicas de tipo binomial se generan por

$e^{xf(t)}=\sum_{n=0}^\infty {p_n(x) \over n!}t^n$

donde p_n(x) es una sucesión de polinomios y f(t) es una función de cierta forma. Las sucesiones de Sheffer se generan de modo similar. Véase el artículo principal polinomio generalizado de Appell para más información.

Ejemplos

Artículo principal: Ejemplos de funciones generadoras

Cuando se trabaja con funciones generadoras, es importante reconocer las expresiones de algunas sucesiones fundamentales.

Funciones generadoras ordinarias

La más fundamental de todas es la sucesión constante 1,1,1,1,..., cuya función generadora ordinaria es

$\sum_{n\in\mathbf{N}}X^n={1\over1-X}.$

La expresión de la derecha se puede justificar multiplicando la serie de potencias de la izquierda por $X - 1$ , y comprobando que su resultado sea la serie constante de potencias 1; en otras palabras, que todos los coeficientes desaparezcan excepto el de X⁰. (Por lo demás, no puede haber otra serie de potencias con esta propiedad, ya que un anillo de series de potencias como Z''X'' es un dominio de integridad.) El lado de la derecha, por lo tanto, designa la inversa de $X - 1$ en el anillo de series de potencias.

Fácilmente se derivan para ésta expresiones para la generación ordinaria de otras sucesiones. Por ejemplo, para la serie geométrica 1,a,a²,a³,... para cada constante a se tiene

$\sum_{n\in\mathbf{N}}a^nX^n={1\over1-aX},$

y en particular

$\sum_{n\in\mathbf{N}}(-1)^nX^n={1\over1+X}.$

También se pueden introducir «brechas» regulares en la sucesión sustituyendo X por alguna potencia de X; así, por ejemplo, para la sucesión1,0,1,0,1,0,1,0,.... se obtiene la función generadora

$\sum_{n\in\mathbf{N}}X^{2n}={1\over1-X^2}.$

Calculando el cuadrado de la función generadora inicial, fácilmente se ve que los coeficientes forman la sucesión 1,2,3,4,5,..., así que se tiene

$\sum_{n\in\mathbf{N}}(n+1)X^n={1\over(1-X)^2},$

y el cubo tiene como coeficientes los números triangulares 1,3,6,10,15,21,... cuyo término n es el coeficiente binomial $\tbinom{n+2}2$ , de manera que

$\sum_{n\in\mathbf{N}}\tbinom{n+2}2 X^n={1\over(1-X)^3}.$

Dado que $\tbinom{n+2}2=\frac12{(n+1)(n+2)} =\frac12(n^2+3n+2)$ , se puede encontrar la función generadora ordinaria para la sucesión 0,1,4,9,16,... de números cuadrados por combinación lineal de las sucesiones precedentes;

$G(n^2;x)=\sum_{n=0}^{\infty}n^2x^n={2\over(1-x)^3}-{3\over(1-x)^2}+{1\over1-x}=\frac{x(x+1)}{(1-x)^3}.$

Función generadora exponencial

$EG(n^2;x)=\sum _{n=0}^{\infty} \frac{n^2x^n}{n!}=x(x+1)e^x$

Serie de Bell

$f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=\frac{1}{1-p^2x}$

Función generadora de la serie de Dirichlet

$DG(n^2;s)=\sum_{n=1}^{\infty} \frac{n^2}{n^s}=\zeta(s-2)$

Aplicaciones

Las funciones generadoras se emplean para

encontrar una forma cerrada para una sucesión dada en una relación de recurrencia. Por ejemplo, considérense los números de Fibonacci;
encontrar relaciones de recurrencia para sucesiones: la forma de una función generadora puede sugerir una fórmula de recurrencia;
encontrar relaciones entre sucesiones: si las funciones generadoras de dos sucesiones tienen una forma similar, entonces las propias sucesiones probablemente están relacionadas;
explorar el comportamiento asintótico de las sucesiones;
demostrar identidades que implican sucesiones;
resolver problemas de enumeración en combinatoria;
evaluar sumas infinitas.

Otras funciones generadoras

Ejemplos de sucesiones polinómicas generadas por funciones generadoras más complejas son:

Difference polynomials
Generalized Appell polynomials
Q-difference polynomials

Véase también

Función generadora de momentos
Función generadora de probabilidad
Teorema de reciprocidad de Stanley
Aplicaciones a particiones.

Referencias

Herbert S. Wilf, Generatingfunctionology (Second Edition) (1994) Academic Press. ISBN 0-12-751956-4.
Donald E. Knuth, The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition) Addison-Wesley. ISBN 0-201-89683-4. Section 1.2.9: Generating Functions, pp.87–96.
Ronald L. Graham, Donald E. Knuth, y Oren Patashnik, Concrete Mathematics. A foundation for computer science (Second Edition) Addison-Wesley. ISBN 0-201-55802-5. Chapter 7: Generating Functions, pp. 320–380.
Gabriel Poveda Ramos, Funciones generatrices, Editorial de la Universidad Pontificia Bolivariana, ISBN 958-696-539-2, 90 pp., Medellín (Colombia) 2006.

Notas

↑ Wilf, Herbert (1994). generatingfunctionology. A. K. Peters. ISBN 978-1-56881-279-3.
↑ Como se mencionó en la introducción, realmente no importa el radio de convergencia de una serie, ya que sólo se busca manipular formalmente (es decir, «mecánicamente») las expresiones. En general es suficiente que una serie sea convergente en un disco abierto (no determinado) alrededor de cero para poder usarla. En el ejemplo, la serie geométrica es convergente en el disco -1<x<1.

Enlaces externos

Funciones generadoras, índices de potencias y cambio de moneda (en inglés) en Cut-the-knot.org (consultado el 1 de agosto de 2008)
Versión descargable en inglés de Generatingfunctionology, de H. Wilf (consultado el 1 de agosto de 2008)
1031 Generating Functions (consultado el 1 de agosto de 2008)
Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados, newsgroup es.ciencia.matematicas
Frederick Lecue; Riedel, Marko, et al., Permutation, Les-Mathematiques.net, en francés (el título desorienta un tanto)
"Generating Functions" por Ed Pegg, Jr., en el sitio web The Wolfram Demonstrations Project, 2007. (consultado el 1 de agosto de 2008)

Categorías:

Combinatoria enumerativa
Exponenciales

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

Función generadora de momentos — En probabilidad y estadística, la función generadora de momentos o función generatriz de momentos de una variable aleatoria X es siempre que esta esperanza exista. La función generadora de momentos se llama así porque, si existe en un entorno de… … Wikipedia Español
Función característica — Para otros usos de este término, véase Función indicatriz. La función característica de una variable aleatoria o de su distribución de probabilidad es una función de variable real que toma valores complejos, que permite la aplicación de métodos… … Wikipedia Español
Función zeta local — En la teoría de números, una función zeta local Z(t) es una función cuya derivada logarítmica es una función generatriz del número de soluciones de un conjunto de ecuaciones definidas sobre un cuerpo finito F, en extensión de cuerpos Fk de F.… … Wikipedia Español
Función zeta de Igusa — En matemáticas, una función zeta de Igusa es un tipo de función generadora, que cuenta el número de soluciones de una ecuación, módulo p, p2, p3, y así sucesivamente Contenido 1 Definición 2 Teorema de Igusa 3 Con … Wikipedia Español
Función localmente convexa — En análisis funcional y en áreas relativas a las matemáticas, espacios vectoriales topológicos localmente convexos o espacios localmente convexos son ejemplos de espacios vectoriales topológicos los cuales generalizan los espacios normados. Ellos … Wikipedia Español
Ejemplos de funciones generadoras — Saltar a navegación, búsqueda Los siguientes ejemplos de funciones generadoras se presentan siguiendo el espíritu de George Pólya, que abogaba por el aprendizaje de las matemáticas haciendo y repasando tantos ejemplos y pruebas como fuese posible … Wikipedia Español
Distribución normal — Saltar a navegación, búsqueda Distribución normal Función de densidad de probabilidad La línea verde corresponde a la distribución normal estandar Función de distribución de probabilidad … Wikipedia Español
Distribución uniforme continua — Saltar a navegación, búsqueda Para la distribución discreta, véase Distribución uniforme discreta. Uniforme Función de densidad de probabilidad Utilizando convención de máximo … Wikipedia Español
Sucesión de Fibonacci — Gráfica de la sucesión de Fibonacci hasta f10 En matemática, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales: La sucesión inicia con … Wikipedia Español
Distribución de Poisson — Saltar a navegación, búsqueda Distribución de Poisson Función de probabilidad El eje horizontal es el índice k. La función solamente está definida en valores enteros de k. Las líneas que conectan los puntos son solo guías para el ojo y no indican … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico

Función generadora

Contenido

Función generadora ordinaria

Aplicaciones

Determinación de la función generadora a partir de una recurrencia

Ejemplo de aplicación práctica

Otras funciones generadoras

Función generadora exponencial

Función generadora de Poisson

Serie de Lambert

Serie de Bell

Función generadora de la serie de Dirichlet

Funciones generadoras de sucesiones polinómicas

Ejemplos

Funciones generadoras ordinarias

Función generadora exponencial

Serie de Bell

Función generadora de la serie de Dirichlet

Aplicaciones

Otras funciones generadoras

Véase también

Referencias

Notas

Enlaces externos

Mira otros diccionarios:

Compartir el artículo y extractos

Los diccionarios y las enciclopedias sobre el Académico

Wikipedia Español

Función generadora

Contenido

Función generadora ordinaria

Aplicaciones

Determinación de la función generadora a partir de una recurrencia

Ejemplo de aplicación práctica

Otras funciones generadoras

Función generadora exponencial

Función generadora de Poisson

Serie de Lambert

Serie de Bell

Función generadora de la serie de Dirichlet

Funciones generadoras de sucesiones polinómicas

Ejemplos

Funciones generadoras ordinarias

Función generadora exponencial

Serie de Bell

Función generadora de la serie de Dirichlet

Aplicaciones

Otras funciones generadoras

Véase también

Referencias

Notas

Enlaces externos

Mira otros diccionarios:

Compartir el artículo y extractos

Link directo