vii. 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}$

Proof: the dictionary entries

The coefficient of $x^{n}$ in $A \cdot B$ is $\sum_{k} a_{k} b_{n - k}$ by expanding the product. $\frac{1}{1 - x} = \sum x^{n}$ , so $\frac{A}{1 - x}$ is the convolution of $a$ with all ones, the prefix sums. $x A^{'} = \sum n a_{n} x^{n}$ by termwise differentiation; $A (c x) = \sum a_{n} c^{n} x^{n}$ . For one item of weight $w$ , choosing $j$ copies contributes $x^{j w}$ , so unlimited copies give $\sum_{j} x^{j w} = \frac{1}{1 - x ^{w}}$ and at most one copy gives $1 + x^{w}$ ; independent choices multiply because their weights add. $\frac{1}{( 1 - x ) ^{k}}$ counts multisets of size $n$ from $k$ types, which is $(k - 1 n + k - 1)$ by stars and bars.

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?” $\to$ 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: with $φ, ψ = \frac{1 \pm 5}{2}$ , $\frac{1}{1 - x - x ^{2}} = \frac{1}{5} (\frac{φ}{1 - φ x} - \frac{ψ}{1 - ψ x})$ , so $a_{n} = F_{n + 1} = \frac{φ ^{n + 1} - ψ ^{n + 1}}{5}$ . 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.

Proof: linear recurrences are rational generating functions

If $a_{n} = \sum_{i = 1}^{d} c_{i} a_{n - i}$ for $n \geq d$ , then $Q (x) = 1 - \sum_{i} c_{i} x^{i}$ satisfies $[x^{n}] Q (x) A (x) = a_{n} - \sum_{i} c_{i} a_{n - i} = 0$ for $n \geq d$ , so $P = Q A$ is a polynomial of degree $< d$ and $A = P / Q$ . Conversely, if $A = P / Q$ with $Q (0) = 1$ and $de g P < de g Q = d$ , comparing coefficients of $Q A = P$ gives the recurrence. $Q$ is the characteristic polynomial with reversed coefficients.

Code: series arithmetic and counting, O(n²)

The $O (n^{2})$ versions below are enough for $n \leq 5000$ and are what you type in a contest when NTT is not needed; the $O (n lo g n)$ versions are in Formal Power Series.

const long long MOD = 998244353;
long long pw(long long a, long long e) { long long r = 1; a %= MOD; for (; e; e >>= 1, a = a * a % MOD) if (e & 1) r = r * a % MOD; return r; }
vector<long long> mulTrunc(const vector<long long>& a, const vector<long long>& b, int n) {   // first n coefficients of a*b, O(n^2)
    vector<long long> c(n, 0);
    for (int i = 0; i < sz(a) && i < n; i++) if (a[i]) for (int j = 0; j < sz(b) && i + j < n; j++) c[i + j] = (c[i + j] + a[i] * b[j]) % MOD;
    return c;
}
vector<long long> invTrunc(const vector<long long>& a, int n) {    // 1/A mod x^n, needs a[0] != 0, O(n^2)
    vector<long long> b(n, 0); long long i0 = pw(a[0], MOD - 2); b[0] = i0;
    for (int k = 1; k < n; k++) {
        long long s = 0;
        for (int j = 1; j <= k && j < sz(a); j++) s = (s + a[j] * b[k - j]) % MOD;
        b[k] = (MOD - s) % MOD * i0 % MOD;
    }
    return b;
}
vector<long long> coinWays(const vector<int>& coins, int n) {      // [x^k] prod 1/(1 - x^w), k <= n
    vector<long long> f(n + 1, 0); f[0] = 1;
    for (int w : coins) for (int k = w; k <= n; k++) f[k] = (f[k] + f[k - w]) % MOD;   // multiply by 1/(1 - x^w)
    return f;
}
vector<long long> connectedFromAll(const vector<long long>& g) {   // exponential formula, labelled: g = all (g[0] = 1), returns connected counts
    int n = sz(g) - 1; vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i <= n; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; }
    vector<long long> c(n + 1, 0);
    for (int m = 1; m <= n; m++) {                                 // root the component containing vertex 1: size k
        long long s = 0;
        for (int k = 1; k < m; k++) s = (s + C[m - 1][k - 1] * c[k] % MOD * g[m - k]) % MOD;
        c[m] = (g[m] - s + MOD) % MOD;
    }
    return c;
}

Proof: the code

Inverse. $A \cdot B = 1$ means $\sum_{j = 0}^{k} a_{j} b_{k - j} = [k = 0]$ , so $b_{0} = a_{0}^{- 1}$ and $b_{k} = - a_{0}^{- 1} \sum_{j = 1}^{k} a_{j} b_{k - j}$ , computed in increasing $k$ . Coins. Multiplying $F$ by $\frac{1}{1 - x ^{w}}$ means $G = F + x^{w} G$ , i.e. $g_{k} = f_{k} + g_{k - w}$ , which is the in-place loop. Exponential formula. In a labelled structure on ${1.. m}$ , let $k$ be the size of the component containing vertex $1$ : choose its other $k - 1$ vertices ( $(k - 1 m - 1)$ ways), a connected structure on them ( $c_{k}$ ), and any structure on the rest ( $g_{m - k}$ ). So $g_{m} = \sum_{k = 1}^{m} (k - 1 m - 1) c_{k} g_{m - k}$ , which the code solves for $c_{m}$ ; in EGF terms this is $G^{'} = C^{'} G$ , i.e. $G = e^{C}$ . Tests: inverse times series is $1$ ; coin counts against brute-force enumeration; connected labelled graphs $1, 1, 4, 38, 728, 26704, 1866256, 251548592$ from $g_{m} = 2^{(2 m)}$ ; derangements from $\frac{e ^{- x}}{1 - x}$ against all permutations.

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.

Proof: EGF products and the table

$[x^{n}] A (x) B (x) = \sum_{k} \frac{a _{k}}{k !} \frac{b _{n - k}}{( n - k )!}$ , and multiplying by $n!$ gives $\sum_{k} (k n) a_{k} b_{n - k}$ : choose which $k$ labels go to the first part. Any set: one structure per size, $\sum \frac{x ^{n}}{n !} = e^{x}$ . Permutations: $n!$ per size, $\sum x^{n} = \frac{1}{1 - x}$ . Cycles: $(n - 1)!$ per size, $\sum \frac{x ^{n}}{n} = ln \frac{1}{1 - x}$ . Permutations are sets of cycles, so $\frac{1}{1 - x} = e^{l n \frac{1}{1 - x}}$ (the exponential formula); a derangement is a permutation without fixed points, so its EGF is $e^{l n \frac{1}{1 - x} - x} = \frac{e ^{- x}}{1 - x}$ . Set partitions are sets of non-empty blocks: $e^{e^{x} - 1}$ . Involutions are sets of cycles of length 1 or 2: $e^{x + x^{2} /2}$ .

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” $\to$ multiply the per-choice series.
The recurrence is linear with constant coefficients $\to$ rational GF, then Bostan-Mori.
The objects are labelled and split into independent parts $\to$ EGF and the exponential formula.
You need $[x^{n}]$ for one huge $n$ $\to$ find the closed form, then extract.
You need all coefficients up to $n$ $\to$ 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.

whoashish's cp notes

Directory