Generating Functions is the habit of encoding counts as coefficients of power series so algebra can solve counting problems. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
Pack a counting sequence into the coefficients of a power series so that algebra on the series does the counting.
Why It Works
1
Represent each choice by a polynomial whose exponents are the possible 'sizes' contributed by that choice.
2
Multiplying such polynomials adds exponents, so the coefficient of $x^n$ in the product counts every way to reach total $n$ — this is the multiplication principle in disguise.
3
For an item available in any amount of size $1$, its factor is $1 + x + x^2 + \cdots = \dfrac{1}{1 - x}$.
4
Read off the answer as the coefficient $[x^n]$ of the resulting series, often via the binomial/geometric expansions.
Worked Examples
Example 1
Using coins worth $1$ and $2$ (unlimited supply, order does not matter), how many ways are there to make $4$?
1
Coin of value $1$ contributes the factor $1 + x + x^2 + x^3 + x^4 + \cdots$; coin of value $2$ contributes $1 + x^2 + x^4 + \cdots$.
2
The number of ways to make $4$ is $[x^4]\,\dfrac{1}{(1-x)(1-x^2)}$.
3
Expand the product up to $x^4$: the $x^4$ terms come from $(\text{four } 1\text{s}),\ (\text{two } 1\text{s} + \text{one } 2),\ (\text{two } 2\text{s})$.
4
That is $3$ ways: $4 = 1{+}1{+}1{+}1 = 1{+}1{+}2 = 2{+}2$.
Answer:
$3$
Warm-up
Using the generating function $(1 + x)^n$, find the coefficient of $x^3$ in $(1 + x)^7$.
1
By the binomial theorem, $(1 + x)^n = \sum_{k} \binom{n}{k} x^k$, so $[x^k](1+x)^n = \binom{n}{k}$.
2
Here $n = 7$ and $k = 3$, so the coefficient is $\binom{7}{3}$.
The coefficient of $x^r$ on the right is $\binom{m+n}{r}$ by the binomial theorem.
3
On the left, multiplying the series, $[x^r]$ collects all ways to take $x^k$ from the first factor (coefficient $\binom{m}{k}$) and $x^{r-k}$ from the second (coefficient $\binom{n}{r-k}$), summed over $k$.
4
Equating the two expressions for $[x^r]$ gives $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$.
Generating functions turn combinatorial constraints into algebra: a part available with multiplicities in a set $S$ contributes the factor $\sum_{s \in S} x^s$, and multiplying factors performs the 'choose one option from each' product automatically. Key tools are the geometric series $\frac{1}{1-x} = \sum x^n$, its derivative-shifted form $(1-x)^{-k} = \sum \binom{n+k-1}{k-1} x^n$, and the finite sum $1 + x + \cdots + x^{m} = \frac{1-x^{m+1}}{1-x}$ for bounded supplies.
They unify partition counting, coin/change problems, dice-sum distributions, and binomial-identity proofs (Vandermonde, the binomial theorem itself), and exponential generating functions handle labeled structures and permutations. On harder contests they convert a recurrence into a closed form by solving for the series.
Pitfall: track the support of each factor carefully — a bounded supply uses the finite polynomial $\frac{1-x^{m+1}}{1-x}$, not the infinite $\frac{1}{1-x}$, and the $(1-x^{m+1})$ numerator must be expanded (its terms subtract overcounted cases). Forgetting the numerator, or mismatching 'order matters' (use a product) with 'order does not' (use distinct factors per part type), are the standard errors.
Spot the Signal
Look for problems where the key step is encoding counts as coefficients of power series so algebra can solve counting problems.
You can describe the hard part as encoding counts as coefficients of power series so algebra can solve counting problems, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the counting object that calls for generating functions, then rewrite the givens around it.
Name the relation that makes Generating Functions legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Generating Functions just because the surface looks familiar; verify the required condition first.
Applying Generating Functions because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let generating functions reveal the counting structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is encoding counts as coefficients of power series so algebra can solve counting problems.