Generating Function · aiwiki.page

A generating function is a mathematical expression that represents a sequence by placing its terms in the coefficients of a series. The most common form associates a sequence $a_0,a_1,a_2,\ldots$ with the power series $A(z)=\sum_{n\ge0}a_nz^n$ . Operations on this single expression translate into operations on the sequence, making generating functions important tools in combinatorics, probability theory, and the analysis of algorithms. Depending on the purpose, the series can be treated as a purely formal algebraic object or as a convergent function. (aofa.cs.princeton.edu)

Definition and interpretation

The ordinary generating function (OGF) of a sequence is

A(z)=\sum_{n=0}^{\infty}a_nz^n.

The notation $[z^n]A(z)$ means “the coefficient of $z^n$ in $A(z)$ ,” so that $[z^n]A(z)=a_n$ . For a counting sequence, the exponent records an object's size and the coefficient records how many objects have that size. A finite sequence gives a polynomial, with subsequent coefficients understood to be zero. (aofa.cs.princeton.edu)

For example, the sequence $1,1,1,\ldots$ has generating function

1+z+z^2+\cdots=\frac{1}{1-z},

using the geometric series identity. Likewise,

\sum_{n\ge0}nz^n=\frac{z}{(1-z)^2}.

These compact expressions retain every coefficient of the original sequences. (aofa.cs.princeton.edu)

Formal and analytic viewpoints

A formal power series is specified by its coefficients, without requiring numerical convergence. Equality means coefficient-by-coefficient equality. Over a field, a formal series has a multiplicative inverse precisely when its constant coefficient is nonzero. Thus $1/(1-z)$ is meaningful formally, independently of whether a numerical value is assigned to $z$ . (math.cmu.edu)

The distinction matters for rapidly growing sequences. The series

\sum_{n\ge0}n!z^n

has radius of convergence zero, but remains a valid formal generating function. If a series does converge near zero, methods of complex analysis become available, including coefficient extraction through contour integration and estimates based on singularities. (math.cmu.edu)

Algebraic operations

Let $A(z)=\sum a_nz^n$ and $B(z)=\sum b_nz^n$ . Their operations have direct coefficient interpretations:

Operation	Coefficient interpretation
$A(z)+B(z)$	Termwise addition: $a_n+b_n$
$z^rA(z)$ , $r\ge0$	Shift by $r$ positions, inserting initial zeros
$A(z)B(z)$	$\displaystyle c_n=\sum_{k=0}^{n}a_kb_{n-k}$
$zA'(z)$	Weight the $n$ -th term by $n$
$\displaystyle A(z)/(1-z)$	Partial sums: $\displaystyle s_n=\sum_{k=0}^{n}a_k$

Multiplication therefore implements discrete convolution, while taking a derivative implements index-dependent weighting. These rules explain why relations involving sums and shifts often become simpler equations for generating functions. (math.cmu.edu)

Main types

Exponential generating functions

The exponential generating function (EGF) of a sequence is

E(z)=\sum_{n\ge0}a_n\frac{z^n}{n!}, \qquad a_n=n![z^n]E(z),

where $n!$ is the factorial. For the constant sequence $a_n=1$ , the EGF is the exponential function $e^z$ , rather than $1/(1-z)$ . (aofa.cs.princeton.edu)

EGFs are especially useful for counting structures on distinct labels. Their product encodes

c_n=\sum_{k=0}^{n}\binom{n}{k}a_kb_{n-k}.

The binomial coefficient chooses which $k$ labels belong to the first component. This distinguishes labelled products from ordinary products, which do not include that allocation factor. (aofa.cs.princeton.edu)

Multivariate generating functions

A generating function can record several parameters:

A(z,u)=\sum_{n,k\ge0}a_{n,k}z^nu^k.

Here $z$ might mark size and $u$ a secondary statistic, such as the number of leaves in a tree. When the substitution is well-defined, $A(z,1)$ counts objects by size alone. Differentiating with respect to $u$ weights objects by their secondary statistic, allowing averages and higher moments to be recovered. (ac.cs.princeton.edu)

Other generating series

Other coefficient encodings suit different operations. A Dirichlet generating series,

D(s)=\sum_{n\ge1}\frac{a_n}{n^s},

is useful in number theory because multiplication combines indices through divisors rather than addition:

c_n=\sum_{d\mid n}a_db_{n/d}.

Choosing a generating series is therefore partly a choice of which sequence operations should become multiplication, differentiation, or another simple transformation. (math.cmu.edu)

Solving recurrence relations

Generating functions turn many recurrence relations into algebraic or differential equations. The usual procedure is to multiply the recurrence by $z^n$ , sum over its valid indices, account for initial terms, and solve the resulting equation. (aofa.cs.princeton.edu)

For the Fibonacci sequence, take

F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\ge2).

Writing $F(z)=\sum_{n\ge0}F_nz^n$ gives

F(z)-z=zF(z)+z^2F(z),

hence

F(z)=\frac{z}{1-z-z^2}.

Factoring the denominator and expanding its partial fractions yields an explicit expression for $F_n$ . The initial conditions are essential: the recurrence alone does not determine the numerator. (math.mit.edu)

Counting combinatorial structures

Generating functions express ways of building objects. Disjoint alternatives correspond to addition; ordered pairs of components, with sizes added, correspond to multiplication. If $A(z)$ counts components and $A(0)=0$ , arbitrary finite sequences of components have generating function

1+A(z)+A(z)^2+\cdots=\frac{1}{1-A(z)}.

The condition excludes zero-size components, which could otherwise produce infinitely many sequences of a fixed size. (aofa.cs.princeton.edu)

A classical example is the Catalan numbers, which count ordered full binary trees by their number of internal nodes. A tree is either a single leaf or an internal root with two subtrees, giving

C(z)=1+zC(z)^2.

Selecting the solution with constant coefficient $1$ gives

C(z)=\frac{1-\sqrt{1-4z}}{2z}, \qquad C_n=\frac{1}{n+1}\binom{2n}{n}.

The first coefficients are $1,1,2,5,14,\ldots$ . This illustrates how a recursive structural description becomes an equation and then a counting formula. (aofa.cs.princeton.edu)

Probability generating functions

For a random variable $X$ taking nonnegative integer values, its probability generating function is

G_X(z)=\mathbb E[z^X] =\sum_{n\ge0}\Pr(X=n)z^n.

Its coefficients form the probability mass function. For a binomial distribution with parameters $m$ and $p$ ,

G_X(z)=(1-p+pz)^m.

The coefficient of $z^k$ is the probability of exactly $k$ successes. (math.mit.edu)

Differentiation generates factorial moments:

G_X^{(r)}(1^-) =\mathbb E[X(X-1)\cdots(X-r+1)].

When the relevant moments are finite, the mean and variance follow from

\mathbb E[X]=G_X'(1^-),

\operatorname{Var}(X) =G_X''(1^-)+G_X'(1^-)-\bigl(G_X'(1^-)\bigr)^2.

Generating-function representations also support exact inference for some discrete probabilistic models. (math.cmu.edu)

Analytic methods and limitations

Analytic combinatorics connects structural counting equations with analytic properties of their generating functions. Singularities can determine both exponential growth and polynomial corrections in the coefficients. For example, the square-root singularity in the Catalan generating function leads to

C_n\sim\frac{4^n}{\sqrt{\pi}\,n^{3/2}}.

Here $\sim$ means that the ratio of the two expressions tends to $1$ . General singularity-transfer results require appropriate analyticity conditions; knowing only the radius of convergence is not enough to determine a full asymptotic formula. (aofa.cs.princeton.edu)

Encoding a sequence does not guarantee an easily usable closed form. An equation for its generating function may be harder to solve than the original recurrence, and extracting coefficients can remain difficult. Formal manipulations also do not automatically justify numerical substitutions or analytic arguments: convergence must be established separately. The usefulness of the method depends on matching the series type and its operations to the structure of the problem. (math.cmu.edu)

The modern subject combines formal series algebra, combinatorial construction rules, and complex-analytic estimates. Herbert S. Wilf's generatingfunctionology, first published in 1990, presents these techniques through sequence and counting problems; Philippe Flajolet and Robert Sedgewick's Analytic Combinatorics develops the systematic connection between combinatorial specifications and asymptotic analysis. (www2.math.upenn.edu)

References

Generating Functionsaofa.cs.princeton.edu
Generating Function Notesmath.mit.edu
generatingfunctionologymath.cmu.edu
Generating Functions lecture slidesaofa.cs.princeton.edu
Analytic Combinatoricsaofa.cs.princeton.edu
Analytic Combinatorics — Philippe Flajolet and Robert Sedgewickac.cs.princeton.edu
Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approacharxiv.org
Download generatingfunctionologywww2.math.upenn.edu