Generating Functions
A generating function encodes a sequence a0, a1, a2, … as the coefficients of a power series A(x) = a0 + a1x + a2x2 + …, so that counting problems become algebra with polynomials and series. In brief: the generating function of the sequence 1, 1, 1, … is 1/(1 − x), and that of the binomial coefficients C(n, k) for fixed n is (1 + x)n. The coefficient of xk in (1 + x)5 is C(5, k): 1, 5, 10, 10, 5, 1.
Generating functions turn the multiplication principle into the multiplication of polynomials: the number of ways to get a total of k from several independent choices is the coefficient of xk in the product of the generating functions of the choices. They also solve recurrences such as the Fibonacci numbers. This guide introduces the idea, shows the standard generating functions, explains how to count with them, how to solve recurrences and gives a table of the main series.
What is a generating function?
For a sequence (an), the (ordinary) generating function is the formal power series A(x) = Σ anxn. The variable x is a placeholder: its powers keep track of the index. In the formal approach, we do not care about the convergence of the series, only about the coefficients. We can add and multiply the series: if A(x) = Σ anxn and B(x) = Σ bnxn, then the coefficient of xn in A(x)B(x) is the convolution cn = a0bn + a1bn−1 + … + anb0. This is exactly the count of the ways to split a total n into two parts, one counted by a and the other by b.
What are the basic generating functions?
- 1, 1, 1, 1, …: 1 + x + x2 + … = 1/(1 − x).
- 1, a, a2, …: 1/(1 − ax).
- C(n, k) for fixed n: (1 + x)n.
- 1, 2, 3, 4, …: 1/(1 − x)2 (the derivative of 1/(1 − x), shifted).
- C(n + k − 1, k) for k = 0, 1, 2, …: 1/(1 − x)n (combinations with repetition).
- 1/k!: the exponential generating function ex = Σ xk/k!, used for arrangements.
How do you count with generating functions?
Build a polynomial for each independent choice. The exponent of x records the contribution of the choice to the total. Multiply the polynomials, and read off the coefficient of the desired power.
Example 1: dice
One die: x + x2 + x3 + x4 + x5 + x6. For two dice, square it: x2 + 2x3 + 3x4 + 4x5 + 5x6 + 6x7 + 5x8 + 4x9 + 3x10 + 2x11 + x12. The coefficient of x7 is 6: there are 6 ways to roll a sum of 7 out of 36, so the probability is 1/6.
Example 2: coins
In how many ways can you make 10 cents with 1-cent and 5-cent coins (unlimited)? The generating function is 1/((1 − x)(1 − x5)). The ways are: 10 ones, 5 ones + 1 five, 2 fives: three ways. With 1-, 5- and 10-cent coins, multiply also by 1/(1 − x10): the coefficient of x10 is 4 (the three above and one ten).
Example 3: distributing objects
The number of ways to distribute 6 identical sweets to 3 children, each receiving at most 3: the coefficient of x6 in (1 + x + x2 + x3)3. Expand (1 + x + x2 + x3)3 = 1 + 3x + 6x2 + 10x3 + 12x4 + 12x5 + 10x6 + 6x7 + 3x8 + x9. So the answer is 10. Check by listing (3, 3, 0) in 3 orders, (3, 2, 1) in 6 orders, (2, 2, 2) in 1 order: 3 + 6 + 1 = 10 ✓.
Example 4: integer solutions
The number of solutions of x1 + x2 + x3 = 10 with nonnegative integers is the coefficient of x10 in 1/(1 − x)3, which is C(12, 2) = 66, matching the stars-and-bars count.
How do you solve a recurrence?
- Multiply the recurrence by xn and sum over n to get an equation for A(x).
- Solve for A(x) as a rational function.
- Decompose into partial fractions.
- Expand each part into a geometric series and read off an.
Example 5: a simple recurrence
a0 = 1 and an = 3an−1 for n ≥ 1. Then A(x) = 1 + 3xA(x), so A(x) = 1/(1 − 3x) = Σ 3nxn, and an = 3n.
Example 6: the Fibonacci numbers
F0 = 0, F1 = 1 and Fn = Fn−1 + Fn−2. Let F(x) = Σ Fnxn. Then F(x) − x = xF(x) + x2F(x), so F(x) = x/(1 − x − x2). The roots of the denominator are related to the golden ratio φ = (1 + √5)/2 and ψ = (1 − √5)/2: 1 − x − x2 = (1 − φx)(1 − ψx). Partial fractions give F(x) = (1/√5)[1/(1 − φx) − 1/(1 − ψx)], so Fn = (φn − ψn)/√5 (Binet’s formula). Check: F10 = (122.99 − 0.0081)/2.236 = 55 ✓.
Example 7: a recurrence with a constant
a0 = 0 and an = 2an−1 + 1. Then A(x) = 2xA(x) + x/(1 − x), so A(x) = x/((1 − x)(1 − 2x)) = 1/(1 − 2x) − 1/(1 − x). Therefore an = 2n − 1: 0, 1, 3, 7, 15, …, the number of moves in the Tower of Hanoi.
Table of generating functions
| Sequence an | First terms | Generating function |
|---|---|---|
| 1 | 1, 1, 1, 1, … | 1/(1 − x) |
| rn | 1, r, r2, … | 1/(1 − rx) |
| n + 1 | 1, 2, 3, 4, … | 1/(1 − x)2 |
| C(5, n) | 1, 5, 10, 10, 5, 1 | (1 + x)5 |
| Fibonacci Fn | 0, 1, 1, 2, 3, 5, … | x/(1 − x − x2) |
| 2n − 1 | 0, 1, 3, 7, 15, … | x/((1 − x)(1 − 2x)) |
| 1/n! (exponential) | 1, 1, 1/2, 1/6, … | ex |
Where do generating functions come from?
Abraham de Moivre introduced the idea of generating functions in 1730 to solve recurrences such as the one for the Fibonacci numbers. Euler used them extensively in the study of partitions of integers, and Laplace gave the method its name fonctions génératrices in his work on probability in the 1810s. In the twentieth century they became a standard tool of combinatorics, as in the works of Pólya and Wilf, who described a generating function as “a clothesline on which we hang up a sequence of numbers for display”.
Where are they used today?
Generating functions are used to count combinatorial structures, to analyse algorithms (the average running time of sorting methods) and in probability, where the probability generating function of a random variable encodes its distribution and gives the mean and variance by differentiation. In electrical engineering and control, the related z-transform converts recurrences describing digital filters into algebraic equations.
Which mistakes are common?
Worrying about convergence in the formal setting
In counting problems, x is a formal symbol. What matters are the coefficients. Convergence matters only when you substitute numbers for x.
Forgetting the offsets
1/(1 − x)2 has coefficients n + 1 (starting from n = 0), not n. Check the first terms.
Using the wrong factor for coin problems
A coin of value v contributes 1/(1 − xv) for an unlimited supply, not 1/(1 − x).
Expanding the product incompletely
When multiplying polynomials, collect all terms of the desired power. Check the total: for (1 + x + x2 + x3)3 the coefficients add up to 43 = 64.