Generating Functions

A generating function packs an entire sequence $a_0, a_1, a_2, \ldots$ into one power series. Algebra on the series (adding, multiplying, shifting, differentiating) then corresponds to combinatorial operations on the sequence. This gives a uniform way to count selections with constraints ("how many ways to make 25 rupees from 1, 2 and 5 rupee coins?") and to solve recurrence relations. The working tasks are finding the sequence of a given generating function, the generating function of a given sequence, or a single coefficient.

The (ordinary) generating function (OGF) of the sequence $(a_n)_{n \ge 0}$ is the formal power series

$x$ is a placeholder: we manipulate the series formally and do not need it to converge. When a closed form like $1/(1 - x)$ is used, it means the series whose product with $1 - x$ is 1. The coefficient of $x^n$ in $G(x)$ is written $[x^n]\,G(x)$.

A finite sequence $a_0, \ldots, a_m$ has a polynomial generating function: the sequence $\binom{n}{0}, \ldots, \binom{n}{n}$ has $G(x) = (1 + x)^n$.

The row $1/(1-x)^k$ is the extended binomial theorem: the coefficient of $x^n$ is the number of multisets of size $n$ from $k$ types, the stars-and-bars count.

If $A(x) = \sum a_n x^n$ and $B(x) = \sum b_n x^n$:

The product rule is the key counting fact: if $a_k$ counts ways to choose $k$ items of one kind and $b_j$ ways to choose $j$ items of another, then $c_n$ counts ways to choose $n$ items in total.

To count selections of $n$ objects from several types, write one factor per type, listing the allowed quantities as powers of $x$, multiply, and read off $[x^n]$.

Example: coins. Ways to pay $n$ rupees with any number of 1 and 2 rupee coins (order irrelevant):

Example: bounded quantities. Ways to choose 6 fruits with at most 2 apples, at least 1 banana, and any number of cherries:

$[x^6]$ of $x/(1-x)^2$ is 6 (sequence $n$), so $[x^6]$ of the product is $6 + 5 + 4 = 15$.

Example: dice. The number of ways to roll a total of 10 with three six-sided dice is the coefficient of $x^{10}$ in $(x + x^2 + \cdots + x^6)^3 = x^3\big((1 - x^6)/(1 - x)\big)^3$, which is the coefficient of $x^7$ in $\big((1 - x^6)/(1 - x)\big)^3$. Expanding $(1 - x^6)^3 = 1 - 3x^6 + \cdots$ and using $1/(1-x)^3$ (coefficients $\binom{n+2}{2}$): $\binom{9}{2} - 3\binom{3}{2} = 36 - 9 = 27$.

Example: a parity constraint. Non-negative integer solutions of $x_1 + x_2 + x_3 = 10$ with $x_1$ even: the generating function is $\dfrac{1}{1 - x^2} \cdot \dfrac{1}{(1 - x)^2}$. Choosing $x_1 = j$ (even) leaves $10 - j + 1$ solutions for $x_2 + x_3 = 10 - j$, so the coefficient of $x^{10}$ is $11 + 9 + 7 + 5 + 3 + 1 = 36$.

Procedure.

$a_n = 3a_{n-1} + 2$ for $n \ge 1$, $a_0 = 1$.

Check: $a_1 = 3 \cdot 1 + 2 = 5 = 6 - 1$.

$F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$, $F_0 = 0$, $F_1 = 1$. The same steps give

Factoring $1 - x - x^2 = (1 - \varphi x)(1 - \psi x)$ with $\varphi, \psi = (1 \pm \sqrt{5})/2$ and splitting into partial fractions yields Binet's formula $F_n = (\varphi^n - \psi^n)/\sqrt{5}$.

Find $a_n$ for $G(x) = \dfrac{1}{(1 - x)(1 - 2x)}$. Partial fractions: $\dfrac{2}{1 - 2x} - \dfrac{1}{1 - x}$, so $a_n = 2^{n+1} - 1$. Equivalently $G$ is $1/(1 - 2x)$ divided by $1 - x$: partial sums of $2^n$, which are $2^{n+1} - 1$.

The recurrence $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$, $C_0 = 1$, is a convolution, so $C(x) = 1 + x\,C(x)^2$. Solving the quadratic and choosing the root that is finite at $x = 0$:

The exponential generating function (EGF) of $(a_n)$ is $\sum a_n x^n / n!$. EGFs suit labelled structures (including linear orders on labelled objects), because the product of EGFs counts ways to split a set of labels between two structures ($c_n = \sum_k \binom{n}{k} a_k b_{n-k}$). Examples: the EGF of $1, 1, 1, \ldots$ is $e^x$; permutations ($a_n = n!$) have EGF $1/(1 - x)$; derangements have EGF $e^{-x}/(1 - x)$.