In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression involving operations on the formal series.
There are various types of generating functions, including ordinary generating functions, exponential generating functions, Lambert series, Bell series, and Dirichlet series. Every sequence in principle has a generating function of each type (except that Lambert and Dirichlet series require indices to start at 1 rather than 0), but the ease with which they can be handled may differ considerably. The particular generating function, if any, 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 sometimes called generating series,This alternative term can already be found in E.N. Gilbert (1956), "Enumeration of Labeled graphs", Canadian Journal of Mathematics 3, p. 405–411, but its use is rare before the year 2000; since then it appears to be increasing. in that a series of terms can be said to be the generator of its sequence of term coefficients.
History Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem.
George Pólya writes in Mathematics and plausible reasoning: The name "generating function" is due to Laplace. Yet, without giving it a name, Euler used the device of generating functions long before Laplace [..]. He applied this mathematical tool to several problems in Combinatory Analysis and the Theory of Numbers.
Definition
Convergence Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers. Thus generating functions are not functions in the formal sense of a mapping from a domain to a codomain.
These expressions in terms of the indeterminate may involve arithmetic operations, differentiation with respect to and composition with (i.e., substitution into) other generating functions; since these operations are also defined for functions, the result looks like a function of . Indeed, the closed form expression can often be interpreted as a function that can be evaluated at (sufficiently small) concrete values of , and which has the formal series as its series expansion; this explains the designation "generating functions". However such interpretation is not required to be possible, because formal series are not required to give a convergent series when a nonzero numeric value is substituted for .
Limitations Not all expressions that are meaningful as functions of are meaningful as expressions designating formal series; for example, negative and fractional powers of are examples of functions that do not have a corresponding formal power series.
Types
Ordinary generating function (OGF)
When the term generating function is used without qualification, it is usually taken to mean an ordinary generating function. The ordinary generating function of a sequence is:
If is the probability mass function of a discrete random variable, then its ordinary generating function is called a probability-generating function.
Exponential generating function (EGF)
The exponential generating function of a sequence is
Exponential generating functions are generally more convenient than ordinary generating functions for combinatorial enumeration problems that involve labelled objects.
Another benefit of exponential generating functions is that they are useful in transferring linear recurrence relations to the realm of differential equations. For example, take the Fibonacci sequence that satisfies the linear recurrence relation . The corresponding exponential generating function has the form
and its derivatives can readily be shown to satisfy the differential equation as a direct analogue with the recurrence relation above. In this view, the factorial term is merely a counter-term to normalise the derivative operator acting on .
Poisson generating function The Poisson generating function of a sequence is
Lambert series
The Lambert series of a sequence is Note that in a Lambert series the index starts at 1, not at 0, as the first term would otherwise be undefined.
The Lambert series coefficients in the power series expansions for integers are related by the divisor sum The main article provides several more classical, or at least well-known examples related to special arithmetic functions in number theory. As an example of a Lambert series identity not given in the main article, we can show that for we have that
where we have the special case identity for the generating function of the divisor function, , given by
Bell series
The Bell series of a sequence is an expression in terms of both an indeterminate and a prime and is given by: pp.42–43
Dirichlet series generating functions (DGFs)
Formal Dirichlet series are often classified as generating functions, although they are not strictly formal power series. The Dirichlet series generating function of a sequence is:
The Dirichlet series generating function is especially useful when is a multiplicative function, in which case it has an Euler product expression in terms of the function's Bell series:
If is a Dirichlet character then its Dirichlet series generating function is called a Dirichlet -series. We also have a relation between the pair of coefficients in the Lambert series expansions above and their DGFs. Namely, we can prove that: if and only if where is the Riemann zeta function.
The sequence generated by a Dirichlet series generating function (DGF) corresponding to:has the ordinary generating function:
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 is a sequence of polynomials and 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.
Examples of polynomial sequences generated by more complex generating functions include:
Appell polynomials Chebyshev polynomials Difference polynomials Generalized Appell polynomials -difference polynomials
Other generating functions Other sequences generated by more complex generating functions include:
Double exponential generating functions Hadamard products of generating functions and diagonal generating functions, and their corresponding integral transformations
Convolution polynomials Knuth's article "Convolution Polynomials" defines a generalized class of convolution polynomial sequences by their special generating functions of the form
for some analytic function with a power series expansion such that .
We say that a family of polynomials, , forms a convolution family if and if the following convolution condition holds for all , and for all :
We see that for non-identically zero convolution families, this definition is equivalent to requiring that the sequence have an ordinary generating function of the first form given above.
A sequence of convolution polynomials defined in the notation above has the following properties:
The sequence is of binomial type Special values of the sequence include and , and For arbitrary (fixed) , these polynomials satisfy convolution formulas of the form
For a fixed non-zero parameter , we have modified generating functions for these convolution polynomial sequences given by
where is implicitly defined by a functional equation of the form . Moreover, we can use matrix methods (as in the reference) to prove that given two convolution polynomial sequences, and , with respective corresponding generating functions, and , then for arbitrary we have the identity
Examples of convolution polynomial sequences include the binomial power series, , so-termed tree polynomials, the Bell numbers, , the Laguerre polynomials, and the Stirling convolution polynomials.
Ordinary generating functions
Examples for simple sequences
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 fundamental generating function is that of the constant sequence , whose ordinary generating function is the geometric series
The left-hand side is the Maclaurin series expansion of the right-hand side. Alternatively, the equality 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 except the one of are equal to 0). Moreover, there can be no other power series with this property. The left-hand side therefore designates the multiplicative inverse of in the ring of power series.
Expressions for the ordinary generating function of other sequences are easily derived from this one. For instance, the substitution gives the generating function for the geometric sequence for any constant :
(The equality also follows directly from the fact that the left-hand side is the Maclaurin series expansion of the right-hand side.) In particular,
One can also introduce regular gaps in the sequence by replacing by some power of , so for instance for the sequence (which skips over ) one gets the generating function
By squaring the initial generating function, or by finding the derivative of both sides with respect to and making a change of running variable , one sees that the coefficients form the sequence , so one has
and the third power has as coefficients the triangular numbers whose term is the binomial coefficient , so that
More generally, for any non-negative integer and non-zero real value , it is true that
Since
one can find the ordinary generating function for the sequence of square numbers by linear combination of binomial-coefficient generating sequences:
We may also expand alternately to generate this same sequence of squares as a sum of derivatives of the geometric series in the following form:
By induction, we can similarly show for positive integers that v4 eq. (0.4)
where denote the Stirling numbers of the second kind and where the generating function
so that we can form the analogous generating functions over the integral th powers generalizing the result in the square case above. In particular, since we can write
we can apply a well-known finite sum identity involving the Stirling numbers to obtain that for finite sum identities involving the Stirling number triangles.
Rational functions
The ordinary generating function of a sequence can be expressed as a rational function (the ratio of two finite-degree polynomials) if and only if the sequence is a linear recursive sequence with constant coefficients; this generalizes the examples above. Conversely, every sequence generated by a fraction of polynomials satisfies a linear recurrence with constant coefficients; these coefficients are identical to the coefficients of the fraction denominator polynomial (so they can be directly read off). This observation shows it is easy to solve for generating functions of sequences defined by a linear finite difference equation with constant coefficients, and then hence, for explicit closed-form formulas for the coefficients of these generating functions. The prototypical example here is to derive Binet's formula for the Fibonacci numbers via generating function techniques.