Other meanings of Generating function
MATHEMATICS
A generating function encodes a sequence as the coefficients of a power series, converting questions about discrete objects into algebraic, analytic, or differential operations. For a sequence a₀, a₁, a₂, …, its ordinary generating function is A(x) = ∑ₙ≥₀ aₙxⁿ. The coefficient of xⁿ records aₙ, while products, substitutions, and derivatives can express counting constructions and recurrence relations compactly.
A generating function represents a sequence by placing its terms beside successive powers of an indeterminate. The ordinary generating function of (aₙ) is A(x) = ∑ₙ≥₀ aₙxⁿ, and coefficient extraction recovers the sequence through aₙ = [xⁿ]A(x).1 The indeterminate x need not initially be assigned a numerical value: in enumerative combinatorics, the series may be treated as a formal power series, where convergence is irrelevant.
Several variants suit different data. An exponential generating function is ∑ₙ≥₀ aₙxⁿ/n!, which is particularly effective when labeled objects or factorial factors occur. A probability generating function uses ∑ₙ≥₀ P(X=n)xⁿ for a nonnegative integer-valued random variable and encodes probabilities and moments. Multivariate generating functions track several statistics at once, while Laurent and Dirichlet series extend the idea to negative powers or powers indexed by arithmetic structure.
Generating functions turn common operations on sequences into simple algebraic operations. Termwise addition adds sequences, multiplication forms convolution, and multiplication by x shifts coefficients; differentiation introduces factors of n. Thus the product A(x)B(x) has coefficient [xⁿ] equal to ∑ₖ₌₀ⁿ aₖbₙ₋ₖ, the discrete convolution of the two sequences.2
A linear recurrence relation often becomes an equation for its generating function. For the Fibonacci numbers, Fₙ₊₂ = Fₙ₊₁ + Fₙ gives F(x) = x/(1 − x − x²) under the usual initial conditions. Rational generating functions correspond to sequences satisfying constant-coefficient linear recurrences; conversely, solving the recurrence can yield a rational or algebraic expression whose coefficients provide the desired formula.1
Generating functions organize combinatorial constructions by marking size with powers of x. If objects are formed by choosing independently from two classes, multiplication reflects the combination; a sequence of choices is represented by a geometric-series factor. This principle produces generating functions for Catalan numbers, integer partitions, walks, trees, tilings, and many other families, often after translating a structural decomposition into an equation.3
When a series is regarded as an analytic function, its singularities control coefficient growth. The location and type of the nearest singularity can reveal exponential rates and polynomial corrections, forming the basis of analytic combinatorics.4 In probability, derivatives of a probability generating function at x = 1 yield factorial moments when they exist; products also represent sums of independent nonnegative integer-valued random variables.5
Generating functions are not limited to convergent power series or to one-dimensional sequences. Formal manipulation permits division by a series with nonzero constant term, implicit equations, and coefficient extraction even when every numerical substitution would diverge. The same coefficient may be obtained by algebraic identities, contour integrals, or recurrence algorithms, linking combinatorics with complex analysis and symbolic computation.1
Less familiar forms include signed and weighted generating functions, where cancellation or a variable marking a statistic is deliberate; diagonal generating functions, obtained by selecting coefficients such as [xⁿyⁿ]; and the partition function of statistical mechanics, which is a generating object for weighted states rather than merely an unweighted count. In computer algebra, coefficient extraction can be automated, but compact closed forms may conceal substantial cancellation or have a smaller domain of analytic validity than their formal interpretation.
Notation varies by field: some authors begin sequences at n = 1, and some use the term generating function broadly for exponential, probability, Dirichlet, or multivariate forms.
Help improve the encyclopedia. Reports go straight to the site manager.