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, 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 A generating function is a device somewhat similar to a bag. Instead of carrying many little objects detachedly, which could be embarrassing, we put them all in a bag, and then we have only one object to carry, the bag. A generating function is a clothesline on which we hang up a sequence of numbers for display.
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 x may involve arithmetic operations, differentiation with respect to x 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 x. Indeed, the closed form expression can often be interpreted as a function that can be evaluated at (sufficiently small) concrete values of x, 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 x.
Limitations Not all expressions that are meaningful as functions of x are meaningful as expressions designating formal series; for example, negative and fractional powers of x 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 an is:
G ( a n ; x ) = ∑ n = 0 ∞ a n x n . {\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}
If an 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 an is
EG ( a n ; x ) = ∑ n = 0 ∞ a n x n n ! . {\displaystyle \operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.}
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 {fn} that satisfies the linear recurrence relation fn+2 = fn+1 + fn. The corresponding exponential generating function has the form
EF ( x ) = ∑ n = 0 ∞ f n n ! x n {\displaystyle \operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}}
and its derivatives can readily be shown to satisfy the differential equation EF″(x) = EF′(x) + EF(x) as a direct analogue with the recurrence relation above. In this view, the factorial term n! is merely a counter-term to normalise the derivative operator acting on xn.
Poisson generating function The Poisson generating function of a sequence an is
… excerpt ends here. Continue reading the full article.
