Generating function: Definition from Answers.com

This article is about generating functions in mathematics. For generating functions in classical mechanics, see Generating function (physics). For signalling molecule, see Epidermal growth factor.

In mathematics, a generating function is a formal power series whose coefficients encode information about a sequence a_n 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.

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.

Definitions

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 a_n is

$G(a_n;x)=\sum_{n=0}^{\infty}a_nx^n.$

When the term generating function is used without qualification, it is usually taken to mean an ordinary generating function.

If a_n 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 a_{m, n} (where n and m are natural numbers) is

$G(a_{m,n};x,y)=\sum_{m,n=0}^{\infty}a_{m,n}x^my^n.$

Exponential generating function

The exponential generating function of a sequence a_n is

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

Poisson generating function

The Poisson generating function of a sequence a_n is

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

Lambert series

The Lambert series of a sequence a_n is

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

Note that in a Lambert series the index n starts at 1, not at 0.

Bell series

The Bell series of an arithmetic function f(n) and a prime p is

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

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 a_n is

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

The Dirichlet series generating function is especially useful when a_n is a multiplicative function, when it has an Euler product expression in terms of the function's Bell series

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

If a_n 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

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

where p_n(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.

Ordinary generating functions

Polynomials are a special case of ordinary generating functions, corresponding to finite sequences, or equivalently sequences that vanish after a certain point. These are important in that many finite sequences can usefully be interpreted as generating functions, such as the Poincaré polynomial, and others.

A key generating function is the constant sequence 1, 1, 1, 1, 1, 1, 1, 1, 1, ..., whose ordinary generating function is

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

The right hand side expression can be justified by multiplying the power series on the left by 1 − X, and checking that the result is the constant power series 1, in other words that all coefficients vanish, except the one of X⁰. Moreover there can be no other power series with this property. The right hand side therefore designates the inverse of 1 − X 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,a²,a³,... for any constant a one has

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

and in particular

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

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

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

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

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

and the third power has as coefficients the triangular numbers 1, 3, 6, 10, 15, 21, ... whose term n is the binomial coefficient $\tbinom{n+2}2$ , so that

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

Since

$\binom{n+2}2=\frac12{(n+1)(n+2)} =\frac12(n^2+3n+2),$

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;

$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}.$

Rational functions

Main article: Linear recursive sequence

The ordinary generating function of a sequence can be expressed as a rational function (the ratio of two polynomials) if and only if the sequence is a linear recursive sequences; this generalizes the examples above.

Multiplication is convolution

Main article: Cauchy product

Multiplication of ordinary generating functions yields a discrete convolution (the Cauchy product) of the series.

Bivariate generating functions

One can define generating functions in several variables, for series with several indices. These are often called super generating functions, and for 2 variables are often called bivariate generating functions.

For instance, since $(1 + x) n$ is the ordinary generating function for binomial coefficients for a fixed n, one may ask for a bivariate generating function that generates the binomial coefficients $\binom{n}{k}$ for all k and n. To do this, consider $(1 + x) n$ as itself a series (in n), and find the generating function in y that has these as coefficients. Since the generating function for $a n$ is just $1 / (1 - a y)$ , the generating function for the binomial coefficients is:

$\frac{1}{1-(1+x)y}=1+(1+x)y+(1+x)^2y^2+\dots,$

and the coefficient on $x k y n$ is the $\binom{n}{k}$ binomial coefficient.