Generating Function

In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about arrays of numbers indexed by several 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 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 power 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 power series as its Taylor series; this explains the designation "generating functions". However such interpretation is not required to be possible, because formal power 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 power series; negative and fractional powers of x are examples of this.

Generating functions are not functions in the formal sense of a mapping from a domain to a codomain; the name is merely traditional, and they are sometimes more correctly called generating series.

Read more about Generating Function:  Definitions, Ordinary Generating Functions, Examples, Applications, Other Generating Functions, Similar Concepts

Other articles related to "generating function, function, generating functions":

Characteristic Function (probability Theory) - Related Concepts
... Related concepts include the moment-generating function and the probability-generating function ... The characteristic function exists for all probability distributions ... However this is not the case for moment generating function ...
Coupon Collector's Problem (generating Function Approach)
... The generating function approach is a combinatorial technique that allows to obtain precise results ... This technique uses the probability generating function (PGF) where is the probability that q steps are taken to collect the n coupons i.e ... The function, first simplified before deriving the expectation, can be expressed as follows ...
Stirling Numbers And Exponential Generating Functions - Stirling Numbers of The First Kind
... Translating to generating functions we obtain the mixed generating function of the unsigned Stirling numbers of the first kind Now the signed Stirling numbers of the first kind are obtained from ...
Catalog Of Articles In Probability Theory - Core Probability: Selected Topics - Moments (mnt)
... moment / (1R) Coefficient of variation / (1R) Correlation / (2R) Correlation function / (UR) Covariance / (2FR) (1G) Covariance function / (UR) Covariance matrix / (FR) Cumulant / (12FDCR) Factorial moment ...

Famous quotes containing the word function:

    Science has fulfilled her function when she has ascertained and enunciated truth.
    Thomas Henry Huxley (1825–95)