Generating Functions for Counting

Definition and intuition

The ordinary generating function (OGF) of a sequence $a_0, a_1, a_2, \ldots$ is the formal power series

$A(x) = \sum_{n \ge 0} a_n x^{n} = a_0 + a_1 x + a_2 x^{2} + \cdots$

Think of $x^{n}$ as a bookmark for "size $n$": the coefficient $a_n$ records how many objects have size $n$. We never plug in a number for $x$ — it is a bookkeeping variable. Writing $[x^{n}]A(x)$ for "the coefficient of $x^{n}$," the whole game is: build $A(x)$ in closed form, then read off $a_n = [x^{n}]A(x)$.

Key formulas

Closed forms come from the geometric and binomial series. The two you must know cold:

$\frac{1}{1-x} = \sum_{n \ge 0} x^{n}, \qquad \frac{1}{(1-x)^{k}} = \sum_{n \ge 0} \binom{n+k-1}{k-1} x^{n}.$

Replacing $x \to -x$ gives the alternating-sign versions, e.g. $\dfrac{1}{(1+x)^{2}} = \sum_{n \ge 0} (-1)^{n}(n+1)\,x^{n}$. The general negative binomial / Newton rule is $[x^{n}]\,(1+x)^{-k} = (-1)^{n}\binom{n+k-1}{k-1}$.

Product = convolution

Multiplying two OGFs combines independent choices: if $A(x)B(x) = C(x)$ then

$c_n = \sum_{i=0}^{n} a_i\, b_{n-i}.$

So "pick an $A$-object of size $i$ and a $B$-object of size $n-i$" is exactly a product. This is why $\dfrac{1}{(1-x)^{k}}$ counts the ways to write $n$ as an ordered sum of $k$ nonnegative integers — it is $\left(\tfrac{1}{1-x}\right)^{k}$.

How to apply it

1. Model: write the OGF as a product/sum of simple pieces (one factor per independent choice or item type).
2. Simplify: factor and cancel to reach a known closed form. Algebraic simplification before expanding usually saves all the work.
3. Extract: expand each factor with the series above, then read off $[x^{n}]$ using convolution.

The same recipe solves linear recurrences: multiply the recurrence by $x^{n}$, sum, solve for $A(x)$, do partial fractions, and extract coefficients.

Mini-example (konkur 1402, Q111)

Find $a_9$ where $f(x) = \dfrac{1 + x^{3}}{(1 + x)^{3}}$. Simplify first using $1 + x^{3} = (1+x)(1 - x + x^{2})$:

$f(x) = \frac{(1+x)(1 - x + x^{2})}{(1+x)^{3}} = \frac{1 - x + x^{2}}{(1+x)^{2}}.$

Expand $\dfrac{1}{(1+x)^{2}} = \sum (-1)^{n}(n+1)x^{n}$ and convolve with $1 - x + x^{2}$:

$a_n = (-1)^{n}\big[(n+1) + n + (n-1)\big] = (-1)^{n}\,(3n) \quad (n \ge 2),$

so $a_9 = (-1)^{9}\cdot 27 = -27$.

Exam trick: Always factor and cancel before expanding. A scary rational function like $\frac{1+x^3}{(1+x)^3}$ usually collapses to a tiny polynomial over a low power of $(1\pm x)$, so the coefficients grow only polynomially in $n$ — distrust any answer choice that grows like $2^{n}$.