Discrete Math · Undergraduate
Generating Functions: Counting with Power Series
Quick answer
A generating function stores a whole sequence a₀, a₁, a₂, … as one power series a₀ + a₁x + a₂x² + ⋯. Multiplying generating functions combines choices: the coefficient of xⁿ in a product counts the ways to make a total of n. So making change, distributing objects and rolling dice become questions about coefficients. A recurrence turns into an equation for the generating function, and solving it gives a closed form, such as x/(1 − x − x²) for the Fibonacci numbers.
What you'll learn
- Write the generating function of a simple sequence
- Count combinations as coefficients of a product
- Count solutions of a + b + c = n with and without upper limits
- Turn a recurrence into an equation for its generating function
A sequence as one function
The generating function of a sequence is the power series
The only holds places: sits on . Some standard ones:
| Sequence | Generating function |
|---|---|
| , for |
Why multiplying counts combinations
Suppose lists the ways to pick some of item A and the ways for item B. In the product, . The coefficient of in collects every pairing whose amounts add to , which is exactly the number of ways to make a total of . Exponents add while coefficients multiply, so counting turns into algebra. The same rule underlies the binomial theorem: chooses, for each of items, either (leave it) or (take it).
Worked examples
Common mistakes
Practice problems
-
Write the generating function of .
Answer
Full solution
A geometric series with ratio .
-
Find the coefficient of in .
Answer
Full solution
Count from with sum : the orders of and .
-
How many nonnegative solutions does have?
Answer
Full solution
.
-
In how many ways can you pay cents with nickels and dimes?
Answer
Full solution
Three nickels, or one dime and one nickel: the coefficient of in .
-
Two dice: what generating function counts the totals, and how many ways give ?
Answer
; ways
Full solution
The coefficient of counts pairs .
-
Which sequence has generating function ?
Answer
Full solution
The binomial coefficients .
-
Find the generating function of , .
Answer
Full solution
, so .
-
A student counts solutions of with each at most as . What went wrong?
Answer
The upper limits were ignored; the answer is .
Full solution
counts all nonnegative solutions. Inclusion–exclusion, or the factor , removes those with a value above .
Frequently asked questions
What is a generating function?
The power series G(x) = a₀ + a₁x + a₂x² + ⋯ whose coefficients are the terms of a sequence. The x is a placeholder; the coefficients carry the information.
Why does multiplying generating functions count combinations?
When two series are multiplied, the coefficient of xⁿ collects every way to pick xⁱ from one and xʲ from the other with i + j = n.
What is the generating function of 1, 1, 1, …?
1/(1 − x) = 1 + x + x² + ⋯, the geometric series.
How many nonnegative solutions does a + b + c = n have?
C(n + 2, 2), the coefficient of xⁿ in 1/(1 − x)³.
What is the generating function of the Fibonacci numbers?
x/(1 − x − x²), found by using Fₙ = Fₙ₋₁ + Fₙ₋₂ to relate F(x) to xF(x) and x²F(x).