Generating Functions — Ordinary and Exponential

Generating functions encode a sequence

(a_{n})

as the coefficients of a formal power series. The ordinary generating function (OGF) is

\sum a_{n} x^{n}

; the exponential generating function (EGF) is

\sum a_{n} x^{n} / n!

. They convert combinatorial operations (sums, shifts, products, compositions) into algebraic operations, letting you solve recurrences, count structures, and prove identities. Core toolkit of combinatorics; popularized by Euler (18th c.) and Wilf's generatingfunctionology (1990).

A generating function is "a clothesline on which we hang up a sequence of numbers for display" (Wilf). Formally, given a sequence $a_{0}, a_{1}, a_{2}, \dots$ , its ordinary generating function is the formal power series $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ , and its exponential generating function is $\hat{A} (x) = \sum_{n \geq 0} a_{n} x^{n} / n!$ . They matter because combinatorial relations among sequences become closed-form algebraic relations among their generating functions: a hard counting problem becomes power-series algebra. The surprising fact is that we often never need convergence — the series is treated formally as a bookkeeping device — yet the same object can be analyzed as a genuine analytic function to extract precise asymptotics. The choice between OGF and EGF is dictated by whether the objects being counted are unlabeled (OGF) or labeled (EGF).

The Core Insight

Translate operations on sequences into operations on functions.

Shifting a sequence ↔ multiplying/dividing by $x$ .
Adding sequences ↔ adding functions.
The convolution of two sequences ↔ the product of their OGFs.
The binomial convolution of two sequences ↔ the product of their EGFs.
Combinatorial constructions (union, pairing, sequence-of, set-of) ↔ sum, product, $\frac{1}{1 - A}$ , $e^{\hat{A}}$ .

Once you know the dictionary, counting reduces to algebra and calculus.

Formal Statement

Ordinary Generating Function (OGF)

For a sequence $(a_{n})_{n \geq 0}$ of real or complex numbers, its ordinary generating function is the formal power series

A (x) = n = 0 \sum \infty a_{n} x^{n} = a_{0} + a_{1} x + a_{2} x^{2} + \dots

⟳Definitional —

a_{n} = [x^{n}] A (x)

, the coefficient of

x^{n}

. The symbol

x

is a formal indeterminate; no value is substituted unless convergence is invoked.

Here $[x^{n}] A (x)$ denotes "the coefficient of $x^{n}$ in $A (x)$ ." The set of all formal power series over a field $K$ , denoted $K [[x]]$ , forms a commutative ring under coefficientwise addition and Cauchy-product multiplication.

Exponential Generating Function (EGF)

For a sequence $(a_{n})_{n \geq 0}$ , its exponential generating function is

\hat{A} (x) = n = 0 \sum \infty a_{n} \frac{x ^{n}}{n !}

⟳Definitional —

a_{n} = n! [x^{n}] \hat{A} (x)

. The weight

1/ n!

is chosen so that products of EGFs implement binomial (labeled) convolution.

The factor $1/ n!$ is exactly what is needed so that multiplying two EGFs counts ways to interleave labels of two labeled structures.

The Two Convolutions

The defining algebraic properties. If $C (x) = A (x) B (x)$ as OGFs, and $\hat{C} (x) = \hat{A} (x) \hat{B} (x)$ as EGFs, then

c_{n} = k = 0 \sum n a_{k} b_{n - k} (Cauchy / ordinary convolution)

⟳Multiply

\sum a_{k} x^{k} \cdot \sum b_{j} x^{j}

and collect the coefficient of

x^{n}

over all

k + j = n

c_{n} = k = 0 \sum n (k n) a_{k} b_{n - k} (binomial / exponential convolution)

⟳The coefficient of

x^{n} / n!

\hat{A} \hat{B}

n! \sum_{k} \frac{a _{k}}{k !} \frac{b _{n - k}}{( n - k )!} = \sum_{k} (k n) a_{k} b_{n - k}

Operational Dictionary

Let $A (x) = \sum a_{n} x^{n}$ . The following equivalences hold in $K [[x]]$ :

n \geq 0 \sum a_{n + 1} x^{n} = \frac{A ( x ) - a _{0}}{x}, n \geq 0 \sum n a_{n} x^{n} = x A^{'} (x)

⟳First: drop

a_{0}

and divide by

x

to shift indices down by one. Second: differentiate

A

term-by-term (

\frac{d}{d x} x^{n} = n x^{n - 1}

) and multiply by

x

n \geq 0 \sum (k = 0 \sum n a_{k}) x^{n} = \frac{A ( x )}{1 - x}

⟳Partial-sum sequence is the convolution of

(a_{n})

with the constant sequence

(1, 1, 1, \dots)

, whose OGF is

\frac{1}{1 - x}

For EGFs, differentiation shifts:

\frac{d}{d x} \hat{A} (x) = n \geq 0 \sum a_{n + 1} \frac{x ^{n}}{n !}

⟳

\frac{d}{d x} \frac{x ^{n}}{n !} = \frac{x ^{n - 1}}{( n - 1 )!}

, so differentiation maps the EGF of

(a_{n})

to the EGF of

(a_{n + 1})

Why It Holds / Derivation

The geometric series and partial fractions, the master tools

Step 1 — The fundamental OGF. Consider

(1, 1, 1, \dots)

. In

K [[x]]

(1 - x) \sum_{n \geq 0} x^{n} = 1

because all terms cancel telescopically. Hence

\frac{1}{1 - x} = n = 0 \sum \infty x^{n}

⟳Multiply

\sum x^{n}

(1 - x)

; the coefficient of

x^{n}

for

n \geq 1

1 - 1 = 0

, and the constant term is

1

Step 2 — Scaling and the negative binomial. Substituting

x \to c x

gives

\frac{1}{1 - c x} = \sum c^{n} x^{n}

. Differentiating

k

times and normalizing gives

\frac{1}{( 1 - x ) ^{k + 1}} = n = 0 \sum \infty (k n + k) x^{n}

⟳Apply

\frac{1}{k !} \frac{d ^{k}}{d x ^{k}}

to [8]; the

k

-th derivative of

(1 - x)^{- 1}

k! (1 - x)^{- (k + 1)}

, and term-by-term it produces

(k n + k)

Step 3 — Solving a linear recurrence (template). Suppose

a_{n} = p a_{n - 1} + q a_{n - 2}

for

n \geq 2

. Multiply by

x^{n}

, sum over

n \geq 2

A (x) - a_{0} - a_{1} x = p x (A (x) - a_{0}) + q x^{2} A (x)

⟳

\sum_{n \geq 2} a_{n - 1} x^{n} = x (A - a_{0})

and

\sum_{n \geq 2} a_{n - 2} x^{n} = x^{2} A

; substitute and isolate

A

Solving for $A (x)$ yields a rational function $\frac{P ( x )}{1 - p x - q x ^{2}}$ . Step 4 — Partial fractions. Factor the denominator $1 - p x - q x^{2} = (1 - α x) (1 - β x)$ and write $A (x) = \frac{C _{1}}{1 - α x} + \frac{C _{2}}{1 - β x}$ . By [8], $a_{n} = C_{1} α^{n} + C_{2} β^{n}$ . This is the closed form. $■$

Leonhard Euler | 1707–1783

Euler was the first to wield generating functions as a systematic instrument. In Introductio in analysin infinitorum (1748) he used them to study partitions of integers, deriving the product formula $\prod_{k \geq 1} (1 - x^{k})^{- 1}$ as the OGF for the partition function $p (n)$ , and discovering the Pentagonal Number Theorem $\prod (1 - x^{k}) = \sum_{j} (- 1)^{j} x^{j (3 j - 1) /2}$ . He treated power series with fearless formal manipulation, anticipating modern formal-power-series rigor by two centuries. His genius lay in seeing that an infinite catalogue of combinatorial facts could be compressed into a single analytic expression and then operated upon.

Building Intuition

Think of a generating function as a single object holding an entire sequence, where the variable $x^{n}$ is a "tag" marking position $n$ . Multiplication by $x$ pushes every tag up by one — a shift. Multiplying two OGFs is like asking: in how many ways can I split a budget of size $n$ between two activities? That is exactly the convolution $\sum a_{k} b_{n - k}$ .

The EGF's $1/ n!$ has a precise meaning. If you are counting labeled objects on ${1, \dots, n}$ (graphs, permutations, set partitions), then combining a structure on a $k$ -subset with a structure on the complementary $(n - k)$ -subset requires choosing which labels go where — the $(k n)$ in [4]. The $1/ n!$ weights bake this choosing directly into the product. Rule of thumb: unlabeled/positional ⟶ OGF; labeled/permutational ⟶ EGF.

OGF vs EGF: the two convolution products

Worked Examples

Fibonacci numbers via OGF

Given:

F_{0} = 0, F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2}

. Find a closed form. Step 1. Let

F (x) = \sum_{n \geq 0} F_{n} x^{n}

. Using the recurrence (template [10] with

p = q = 1

F (x) - 0 - x = x F (x) + x^{2} F (x) .

Step 2. Solve:

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

. Step 3. Factor

1 - x - x^{2} = (1 - φ x) (1 - ψ x)

where

φ = \frac{1 + 5}{2}

ψ = \frac{1 - 5}{2}

. Partial fractions:

F (x) = \frac{1}{5} (\frac{1}{1 - φ x} - \frac{1}{1 - ψ x}) .

Step 4. Read off coefficients with [8]:

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5} (Binet’s formula, dimensionless count)

Check:

F_{5} = \frac{φ ^{5} - ψ ^{5}}{5} = 5

. ✓

Counting set partitions / derangements via EGF

Given:

D_{n}

= number of permutations of

n

labeled items with no fixed point (derangements). A permutation decomposes into fixed points (each a singleton) and a derangement of the rest:

n! = k = 0 \sum n (k n) D_{n - k} .

This is a binomial convolution [4] of

(D_{n})

with the all-ones sequence. Step 1. In EGF language:

\sum n! \frac{x ^{n}}{n !} = \hat{D} (x) \cdot e^{x}

, i.e.

\frac{1}{1 - x} = \hat{D} (x) e^{x}

. Step 2. Solve:

\hat{D} (x) = \frac{e ^{- x}}{1 - x}

. Step 3. Multiply the series

e^{- x} = \sum \frac{( - 1 ) ^{k}}{k !} x^{k}

and

\frac{1}{1 - x} = \sum x^{m}

; the coefficient of

x^{n}

\sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}

. Then

D_{n} = n! [x^{n}] \hat{D} (x)

D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !} (integer count of derangements)

Check:

D_{4} = 24 (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}) = 9

. ✓ And

D_{n} / n! \to e^{- 1}

Common Misconceptions

Convergence is not required for formal manipulation. The series

\sum n! x^{n}

has radius of convergence

0

, yet it is a perfectly legitimate element of

K [[x]]

and can be added, multiplied, and differentiated formally. Convergence is only needed when you substitute a number for $x$ or extract asymptotics via complex analysis. Conversely, you may NOT freely substitute

x = 1

to "sum a sequence" unless the series actually converges there. Do not confuse OGF and EGF coefficients. From an OGF,

a_{n} = [x^{n}] A (x)

. From an EGF,

a_{n} = n! [x^{n}] \hat{A} (x)

— forgetting the

n!

is the single most common error. Naively using the OGF product for labeled objects fails. Suppose you count labeled structures and try the ordinary product. The number of ways to 2-color the labels of

{1, \dots, n}

(each element either red or blue) is

2^{n}

. Its EGF is

e^{x} \cdot e^{x} = e^{2 x} = \sum 2^{n} x^{n} / n!

— correct. If you instead used the OGF product

\frac{1}{1 - x} \cdot \frac{1}{1 - x} = \frac{1}{( 1 - x ) ^{2}} = \sum (n + 1) x^{n}

, you would get

n + 1

, the count of unlabeled compositions into two parts — a completely different, wrong answer for the labeled problem. The mismatch is precisely the missing

(k n)

choices of label placement.

Connections

Generating functions sit at the crossroads of several areas. Solving Linear Recurrence Relations becomes routine partial-fraction extraction. The Symbolic Method in Combinatorics (Flajolet–Sedgewick) systematizes the OGF/EGF dictionary into "admissible constructions" — SEQ, SET, CYC, MSET — translating combinatorial classes directly into functional equations. The EGF formalism is the analytic shadow of Species of Structures (Joyal), a category-theoretic foundation for labeled enumeration. Extracting $a_{n}$ asymptotically from a generating function is the subject of Analytic Combinatorics, using Cauchy's Integral Formula and singularity analysis. The Binomial Theorem and Catalan Numbers both fall out as special cases, and the multiplicative structure on Dirichlet series mirrors the OGF story for number-theoretic functions.

Real-World Applications

Algorithm analysis. Average-case complexity of Quicksort, hashing, and tries is computed by setting up an EGF/OGF recurrence and extracting coefficients (Knuth, TAOCP; Flajolet–Sedgewick).
Probability — moment & probability generating functions. $G (s) = \sum P (X = n) s^{n}$ (a PGF, an OGF) turns sums of independent random variables into products; $E [X] = G^{'} (1)$ and branching-process extinction probabilities are fixed points of $G$ .
Coding theory. Weight enumerators of error-correcting codes are generating polynomials; the MacWilliams identity relates a code's enumerator to its dual's.
Statistical mechanics. The grand partition function $Ξ = \sum_{N} z^{N} Z_{N}$ is literally an OGF in the fugacity $z$ ; thermodynamic quantities are its log-derivatives.
Population genetics & queueing theory. Birth–death and $M / M /1$ queue state probabilities are solved through generating-function transforms of the balance equations.
Signal processing. The $z$ -transform $X (z) = \sum x [n] z^{- n}$ is an OGF of a discrete signal; system poles are the partial-fraction roots.
Computational biology. RNA secondary-structure counting and sequence-alignment statistics use OGF recurrences (Catalan-like dynamic programming).

Historical Development

1730s–1748 — Euler introduces generating functions for integer partitions; proves the Pentagonal Number Theorem and the product formula for $p (n)$ .
1751 — Euler studies the Catalan numbers via the polygon-triangulation generating function $C (x) = \frac{1 - 1 - 4 x}{2 x}$ .
1812 — Laplace, in Théorie analytique des probabilités, develops the fonction génératrice as a central tool of probability; the Laplace transform is its continuous analogue.
1830s–1850s — Cayley and Sylvester use generating functions in invariant theory and tree enumeration.
1889 — Cayley's formula $n^{n - 2}$ for labeled trees; later given EGF proofs via the tree function $T (x) = x e^{T (x)}$ .
1927 — George Pólya's enumeration theorem (cycle index series) systematizes counting under symmetry — a deep OGF construction.
1973 — Foata & Schützenberger's combinatorial theory of formal power series cements the formal viewpoint.
1981 — André Joyal introduces the theory of species, giving EGFs a rigorous categorical foundation.
1990 — Herbert Wilf publishes generatingfunctionology, the standard undergraduate text; 2009 — Flajolet & Sedgewick's Analytic Combinatorics unifies the symbolic and asymptotic theory.

Subtleties & Limits

When does a generating function have a "nice" closed form? A power series is D-finite (holonomic) if it satisfies a linear ODE with polynomial coefficients — equivalently its coefficients are P-recursive. Algebraic ⊂ D-finite, but many natural sequences are non-holonomic, and deciding holonomicity for a combinatorially defined class can be subtle. A deeper question: for a given lattice-walk model in a quadrant, when is the OGF algebraic, D-finite, or neither? The Bousquet-Mélou–Mishna classification (2010) resolved the 79 small-step quadrant models using a group-of-the-walk invariant, but extensions to higher dimensions, weighted steps, and three-quarter-plane walks remain active research. Separately, effective asymptotics from generating functions (transfer theorems, multivariate singularity analysis) is well developed for meromorphic/algebraic singularities but still open in full generality for functions with complicated singular structure.