# Generating function

In mathematics, a **generating function** is a way of encoding an infinite sequence of numbers (*a*_{n}) by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. 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. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem.[1] One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of 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 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 often expressed in closed form (rather than as a series), by some expression involving operations defined for formal series. 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*. Also, 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.

Generating functions are not functions in the formal sense of a mapping from a domain to a codomain. Generating functions are sometimes called **generating series**,[2] in that a series of terms can be said to be the generator of its sequence of term coefficients.