Función generadora

En matemáticas, una función generadora o función ge- Su función generadora es

neratriz es una serie formal de potencias cuyos coeficien-
tes codifican información sobre una sucesión an cuyo ín- F (x) = x
1−x−x2
dice corre sobre los enteros no negativos.
Hay varios tipos de funciones generadoras: funciones ge- puesto que el desarrollo en serie de potencias
neradoras ordinarias, funciones generadoras expo- de tal función es
nenciales, la serie de Lambert, la serie de Bell y la serie
de Dirichlet; de las cuales abajo se ofrecen definiciones
= 0 + 1 · x + 1 · x2 + 2x3 + 3x4 +
x
y ejemplos. Cada sucesión tiene una función generadora 1−x−x2

de cierto tipo. El tipo de función generadora que es apro- 5x + 8x + 13x7 + · · · .

5 6

piada en un contexto dado depende de la naturaleza de la

sucesión y los detalles del problema que se analiza. y los coeficientes de tal desarrollo son precisa-
mente 0,1,1,2,3,5,8,13,...
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 Es posible definir funciones generadoras sobre varias va-
cuenta que las funciones generadoras son series formales riables. Por ejemplo, la función generadora ordinaria en 2
de potencias, por lo que no se considera ni se analiza el variables de (am,n) donde n y m son índices que recorren
problema de la convergencia en todos los valores de x. los enteros no negativos, es
Por lo mismo es importante observar que las funciones ∑∞
generadoras no son realmente funciones en en el sentido A(x, y) = m,n=0 am,n xm y n = a0,0 +
usual de ser mapeos entre un dominio y un codominio; el a1,0 x + a0,1 y + a2,0 x2 + a1,1 xy + a0,2 y 2 +
nombre es únicamente el resultado del desarrollo históri- a3,0 x3 + a2,1 x2 y + · · ·
co de su estudio.

Una función generadora es una cuerda de 1 Aplicaciones

tender en la que colgamos una sucesión de
números para mostrarla Si bien las funciones generadoras son una herramienta
Herbert Wilf[1] 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
0.1 Función generadora ordinaria pueden ser modificadas y adaptadas en las diferentes si-
tuaciones que se presentan. A continuación se ilustran va-
La función generadora ordinaria de una sucesión (an) = rios usos de las funciones generadoras junto con la idea
a0 , a1 , a2 , a3 ... se define como general que se está usando.

∑∞
A(x) = an xn = a0 +a1 x+a2 x2 +
n=0 1.1 Determinación de la función generado-
a3 x3 + · · ·
ra a partir de una recurrencia
Es común usar la expresión función generadora sin mayor
En esta situación lo que se hace es multiplicar ambos la-
calificativo, para referirse a este tipo de función.
dos de la recurrencia por xn y sumar sobre todos los ín-
dices. Después se efectúan transformaciones para que la
Ejemplo. La sucesión de Fibonacci definida por la recu-
igualdad entre sumas que se obtiene se convierta en una
rrencia
ecuación que involucra la función generadora y se proce-
de a resolverla.
fn+1 = fn + fn−1 , n > 0, f0 =
0, f1 = 1 Como ilustración, considere la recurrencia

es la sucesión 0,1,1,2,3,5,8,13,21,... an+1 = 3an + 2, a0 = 1 .

1
2 2 OTRAS FUNCIONES GENERADORAS

que da origen a la sucesión y que corresponen a usar a monedas de 1 peso, b monedas

(an)=1,5,17,53,161,485,1457... de 2 pesos y c monedas de 5 pesos.
Multiplicando ambos lados por xn y sumando sobre todos La aplicación de la fórmula de Taylor es demasiado com-
los valores de n se obtiene: pleja en este caso, por lo que aplicaremos el siguiente ar-
tificio debido a Ronald Graham.
∑∞ n 2
n=0 an+1 ∑x∞ = a1 + a2 x + a3 x + Cada uno de los denominadores (1-x), (1-x2 ) y (1-x5 ) son
a4 x3 + · · · = n=0 (3an + 2)xn . divisores de (1-x10 ), por lo que podemos reescribir
A(x)
El lado izquierdo es casi la función generadora, pero los C(x) = (1−x10 )3
índices están desfasados. Pero notando que
para un A(x) en donde:
a1 + a2 x + a3 x + a4 x + · · · =
2 3 ( 10
)( )(
1−x10 1−x1
(a0 +a1 x+a2 x2 +a3 x3 +··· )−a0 A(x) = A1 (x) · A2 (x) · A3 (x) = 1−x1−x 1−x 2 1−x5
x , 22 21 20 19 18 17 16
= x + x + 2x + 2x + 3x + 4x + 5x +
+7x10 + 8x9 + 7x8 + 6x7 + 5x6 + 4x5 + 3x4 +
se deduce que el lado izquierdo es
Finalmente, desarrollando la función generadora
A(x)−a0
= A(x)−1
. ∑ (2+k) 10k ()
x x 1
10 )3 = k x = 22 +
(3) (1−x () ()
k≥0

2 x
10
+ 42 x20 + 52 x30 + · · ·
El lado derecho se desarrolla como

∑∞ ∑∞ obtenemos
n n
∑∞ n=0n(3an + 2)x = 3 k=02an x 3 + ∑ (2+k) 10k
2 k=0 x = 3A(x) + 2(1 + x + x + x + C(x) = A(x) k≥0 k x .
· · · ) = 3A(x) + 1−x
2
.
De la expresión anterior se puede leer con detalle el valor
n
Al final, se aplicó la fórmula para sumar una serie exacto del coeficiente de x , es decir, el número cn de
geométrica:[2] 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 x77 :
1 + x + x2 + x3 + x4 + · · · = 1−x1
.
() ()
(6x7 ) · 92 x70 + (4x17 ) · 82 x60 =
( (9) (8)) 77
Igualando ambas simplificaciones, se obtiene la ecuación 6 2 + 4 2 x = (6 · 36 + 4 · 28)x77 =
328x77
A(x)−1 2
= 3A(x) + 1−x ,
x y se concluye que hay 328 formas de pagar 77 pesos con
monedas de 1, 2 o 5 pesos.
que al resolverse arroja por resultado

A(x) = x+1
3x2 −4x+1 .
2 Otras funciones generadoras

2.1 Función generadora exponencial

1.2 Ejemplo de aplicación práctica
La función generadora exponencial de una sucesión an es
Si cn es el número de formas en que se puede pagar n pe-
sos usando monedas de 1, 2 y 5 pesos, entonces la función
generadora de la sucesión (cn) es ∞
∑ xn
EG(an ; x) = an .
n=0
n!
C(x) = 1−x 1
· 1−x
1
2 · 1−x5 = (1 + x +
1

x + x + · · · )(1 + x + x + x6 + · · · )(1 +
2 3 2 4

x5 + x10 + x15 + · · · ) . 2.2 Función generadora de Poisson

La función generadora de Poisson de una sucesión an es
ya que el coeficiente de xn es igual al número de formas
de escoger a, b, c tales que
∞
∑ xn
P G(an ; x) = an e−x .
xn = xa x2b x5c = xa+2b+5c , n=0
n!
 3

2.3 Serie de Lambert donde pn(x) es una sucesión de polinomios y f(t) es

una función de cierta forma. Las sucesiones de Sheffer
La serie de Lambert de una sucesión an es se generan de modo similar. Véase el artículo principal
polinomio generalizado de Appell para más información.
∞
∑ xn
LG(an ; x) = an .
n=1
1 − xn 3 Ejemplos
Nótese que en una serie de Lambert, el índice n comienza Cuando se trabaja con funciones generadoras, es im-
en el 1, no en 0. portante reconocer las expresiones de algunas sucesiones
fundamentales.
2.4 Serie de Bell
3.1 Funciones generadoras ordinarias
La serie de Bell de una función aritmética f(n) y un
número primo p es La más fundamental de todas es la sucesión constante
1,1,1,1,..., cuya función generadora ordinaria es
∞
∑
fp (x) = f (pn )xn . ∑ 1
n=0 Xn = .
1−X
n∈N

2.5 Función generadora de la serie de Di- La expresión de la derecha se puede justificar multipli-
richlet cando la serie de potencias de la izquierda por X − 1 ,
y comprobando que su resultado sea la serie constante de
Las series de Dirichlet a menudo se clasifican como fun- potencias 1; en otras palabras, que todos los coeficientes
ciones generadoras, aunque no son estrictamente series desaparezcan excepto el de X0 . (Por lo demás, no pue-
formales de potencias. La función generadora de la serie de haber otra serie de potencias con esta propiedad, ya
de Dirichlet de una sucesión an es que un anillo de series de potencias como Z[[X]] es un
dominio de integridad.) El lado de la derecha, por lo tan-
to, designa la inversa de X − 1 en el anillo de series de
∑∞
an potencias.
DG(an ; s) = .
ns Fácilmente se derivan para ésta expresiones para la ge-
n=1
neración ordinaria de otras sucesiones. Por ejemplo, para
La función generadora de la serie de Dirichlet es espe- la serie geométrica 1,a,a2 ,a3 ,... para cada constante a se
cialmente útil cuando an es una función multiplicativa, tiene
cuando tiene una expresión de producto de Euler en tér-
minos de la serie de Bell de la función ∑ 1
an X n = ,
1 − aX
∏ n∈N
DG(an ; s) = fp (p−s ) .
y en particular
p

Si an es un carácter de Dirichlet, entonces su función ge- ∑ 1

neradora de la serie de Dirichlet se llama serie L de Di- (−1)n X n = .
richlet. 1+X
n∈N

También se pueden introducir «brechas» regulares en la

2.6 Funciones generadoras de sucesiones 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
polinómicas
función generadora
El concepto de funciones generadoras puede extenderse
a sucesiones de otros objetos. Así, por ejemplo, las suce- ∑ 1
siones polinómicas de tipo binomial se generan por X 2n = .
1 − X2
n∈N

∞
Calculando el cuadrado de la función generadora inicial,
∑ pn (x) n
e xf (t)
= t fácilmente se ve que los coeficientes forman la sucesión
n=0
n! 1,2,3,4,5,..., así que se tiene
4 7 REFERENCIAS

• encontrar relaciones entre sucesiones: si las funcio-

∑ nes generadoras de dos sucesiones tienen una for-
1
(n + 1)X n = , ma similar, entonces las propias sucesiones proba-
(1 − X)2
n∈N blemente están relacionadas;
y el cubo tiene como coeficientes los números triangu- • explorar el comportamiento asintótico de las suce-
lares 1,3,6,10,15,21,...
( ) cuyo término n es el coeficiente siones;
binomial n+2 2 , de manera que
• demostrar identidades que implican sucesiones;
∑( ) n 1 • resolver problemas de enumeración en
n+2
X = . combinatoria;
2 (1 − X)3
n∈N
( ) • evaluar sumas infinitas.
Dado que n+2 2 = 12 (n + 1)(n + 2) = 21 (n2 + 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; 5 Otras funciones generadoras
Ejemplos de sucesiones polinómicas generadas por fun-
∞
∑ 2 3 1 ciones
x(x + generadoras
1) más complejas son:
G(n2 ; x) = n2 xn = − + = .
n=0
(1 − x) (1 − x) 1 − x
3 2 (1 − x) 3

• Difference polynomials

3.2 Función generadora exponencial • Generalized Appell polynomials

• Q-difference polynomials

∑∞
n2 x n
EG(n2 ; x) = = x(x + 1)ex
n=0
n! 6 Véase también

3.3 Serie de Bell • Función generadora de momentos

• Función generadora de probabilidad

∞
∑ • Teorema de reciprocidad de Stanley
1
fp (x) = p2n xn =
n=0
1 − p2 x • Aplicaciones a particiones.

3.4 Función generadora de la serie de Di-

richlet
7 Referencias
• Herbert S. Wilf, Generatingfunctionology (Second
Edition) (1994) Academic Press. ISBN 0-12-
∑∞
n2 751956-4.
2
DG(n ; s) = = ζ(s − 2)
ns
n=1
• Donald E. Knuth, The Art of Computer Program-
ming, Volume 1 Fundamental Algorithms (Third Edi-
4 Aplicaciones tion) Addison-Wesley. ISBN 0-201-89683-4. Sec-
tion 1.2.9: Generating Functions, pp.87–96.

Las funciones generadoras se emplean para • Ronald L. Graham, Donald E. Knuth, y Oren Pa-
tashnik, Concrete Mathematics. A foundation for
• encontrar una forma cerrada para una sucesión dada computer science (Second Edition) Addison-Wesley.
en una relación de recurrencia. Por ejemplo, consi- ISBN 0-201-55802-5. Chapter 7: Generating Fun-
dérense los números de Fibonacci; ctions, pp. 320–380.

• encontrar relaciones de recurrencia para sucesiones: • Gabriel Poveda Ramos, Funciones generatrices, Edi-
la forma de una función generadora puede sugerir torial de la Universidad Pontificia Bolivariana, ISBN
una fórmula de recurrencia; 958-696-539-2, 90 pp., Medellín (Colombia) 2006.
 5

8 Notas
[1] Wilf, Herbert (1994). generatingfunctionology (2.ª edi-
ción). A. K. Peters. ISBN 978-1-56881-279-3.

[2] Como se mencionó en la introducción, realmente no im-

porta el radio de convergencia de una serie, ya que sólo se
busca manipular formalmente (es decir, «mecánicamen-
te») las expresiones. En general es suficiente que una serie
sea convergente en un disco abierto (no determinado) al-
rededor de cero para poder usarla. En el ejemplo, la serie
geométrica es convergente en el disco −1<x<1.

9 Enlaces externos
• Funciones generadoras, índices de potencias y cam-
bio de moneda (en inglés) en Cut-the-knot.org (con-
sultado el 1 de agosto de 2008)
• Versión descargable en inglés de Generatingfunctio-
nology, de H. Wilf (consultado el 1 de agosto de
2008)

• 1031 Generating Functions (consultado el 1 de agos-

to de 2008)

• Ignacio Larrosa Cañestro, León-Sotelo, Marko Rie-

del, Georges Zeller, Suma de números equilibrados,
newsgroup es.ciencia.matemáticas
• Frederick Lecue; Riedel, Marko, et al., Permutation,
Les-Mathematiques.net, en francés (el título des-
orienta un tanto)

• “Generating Functions” por Ed Pegg, Jr., en el sitio

web The Wolfram Demonstrations Project, 2007.
(consultado el 1 de agosto de 2008)
6 10 TEXTO E IMÁGENES DE ORIGEN, COLABORADORES Y LICENCIAS

10 Texto e imágenes de origen, colaboradores y licencias

10.1 Texto
• Función generadora Fuente: https://es.wikipedia.org/wiki/Funci%C3%B3n_generadora?oldid=79375387 Colaboradores: Magister Mat-
hematicae, GermanX, Folkvanger, CEM-bot, JAnDbot, Muro de Aguas, TXiKiBoT, VolkovBot, Muro Bot, SieBot, Drinibot, DragonBot,
Neodop, Botellín, Alexbot, Juan Mayordomo, LucienBOT, Louperibot, Fernando H, Arjuno3, Luckas-bot, Nallimbot, Jkbw, FrescoBot,
Ricardogpn, Albert.granados, TobeBot, Jerowiki, ZéroBot, Alberto Leguiza, KLBot2, Makecat-bot, Addbot y Anónimos: 2

10.2 Imágenes

10.3 Licencia de contenido

• Creative Commons Attribution-Share Alike 3.0