TOPICS
Search

Generating Function


A generating function f(x) is a formal power series

 f(x)=sum_(n=0)^inftya_nx^n
(1)

whose coefficients give the sequence {a_0,a_1,...}.

The Wolfram Language command GeneratingFunction[expr, n, x] gives the generating function in the variable x for the sequence whose nth term is expr. Given a sequence of terms, FindGeneratingFunction[{a1, a2, ...}, x] attempts to find a simple generating function in x whose nth coefficient is a_n.

Given a generating function, the analytic expression for the nth term in the corresponding series can be computing using SeriesCoefficient[expr, {x, x0, n}]. The generating function f(x) is sometimes said to "enumerate" a_n (Hardy 1999, p. 85).

Generating functions giving the first few powers of the nonnegative integers are given in the following table.

n^pf(x)series
1x/(1-x)x+x^2+x^3+...
nx/((1-x)^2)x+2x^2+3x^3+4x^4+...
n^2(x(x+1))/((1-x)^3)x+4x^2+9x^3+16x^4+...
n^3(x(x^2+4x+1))/((1-x)^4)x+8x^2+27x^3+...
n^4(x(x+1)(x^2+10x+1))/((1-x)^5)x+16x^2+81x^3+...

There are many beautiful generating functions for special functions in number theory. A few particularly nice examples are

f(x)=1/((x)_infty)
(2)
=sum_(n=0)^(infty)P(n)x^n
(3)
=1+x+2x^2+3x^3+...
(4)

for the partition function P, where (q)_infty is a q-Pochhammer symbol, and

f(x)=x/(1-x-x^2)
(5)
=sum_(n=0)^(infty)F_nx^n
(6)
=x+x^2+2x^3+3x^4+...
(7)

for the Fibonacci numbers F_n.

Generating functions are very useful in combinatorial enumeration problems. For example, the subset sum problem, which asks the number of ways c_(m,s) to select m out of M given integers such that their sum equals s, can be solved using generating functions.

The generating function of G(t) of a sequence of numbers f(n) is given by the Z-transform of f(n) in the variable 1/t (Germundsson 2000).


See also

Cumulant-Generating Function, Enumerate, Exponential Generating Function, Formal Power Series, Moment-Generating Function, Recurrence Relation, Subset Sum Problem, Z-Transform Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Bender, E. A. and Goldman, J. R. "Enumerative Uses of Generating Functions." Indiana U. Math. J. 20, 753-765, 1970/1971.Bergeron, F.; Labelle, G.; and Leroux, P. "Théorie des espèces er Combinatoire des Structures Arborescentes." Publications du LACIM. Québec, Montréal, Canada: Univ. Québec Montréal, 1994.Cameron, P. J. "Some Sequences of Integers." Disc. Math. 75, 89-102, 1989.Doubilet, P.; Rota, G.-C.; and Stanley, R. P. "The Idea of Generating Function." Ch. 3 in Finite Operator Calculus (Ed. G.-C. Rota). New York: Academic Press, pp. 83-134, 1975.Germundsson, R. "Mathematica Version 4." Mathematica J. 7, 497-524, 2000.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, 1973.Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, p. 85, 1999.Lamdo, S. K. Lectures on Generating Functions. Providence, RI: Amer. Math. Soc., 2003.Leroux, P. and Miloudi, B. "Généralisations de la formule d'Otter." Ann. Sci. Math. Québec 16, 53-80, 1992.Riordan, J. Combinatorial Identities. New York: Wiley, 1979.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, 1980.Rosen, K. H. Discrete Mathematics and Its Applications, 4th ed. New York: McGraw-Hill, 1998.Sloane, N. J. A. and Plouffe, S. "Recurrences and Generating Functions." §2.4 in The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, pp. 9-10, 1995.Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, p. 63, 1996.Viennot, G. "Une Théorie Combinatoire des Polynômes Orthogonaux Généraux." Publications du LACIM. Québec, Montréal, Canada: Univ. Québec Montréal, 1983.Wilf, H. S. Generatingfunctionology, 2nd ed. New York: Academic Press, 1994.

Referenced on Wolfram|Alpha

Generating Function

Cite this as:

Weisstein, Eric W. "Generating Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GeneratingFunction.html

Subject classifications