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 an cuyo índice corre sobre los enteros no negativos.
El tipo de función generatriz 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.
En ocasiones, una función de este tipo 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 generatrices no son realmente funciones 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.
La función generadora ordinaria de una sucesión (an) = a0, a1, a2, a3 ... se define como
Es posible definir funciones generadoras sobre varias variables.
Por ejemplo, la función generadora ordinaria en 2 variables de (am,n) donde n y m son índices que recorren los enteros no negativos, es
Si bien las funciones generatrices 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.
En esta situación lo que se hace es multiplicar ambos lados de la recurrencia por xn y sumar sobre todos los índices.
que da origen a la sucesión (an)=1,5,17,53,161,485,1457... Multiplicando ambos lados por xn y sumando sobre todos los valores de n se obtiene:
El lado izquierdo es casi la función generadora, pero los índices están desfasados.
, se deduce que el lado izquierdo es
Al final, se aplicó la fórmula para sumar una serie geométrica:[2]
Igualando ambas simplificaciones, se obtiene la ecuación
que al resolverse arroja por resultado
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.
Por ejemplo, el número de formas de pagar 77 pesos se obtiene calculando el término correspondiente a x77:
y se concluye que hay 328 formas de pagar 77 pesos con monedas de 1, 2 o 5 pesos.
La serie de Bell de una función aritmética f(n) y un número primo p es Las series de Dirichlet a menudo se clasifican como funciones generatrices, aunque no son estrictamente series formales de potencias.
Así, por ejemplo, las sucesiones polinómicas de tipo binomial se generan por donde pn(x) es una sucesión de polinomios y f(t) es una función de cierta forma.
Véase el artículo principal polinomio generalizado de Appell para más información.
Cuando se trabaja con funciones generadoras, es importante reconocer las expresiones de algunas sucesiones fundamentales.
, y comprobando que su resultado sea la serie constante de potencias 1; en otras palabras, que todos los coeficientes desaparezcan excepto el de X0.
Fácilmente se derivan para ésta expresiones para la generación ordinaria de otras sucesiones.
Por ejemplo, para la serie geométrica 1,a,a2,a3,... para cada constante a se tiene y en particular 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 Calculando el cuadrado de la función generatriz inicial, fácilmente se ve que los coeficientes forman la sucesión 1,2,3,4,5,..., así que se tiene y el cubo tiene como coeficientes los números triangulares 1,3,6,10,15,21,... cuyo término n es el coeficiente binomial
, 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; Las funciones generadoras se emplean para Ejemplos de sucesiones polinómicas generadas por funciones generadoras más complejas son: