Generating functions: turning a counting problem into a product

Generating functions are usually explained backwards. You are shown $\frac{1}{1-x} = 1 + x + x^2 + \cdots$, warned that it does not converge, told the warning does not matter, and then handed a problem. What is missing is the part you actually need in a contest: when to reach for one, what to write down, and how to get a number out without doing partial fractions.

So this is the method, not the definition.

The one sentence that carries everything

A generating function is a filing cabinet. The coefficient of $x^n$ is the answer for total $n$, and $x$ is never substituted for anything; it is only there to keep the drawers apart.

The reason this is useful is one fact about multiplication. The coefficient of $x^n$ in a product $A(x)B(x)$ is $\sum_k a_k b_{n-k}$, which reads in English as take some from the first pile and some from the second, and add the sizes. That is exactly what independent choices do. So:

1. One factor per kind of thing you are choosing.
2. Exponents record cost. An item that adds $w$ to the total contributes $x^w$.
3. Multiply, then read off the coefficient of $x^n$.

That is the whole procedure. Everything below is either the dictionary for step 1 or the arithmetic for step 3.

Three signals that a counting problem is this problem

• The total is a sum of weights. Coins summing to an amount, dice summing to a score, part sizes summing to $n$. If the thing being constrained is a total, exponents can carry it.
• The constraint is per item, not global. "Each part may be used at most twice" is a property of one part on its own, so it becomes one factor. "The largest part is twice the smallest" relates two parts and cannot be a factor.
• You want one specific total, but nothing about the setup depends on which total. The product is built once and answers every $n$ at the same time, which is why it beats casework the moment the question is asked twice.

The dictionary

For a single item of size $w$, the constraint on how many copies you may take translates directly:

• Any number of copies: $\frac{1}{1-x^w} = 1 + x^w + x^{2w} + \cdots$
• At most one copy: $1 + x^w$
• At most two copies: $1 + x^w + x^{2w}$
• A fixed number of copies, $k$ of them: $x^{kw}$
• A bounded number of copies, between $a$ and $b$: $x^{aw} + x^{(a+1)w} + \cdots + x^{bw}$
• An ordered sequence of parts, drawn from a set whose series is $P(x)$: $\frac{1}{1-P(x)}$

One identity is worth memorising because it converts a coefficient extraction into a binomial coefficient on sight: $\frac{1}{(1-x)^k}$ has coefficient $\binom{n+k-1}{k-1}$ at $x^n$. That is stars and bars wearing algebra, and if your product collapses to that shape you are already finished.

A first one, end to end

In how many ways can three standard dice sum to ten?

One die is $x + x^2 + x^3 + x^4 + x^5 + x^6$. Note the missing constant term: a die must show something, so "zero" is not an option, and the factor starts at $x^1$. Three dice are independent, so the answer is the coefficient of $x^{10}$ in $(x + x^2 + \cdots + x^6)^3$, which is $27$.

You could also get $27$ by casework, and on this problem casework is faster. The reason to write the product anyway is that it survives a change in the question. Four dice, or dice labelled $1,2,2,3,3,4$, or "at least one six" — each is a small edit to a factor, and none of them is a small edit to your casework.

Extraction without partial fractions

Nobody expands $\frac{1}{(1-x)(1-x^2)(1-x^5)}$ by partial fractions on a timed paper. You multiply the factors into a row of coefficients, one factor at a time, and the row is short because you only need up to $x^n$.

Start with the row for the empty selection: a $1$ in position $0$ and zeros everywhere else. Then, for each factor:

• Unlimited copies, the factor $\frac{1}{1-x^w}$: sweep $i$ upward and set $\text{row}[i] \mathrel{+}= \text{row}[i-w]$. You read the row you are currently writing.
• At most one copy, the factor $1 + x^w$: take a copy of the row first, then set $\text{new}[i] = \text{old}[i] + \text{old}[i-w]$. You read the row as it was before this factor.

That distinction is the single mistake people make with this method, and it is invisible once made: sweeping upward with an at-most-one factor silently grants you unlimited copies, and the answer comes out too big with nothing to point at. Test it on one factor. Allowing any number of $2$s gives a row with a $1$ in every even position; allowing at most one $2$ gives a row with a $1$ in positions $0$ and $2$ and nothing else. Same loop, different source row, completely different object.

Run it on coins of $1$, $2$ and $5$ making $25$. After the $1$s every entry is $1$. After the $2$s the row is $1,1,2,2,3,3,4,4,\ldots$ — each amount plus its own count two places back. After the $5$s the entry at $25$ is $42$, and that is the answer. Three sweeps of a $26$-entry row, no algebra.

The free sanity check

Take subsets of $\{1,2,\ldots,10\}$ and ask how many sum to $25$. Every element is in or out, so the product is $(1+x)(1+x^2)\cdots(1+x^{10})$ and the answer is the coefficient of $x^{25}$, which is $39$.

The coefficient of $x^{30}$ is also $39$, and not by accident. The whole set sums to $55$, so complementing a subset turns a sum of $25$ into a sum of $30$. The coefficient list is a palindrome, and the bijection producing it is exactly the complement map that proves $\binom{n}{k} = \binom{n}{n-k}$. Whenever your factors are $1 + x^{w}$ across a full set, check the two ends of your row against each other before you trust the middle.

Two more things fall out of the same product for free. Ignoring the sums entirely — adding up every coefficient — gives $2^{10}$, which is just the count of subsets of a $10$-element set; the generating function is that count refined by total. And the row update for a factor $1+x$, $\text{new}[n] = \text{old}[n] + \text{old}[n-1]$, is Pascal's identity written as a loop. The method you are running by hand is the identity you already know.

When it is the wrong tool

• The answer is a single binomial coefficient. If the product is $\frac{1}{(1-x)^k}$, quote stars and bars and stop.
• The constraint relates two parts to each other. "All parts distinct" is fine, because it is per part: $\prod_{k \ge 1}(1 + x^k)$. "No two parts differ by exactly one" is not, and no amount of rearranging makes it a factor.
• The objects are labelled and order matters inside a part. That is the territory of exponential generating functions, which use $\frac{x^n}{n!}$ and are a genuinely different tool, not a variation.
• The count is small and structured. Constructive counting with a correction for overcounting is shorter than a product whenever you can describe the object in two or three choices.

What to practise

Do not practise expanding series. Practise the translation. Take twenty counting problems and write only the product for each — factors and the exponent you would extract — then stop and move to the next one. Ten minutes of that buys more than one fully worked example, because the product is the step you will get wrong under time pressure and the arithmetic is the step you will not.

Lemma teaches this as a named technique with the identities and the recognition rules attached: see generating functions for the statement and where it sits, and the technique index for the neighbours it trades against. The problem archive carries the combinatorics problems above in full, and the daily problem posts a fresh one every day in three difficulty tiers with no account needed.