Generating Functions

Encode a sequence $(a_{0}, a_{1}, a_{2}, \dots)$ as the formal power series

$A (x) = \sum_{n \geq 0} a_{n} x^{n} .$

Operations on sequences become algebra on the series, and the coefficient extraction $[x^{n}] A (x)$ recovers the answer.

The dictionary

Sequence operation	Series operation
$a_{n} + b_{n}$	$A + B$
$\sum_{k} a_{k} b_{n - k}$ (convolution)	$A \cdot B$
$a_{n - 1}$ (shift right)	$x A$
$a_{n + 1}$ (shift left)	$(A - a_{0}) / x$
$n a_{n}$	$x A^{'}$
$\sum_{k \leq n} a_{k}$ (prefix sums)	$\frac{A}{1 - x}$
$a_{n} c^{n}$	$A (c x)$
choose any number of copies of one item	$\frac{1}{1 - x ^{w}}$
choose at most one copy	$1 + x^{w}$

The essential series

$\frac{1}{1 - x} = \sum x^{n}, \frac{1}{( 1 - x ) ^{k}} = \sum (k - 1 n + k - 1) x^{n}, (1 + x)^{n} = \sum (k n) x^{k}$

$e^{x} = \sum \frac{x ^{n}}{n !}, ln \frac{1}{1 - x} = \sum_{n \geq 1} \frac{x ^{n}}{n}, \frac{1}{1 - x - x ^{2}} = \sum F_{n + 1} x^{n}$

$\frac{1 - 1 - 4 x}{2 x} = \sum C_{n} x^{n} (Catalan) .$

Why they help

Counting with constraints

“How many ways to make $n$ using coins $1, 2, 5$ , unlimited?”

$\frac{1}{( 1 - x ) ( 1 - x ^{2} ) ( 1 - x ^{5} )},$

and the answer is $[x^{n}]$ of that. Each factor encodes one coin’s choices; multiplying combines them. This makes coin change a mechanical derivation rather than a DP to be invented.

“…using each coin at most twice?” → replace $\frac{1}{1 - x ^{c}}$ with $1 + x^{c} + x^{2 c}$ .

Solving recurrences

For $a_{n} = a_{n - 1} + a_{n - 2}$ with $a_{0} = a_{1} = 1$ :

$A (x) = \frac{1}{1 - x - x ^{2}},$

and partial fractions give Binet’s formula. In general, a linear recurrence corresponds to a rational generating function, whose denominator is the reversed characteristic polynomial. That correspondence is what Bostan-Mori exploits to compute the $n$ -th term in $O (k lo g k lo g n)$ .

Deriving identities

$(1 + x)^{m} (1 + x)^{n} = (1 + x)^{m + n}$ gives Vandermonde’s identity $\sum_{k} (k m) (r - k n) = (r m + n)$ by comparing coefficients. Most binomial identities fall out this way.

Exponential generating functions

For labelled structures, use $A (x) = \sum a_{n} \frac{x ^{n}}{n !}$ . Then the product corresponds to splitting a labelled set into two parts:

$[x^{n}] A (x) B (x) \cdot n! = \sum_{k} (k n) a_{k} b_{n - k} .$

Structure	EGF
Any set	$e^{x}$
Non-empty set	$e^{x} - 1$
Permutations	$\frac{1}{1 - x}$
Cycles	$ln \frac{1}{1 - x}$
Derangements	$\frac{e ^{- x}}{1 - x}$
Set partitions (Bell)	$e^{e^{x} - 1}$
Involutions	$e^{x + x^{2} /2}$

The exponential formula — “if $C (x)$ is the EGF for connected structures, then $e^{C (x)}$ is the EGF for all structures” — is remarkably powerful: it turns “count graphs” into “count connected graphs” and back.

Computing with them

Operation	Cost
Multiply two series to $n$ terms	$O (n lo g n)$ with NTT
Inverse $1/ A$	$O (n lo g n)$ by Newton iteration
$ln A$ , $exp A$	$O (n lo g n)$
$A$ , $A^{k}$	$O (n lo g n)$
Extract $[x^{n}]$ of a rational function	$O (k lo g k lo g n)$ (Bostan-Mori)
Composition $A (B (x))$	$O (n lo g^{2} n)$ (or better)

See Formal Power Series for the implementations.

When to reach for them

The problem is “count the ways to combine independent choices” → multiply the per-choice series.
The recurrence is linear with constant coefficients → rational GF, then Bostan-Mori.
The objects are labelled and split into independent parts → EGF and the exponential formula.
You need $[x^{n}]$ for one huge $n$ → find the closed form, then extract.
You need all coefficients up to $n$ → NTT-based series operations.

Even when you end up writing an ordinary DP, deriving the generating function first often reveals the right state and transition.

See also: Formal Power Series · Combinatorics · Bostan-Mori

whoashish's cp notes

Directory