In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers.
There are various types of generating functions, including ordinary generating functions, exponential generating functions, Lambert series, Bell series, and Dirichlet series; definitions and examples are given below. Every sequence has a generating function of each type. The particular generating function that is most useful in a given context will depend upon the nature of the sequence and the details of the problem being addressed.
Generating functions are often expressed in closed form as functions of a formal argument x. Sometimes a generating function is evaluated at a specific value of x. However, it must be remembered that generating functions are formal power series, and they will not necessarily converge for all values of x.
It is important to note that generating functions are not functions in the formal sense of a mapping from a domain to a codomain; the name merely stems from the historical study of the structures.
- A generating function is a clothesline on which we hang up a sequence of numbers for display.
- — Herbert Wilf, Generatingfunctionology (1994)
Ordinary generating function
The ordinary generating function of a sequence an is
When the term generating function is used without qualification, it is usually taken to mean an ordinary generating function.
If an is the probability mass function of a discrete random variable, then its ordinary generating function is called a probability-generating function.
The ordinary generating function can be generalized to sequences with multiple indexes. For example, the ordinary generating function of a sequence am, n (where n and m are natural numbers) is
Exponential generating function
The exponential generating function of a sequence an is
Poisson generating function
The Poisson generating function of a sequence an is
The Lambert series of a sequence an is
Note that in a Lambert series the index n starts at 1, not at 0.
The Bell series of an arithmetic function f(n) and a prime p is
Dirichlet series generating functions
Dirichlet series are often classified as generating functions, although they are not strictly formal power series. The Dirichlet series generating function of a sequence an is
The Dirichlet series generating function is especially useful when an is a multiplicative function, when it has an Euler product expression in terms of the function's Bell series
If an is a Dirichlet character then its Dirichlet series generating function is called a Dirichlet L-series.
Polynomial sequence generating functions
The idea of generating functions can be extended to sequences of other objects. Thus, for example, polynomial sequences of binomial type are generated by
where pn(x) is a sequence of polynomials and f(t) is a function of a certain form. Sheffer sequences are generated in a similar way. See the main article generalized Appell polynomials for more information.
When working with generating functions, it is important to recognise the expressions of some fundamenal sequences.
Ordinary generating functions
The most fundamental of all is the constant sequence 1,1,1,1,..., whose ordinary generating function is
The right hand side expression can be justified by multiplying the power series on the left by
, and checking that the result is the constant power series 1, in other words that all coefficients vanish, except the one of X0
. (Moreover there can be no other power series with this property, since a power series ring
is an integral domain
.) The right hand side therefore designates the inverse of
in the ring of power series.
Expressions for the ordinary generating of other sequences are easily derived for this one. For instance for the geometric series 1,a,a2,a3,... for any constant a one has
and in particular
One can also introduce regular "gaps" in the sequence by replacing X
by some power of X
, so for instance for the sequence 1,0,1,0,1,0,1,0,.... one gets the generating function
Computing the square of the initial generating function, one easily sees that the coefficients form the sequence 1,2,3,4,5,..., so one has
and the third power has as coefficients the triangular numbers
1,3,6,10,15,21,... whose term n
is the binomial coefficient
, so that
one can find the ordinary generating function for the sequence 0,1,4,9,16,... of square numbers
by linear combination of the preceding sequences;
Exponential generating function
Dirichlet series generating function
Generating functions are used to
- Find a closed formula for a sequence given in a recurrence relation. For example consider Fibonacci numbers
- Find recurrence relations for sequences – the form of a generating function may suggest a recurrence formula.
- Find relationships between sequences – if the generating functions of two sequences have a similar form, then the sequences themselves are probably related.
- Explore the asymptotic behaviour of sequences.
- Prove identities involving sequences.
- Solve enumeration problems in combinatorics.
- Evaluate infinite sums.
Other generating functions
Examples of polynomial sequences
generated by more complex generating functions include:
- Generating Functions, Power Indices and Coin Change at cut-the-knot
- Generatingfunctionology PDF download page
- 1031 Generating Functions
- 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, in French, title somewhat misleading.
- "Generating Functions" by Ed Pegg, Jr., The Wolfram Demonstrations Project, 2007.