1
Coefficients are the answers
[xᵏ]G(x) — the coefficient of xᵏ — is the count for size k. The whole sequence travels together.
Lesson · Combinatorics and Counting · Technique
Generating Functions
A generating function packs a counting sequence into one formal power series. Multiplying series corresponds to combining choices, so a counting problem becomes an algebra problem.
G(x) = a₀ + a₁x + a₂x² + … the sequence, packed
1/(1−x) = 1 + x + x² + … any number of one type
(1+x)ⁿ = Σ C(n,k) xᵏ at most one of each of n types
MULTIPLY series ⟷ COMBINE independent choices
A sequence as one object
Core ideas
What this lesson establishes
The idea is a change of representation: turn a sequence into a function so that operations on sequences become arithmetic.
2
Multiplication is combination
Multiplying two generating functions convolves their coefficients, which is exactly "choose some from the first source and the rest from the second".
3
The series is formal
Convergence is irrelevant. x is a bookkeeping symbol and the series is a way of writing an infinite sequence, not a function to be evaluated.
The material
Generating functions
The definition, the basic series, and two problems solved by algebra.
Definition · Ordinary generating function
For a sequence a₀, a₁, a₂, …, its generating function is the formal power series G(x) = Σ_{k≥0} a_k x^k. Two series are equal exactly when all their coefficients agree.
1/(1 − x) = 1 + x + x² + x³ + … all a_k = 1
1/(1 − x)² = 1 + 2x + 3x² + 4x³ + … a_k = k+1
1/(1 − ax) = 1 + ax + a²x² + … a_k = aᵏ
(1 + x)ⁿ = Σ_k C(n,k) xᵏ binomial
1/(1 − x)ⁿ = Σ_k C(n+k−1, k) xᵏ stars and bars!
(1 − xᵐ⁺¹)/(1 − x) = 1 + x + … + xᵐ at most m copies
The fifth line is “Combinations with Repetition” in a different notation, and that is the point of the method: 1/(1−x)ⁿ encodes "choose any number from each of n types", and its coefficients are exactly the stars-and-bars counts.
Why multiplication combines choices
If A(x) counts the ways to pick items from source 1 and B(x) from source 2, then the coefficient of xᵏ in A(x)B(x) is Σ_j a_j b_{k−j} — take j items from the first source and k − j from the second, over all splits. That is precisely the product rule combined with the sum rule.
Example · Coins
In how many ways can n cents be made from pennies, nickels and dimes? Each denomination contributes a factor: 1/(1−x) for pennies, 1/(1−x⁵) for nickels, 1/(1−x¹⁰) for dimes. The answer is the coefficient of xⁿ in the product. For n = 25 it is 12.
Example · A restricted selection
How many ways to choose 10 items from 4 types with at most 3 of each? Each type contributes 1 + x + x² + x³, so the answer is [x¹⁰](1 + x + x² + x³)⁴. Expanding gives 10. Check it another way: a selection is short of the maximum 12 by 2, spread over four types, and “Combinations with Repetition” counts those spreads as C(5, 2) = 10. Inclusion and exclusion would also work; the generating function encodes the constraint directly.
Solving a recurrence
Generating functions solve recurrences by turning them into equations. For aₙ = 3aₙ₋₁ with a₀ = 1, write G(x) = Σ aₙxⁿ. Multiplying the recurrence by xⁿ and summing gives G(x) − 1 = 3xG(x), so G(x) = 1/(1 − 3x), whose coefficients are 3ⁿ.
The same method handles Fibonacci: G(x) = x/(1 − x − x²), and a partial-fraction decomposition recovers Binet's formula from “Solving Linear Recurrences” in Induction and Recursion. The method is more general than characteristic roots, and it extends to recurrences those cannot touch.
Theorem · Formal manipulation is legitimate
Addition, multiplication and (when a₀ ≠ 0) inversion of formal power series are well defined coefficient by coefficient, with no convergence question, because each coefficient of a product depends on finitely many coefficients of the factors.
Interactive
The four counting rules
Enumerated while enumeration is possible
Method
Using a generating function
One factor per source of choice.
1
Write a factor for each source
Unlimited supply gives 1/(1−x); at most one gives 1 + x; at most m gives 1 + x + ⋯ + x^m; multiples of d only gives 1/(1−x^d).
2
Multiply the factors
The product's coefficients count the combined selections, by the convolution argument above.
3
Extract the coefficient you need
By expansion, by a known series, or by partial fractions. This is where the algebra lives.
4
Check against a direct count
For small n the answer should match an enumeration. A generating function set up wrongly produces a confident wrong series.
Generating functions
Score 0 / 0Choose the answer you can justify.
Making 25 cents
Pennies, nickels and dimes, unlimited supply.
G(x) = 1/(1−x) · 1/(1−x⁵) · 1/(1−x¹⁰)
We need [x²⁵]G(x). Split by the number of dimes:
0 dimes: 25 cents from pennies and nickels
nickels 0..5 → 6 ways
1 dime: 15 cents from pennies and nickels
nickels 0..3 → 4 ways
2 dimes: 5 cents from pennies and nickels
nickels 0..1 → 2 ways
total 6 + 4 + 2 = 12
The generating function ENCODES this split; the case analysis is
what extracting the coefficient amounts to.
For 25 cents the case split is quicker than the algebra. The generating function earns its place when the target is symbolic — it gives the answer for every n at once, and the cases would have to be redone for each.
Common mistakes
1
Worrying about convergenceThese are formal series. x never takes a value, and each coefficient depends on finitely many others.
2
Using the wrong factor for a constraint"At most m" is a polynomial with m+1 terms; "multiples of d" is 1/(1−x^d). Getting the factor wrong makes the whole product count something else.
3
Reaching for generating functions on a small problemFor one specific n, a case split is usually faster. The method pays when the answer must hold for all n.
Check your understanding
✓
Finish when you can write the generating function for a constrained selection.
Write the generating function for making n cents from pennies, nickels and quarters with at most three of each, and extract the coefficient for n = 30. The factors are where the constraints live.
Note: Exponential generating functions Σ aₙxⁿ/n! are the right tool when the objects are labelled and order matters, and they turn the derangement recurrence into a two-line calculation. This lesson stays with the ordinary kind, which suits unlabelled selection problems.