Generating Functions

A generating function encodes a sequence $(a_{n})$ as the coefficients of a formal power series $\sum a_{n} x^{n}$ , turning sequence operations into algebra. Key result: counting, recurrences, and convolutions become multiplication, differentiation, and substitution of functions. Used across combinatorics, probability, number theory, and analysis of algorithms. Introduced by Abraham de Moivre (1730) and developed extensively by Euler and Laplace.

A generating function is a formal device that packages an infinite sequence $a_{0}, a_{1}, a_{2}, \dots$ into a single object—the formal power series $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ (ordinary type) or $\sum_{n \geq 0} a_{n} x^{n} / n!$ (exponential type). The "function" is a bookkeeping tool: we manipulate it algebraically and then read off coefficients, often without ever evaluating it at a number. This matters because difficult problems about sequences—solving recurrences, counting structures, computing convolutions—translate into routine operations on functions like addition, multiplication, and differentiation. The surprising fact is that a closed-form function can compress infinitely many combinatorial facts: for instance, $1/ (1 - x - x^{2})$ contains every Fibonacci number, and its partial fraction decomposition instantly yields Binet's formula.

The Core Insight

A sequence is hard to manipulate term-by-term, but the whole sequence at once, viewed as a power series, lives in a ring where you can add, multiply, invert, differentiate, and compose. The clothesline metaphor (Wilf): a generating function is a clothesline on which we hang up the terms of a sequence for display. The power of $x^{n}$ is just a label remembering position $n$ ; the coefficient is the datum. Combinatorial operations on objects (disjoint union, pairing, sequencing) correspond exactly to algebraic operations on their generating functions.

Formal Statement

Ordinary Generating Function (OGF)

Given a sequence $(a_{n})_{n \geq 0}$ of numbers (in a commutative ring $R$ , typically $Q$ , $R$ , or $C$ ), 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

⟳This is a definition;

x

is a formal indeterminate, not a number, and convergence is not required.

Here $a_{n} = [x^{n}] A (x)$ denotes the coefficient extraction operator: $[x^{n}]$ returns the coefficient of $x^{n}$ .

Exponential Generating Function (EGF)

The exponential generating function of $(a_{n})_{n \geq 0}$ is

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

⟳The

n!

weighting is chosen so that labelled-structure operations (where order of labels matters) become clean products.

EGFs are preferred for labelled combinatorial structures (permutations, labelled graphs); OGFs for unlabelled ones (partitions, integer compositions).

The Ring of Formal Power Series

The set $R [[x]]$ of all formal power series over $R$ forms a commutative ring under coefficientwise addition and Cauchy-product multiplication:

(n \sum a_{n} x^{n}) (n \sum b_{n} x^{n}) = n = 0 \sum \infty (k = 0 \sum n a_{k} b_{n - k}) x^{n}

⟳Collect all products

a_{k} x^{k} \cdot b_{n - k} x^{n - k}

contributing to

x^{n}

; the inner sum is the convolution

(a * b)_{n}

A series $A (x)$ is invertible in $R [[x]]$ if and only if $a_{0}$ is a unit of $R$ (e.g. $a_{0} \neq = 0$ when $R$ is a field).

Convolution Theorem

If $A (x) = \sum a_{n} x^{n}$ and $B (x) = \sum b_{n} x^{n}$ are OGFs, then the product $A (x) B (x)$ is the OGF of the convolution sequence $c_{n} = \sum_{k = 0}^{n} a_{k} b_{n - k}$ . For EGFs, the product $\hat{A} (x) \hat{B} (x)$ is the EGF of the binomial convolution:

c_{n} = k = 0 \sum n (k n) a_{k} b_{n - k}

⟳Multiply

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

\sum b_{j} x^{j} / j!

, set

n = k + j

, and multiply and divide by

n!

to recover the binomial coefficient.

Fundamental Operations Dictionary

For OGFs, the following correspondences hold (with $A (x) = \sum a_{n} x^{n}$ ):

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

⟳Shift by reindexing

m = n + 1

; the factor

n

comes from

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

; the partial-sum identity is convolution of

(a_{n})

with the all-ones sequence

1/ (1 - x)

Why It Holds / Derivation

Solving a Linear Recurrence via OGF: the Fibonacci case

We derive the closed form of the Fibonacci numbers $F_{0} = 0, F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2}$ .

Step 1. Define

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

. Step 2. Encode the recurrence. Multiply

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

(valid for

n \geq 2

) by

x^{n}

and sum:

n \geq 2 \sum F_{n} x^{n} = n \geq 2 \sum F_{n - 1} x^{n} + n \geq 2 \sum F_{n - 2} x^{n} .

Step 3. Express each sum via

F (x)

. The left side is

F (x) - F_{0} - F_{1} x = F (x) - x

. The first right sum is

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

. The second is

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

. Step 4. Assemble:

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

, hence

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

⟳Collect

F (x)

terms on the left and factor.

Step 5. Partial fractions. Factor

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

where

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

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

. Decompose:

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

Step 6. Expand each geometric series

\frac{1}{1 - r x} = \sum_{n} r^{n} x^{n}

and read off coefficients:

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

⟳

[x^{n}] \frac{1}{1 - r x} = r^{n}

; subtract the two geometric expansions termwise.

■

Leonhard Euler | 1707–1783

Though de Moivre first used generating functions to solve recurrences, Euler made them a central tool of analysis and number theory. His 1748 Introductio in analysin infinitorum used the product $\prod_{k} (1 - x^{k})^{- 1}$ as the generating function for partitions, leading to the Pentagonal Number Theorem and deep partition identities. Euler treated formal series with a fearless algebraic spirit—manipulating divergent series and infinite products to extract finite truths—anticipating the rigorous formal-power-series framework formalized only in the 20th century.

Building Intuition

Think of $x^{n}$ as a box labelled $n$ , and $a_{n}$ as the number of marbles in that box. The series $A (x)$ is the entire shelf of boxes. Multiplying two generating functions is like asking: in how many ways can I pick a marble from $A$ 's box $k$ and one from $B$ 's box $n - k$ so the labels add to $n$ ? That's exactly a convolution, which is how counting "split this object into two parts" works. The variable $x$ "remembers size by exponent and adds sizes by multiplication"—it is a size-tracking accountant. You never plug in a number unless you want a value (e.g. setting $x = 1$ to sum the sequence, or differentiating then setting $x = 1$ to get a weighted sum/expectation).

OGF as a shelf of labelled coefficient-boxes; product = convolution

Worked Examples

Counting compositions of an integer

Given. How many ways can a positive integer

n

be written as an ordered sum of positive integers (compositions)? E.g.

3 = 3 = 2 + 1 = 1 + 2 = 1 + 1 + 1

, so

4

ways. Step 1. A single positive part has OGF

P (x) = x + x^{2} + x^{3} + \dots = \frac{x}{1 - x}

(one object of each size

\geq 1

). Step 2. A composition is a sequence of

\geq 1

parts. The "sequence of one or more

P

" construction gives

C (x) = k \geq 1 \sum P (x)^{k} = \frac{P ( x )}{1 - P ( x )} = \frac{x / ( 1 - x )}{1 - x / ( 1 - x )} = \frac{x}{1 - 2 x} .

Step 3. Expand:

\frac{x}{1 - 2 x} = x \sum_{m \geq 0} (2 x)^{m} = \sum_{m \geq 0} 2^{m} x^{m + 1}

, so

[x^{n}] C (x) = 2^{n - 1}

for

n \geq 1

. Answer.

2^{n - 1} compositions of n

(e.g.

n = 3 \Rightarrow 2^{2} = 4

✓, dimensionless count).

Mean of a probability distribution via PGF

Given. Roll a fair die; let

X

be the outcome. Find

E [X]

using the probability generating function

G (x) = E [x^{X}] = \sum_{k} P (X = k) x^{k}

. Step 1. Each face has probability

\frac{1}{6}

, so

G (x) = \frac{1}{6} (x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6}) = \frac{x ( 1 - x ^{6} )}{6 ( 1 - x )} .

Step 2. Use the identity

E [X] = G^{'} (1)

G^{'} (x) = \frac{1}{6} (1 + 2 x + 3 x^{2} + 4 x^{3} + 5 x^{4} + 6 x^{5}) .

Step 3. Evaluate at

x = 1

G^{'} (1) = \frac{1}{6} (1 + 2 + 3 + 4 + 5 + 6) = \frac{1}{6} \cdot 21 = \frac{21}{6} = 3.5.

Answer.

E [X] = 3.5

(dimensionless; matches direct computation). Note: variance follows from

G^{''} (1) + G^{'} (1) - G^{'} (1)^{2}

Common Misconceptions

Generating functions are formal, not analytic—by default. You do not need

\sum a_{n} x^{n}

to converge anywhere for the algebra to be valid. The series

\sum n! x^{n}

has radius of convergence

0

, yet is a perfectly good element of

Q [[x]]

on which you may add, multiply, and invert. Convergence is required only when you actually substitute a numerical value of

x

(e.g. setting

x = 1/2

, or applying analytic methods like singularity analysis to estimate

a_{n}

). Confusing the formal and analytic viewpoints leads to false statements about "the value" of a divergent generating function. Multiplication is not always valid for two-sided or Laurent series. The Cauchy product

\sum_{n} (\sum_{k} a_{k} b_{n - k})

requires each coefficient to be a finite sum. If you allow doubly-infinite series

\sum_{n \in Z} a_{n} x^{n}

, the convolution

\sum_{k} a_{k} b_{n - k}

can become an infinite sum with no formal meaning. For example, formally multiplying

\sum_{n \geq 0} x^{n}

\sum_{n \geq 0} x^{- n}

gives a coefficient of

x^{0}

equal to

\sum_{k \geq 0} 1 \cdot 1 = \infty

. Thus the ring structure

R [[x]]

relies crucially on series being bounded below in degree.

Connections

Generating functions sit at a crossroads of many fields. The OGF dictionary is the engine of Analytic Combinatorics, where the location and nature of singularities of $A (x)$ control the asymptotic growth of $a_{n}$ (Flajolet–Sedgewick). In probability, the Probability Generating Function and Moment Generating Function are specializations giving moments and supporting limit theorems. The EGF formalism is the species-theoretic shadow of Exponential Formula for labelled structures. Number theory uses Dirichlet Series $\sum a_{n} / n^{s}$ —a "multiplicative" cousin where convolution corresponds to Dirichlet rather than Cauchy product. The recurrence-solving method generalizes via the Z-transform in signal processing and the Laplace Transform in the continuous setting.

Real-World Applications

Algorithm analysis. Average-case running times (e.g. of Quicksort, hashing, binary search trees) are extracted from generating functions of cost; Knuth's The Art of Computer Programming and Flajolet–Sedgewick's Analytic Combinatorics systematize this.
Coding theory. The weight enumerator polynomial of an error-correcting code is a generating function over codeword weights; the MacWilliams identity relates a code's enumerator to its dual's.
Statistical mechanics. The partition function $Z = \sum_{s} e^{- β E_{s}}$ is literally a generating function over energy states; derivatives give energy, heat capacity, and other thermodynamic quantities.
Queueing theory & reliability. PGFs of queue lengths and busy-period lengths (e.g. in the M/G/1 queue) are obtained via generating-function functional equations.
Genetics & branching processes. Galton–Watson extinction probabilities are computed as fixed points $G (s) = s$ of the offspring PGF.
Cryptography & combinatorial enumeration. Counting Latin squares, lattice paths, and configurations underpins randomness and design analysis.
Financial mathematics. Compound-distribution aggregate-loss models in actuarial science use PGFs (Panjer recursion) to compute claim-total distributions.

Historical Development

1730 — Abraham de Moivre, in Miscellanea Analytica, introduces generating functions to solve linear recurrences, including a closed form for Fibonacci-type sequences.
1748 — Euler publishes Introductio in analysin infinitorum, using infinite products as generating functions for partitions; foundation of partition theory.
1750s — Euler discovers the Pentagonal Number Theorem, expressing $\prod (1 - x^{k})$ as a sparse signed series.
1782 — Pierre-Simon Laplace systematizes "fonctions génératrices" in his probability work, coining the modern term and applying them to difference equations.
1812 — Laplace's Théorie analytique des probabilités makes generating functions (and the Laplace transform) central to probability.
1900s–1930s — Formal power series receive rigorous algebraic foundations; the ring $R [[x]]$ is studied abstractly.
1960s — Donald Knuth popularizes generating functions for rigorous algorithm analysis.
1970s–1980s — Gian-Carlo Rota, Joyal's theory of species, and the umbral calculus give combinatorics a structural, functorial language for generating functions.
1990s–2009 — Philippe Flajolet and Robert Sedgewick develop Analytic Combinatorics, linking singularities of generating functions to coefficient asymptotics; Wilf's generatingfunctionology becomes a standard text.

Subtleties & Limits

Generating functions are most powerful when they have a nice closed form, but classifying which sequences admit which kind of GF is deep. A sequence is D-finite (holonomic) iff its OGF satisfies a linear ODE with polynomial coefficients; algebraic iff the OGF satisfies a polynomial equation; and these classes are properly nested. Determining whether a given combinatorially defined OGF is algebraic, D-finite, or "wild" can be extremely hard. Famous open territory: many sequences in enumerative combinatorics (e.g. certain self-avoiding-walk and lattice-animal counts) are conjectured to be non-D-finite, but proving non-holonomicity is notoriously difficult. The automatic/transcendence classification of multivariate generating functions, and effective asymptotics from implicit functional equations, remain active research areas.

Generating Functions

The Core Insight

Formal Statement

Ordinary Generating Function (OGF)

Exponential Generating Function (EGF)

The Ring of Formal Power Series

Convolution Theorem

Fundamental Operations Dictionary

Why It Holds / Derivation

Solving a Linear Recurrence via OGF: the Fibonacci case

Leonhard Euler | 1707–1783

Building Intuition

OGF as a shelf of labelled coefficient-boxes; product = convolution

Worked Examples

Counting compositions of an integer

Mean of a probability distribution via PGF

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads