Generating Functions
The Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, 21... can be compressed into a single elegant fraction: x/(1 - x - x^2). That fraction is a generating function — a way of encoding an entire infinite sequence as a formal power series. Generating functions let you use algebraic tricks (addition, multiplication, partial fractions) to solve counting problems that would otherwise require laborious recursion or brute-force enumeration.
What You'll Learn
- Define an ordinary generating function (OGF) and read off sequence terms from its power series expansion - Use the closed form 1/(1-x) = 1 + x + x^2 + ... and variations to build OGFs for common sequences - Multiply generating functions to solve combinatorial counting problems - Derive the OGF for the Fibonacci sequence using recurrence relations - Distinguish ordinary from exponential generating functions (EGFs)
What Is a Generating Function?
Given a sequence a_0, a_1, a_2, a_3, ..., its ordinary generating function (OGF) is the formal power series: A(x) = a_0 + a_1*x + a_2*x^2 + a_3*x^3 + ... The word 'formal' is crucial. We are not treating x as a number we plug in — we treat the series as an algebraic object where x is just a placeholder. The coefficient of x^n in A(x) is exactly a_n. Example 1: The all-ones sequence 1, 1, 1, 1, ... A(x) = 1 + x + x^2 + x^3 + ... = 1/(1-x) (geometric series formula, |x| < 1) Example 2: The sequence 1, 2, 3, 4, ... (natural numbers) B(x) = 1 + 2x + 3x^2 + 4x^3 + ... = 1/(1-x)^2 This follows because d/dx [1/(1-x)] = 1/(1-x)^2, and differentiating the geometric series gives 1 + 2x + 3x^2 + ...
Building Generating Functions from Known Forms
A handful of closed-form identities power most generating function work. Know these cold: 1/(1-x) = sum_{n>=0} x^n [all-ones sequence] 1/(1-ax) = sum_{n>=0} a^n * x^n [geometric sequence with ratio a] 1/(1-x)^k = sum_{n>=0} C(n+k-1, k-1) * x^n [combinations with repetition] (1+x)^n = sum_{k=0}^{n} C(n,k) * x^k [binomial theorem] To use these: identify what your sequence looks like, find the matching closed form, and extract coefficients. For example, to find [x^5] in 1/(1-2x)^3 (the coefficient of x^5), use form (3): a_n = C(n+2, 2) * 2^n. At n=5: C(7,2) * 32 = 21 * 32 = 672.
The notation [x^n] A(x) means 'the coefficient of x^n in A(x).' This is a useful shorthand. For instance, [x^3] in 1/(1-x)^2 is the coefficient of x^3, which equals 4 (since the sequence is 1, 2, 3, 4, ...). This notation makes many arguments cleaner to write.
Multiplying Generating Functions: Combining Counts
When you multiply two generating functions A(x) * B(x), the coefficient of x^n in the product is: [x^n](A*B) = sum_{k=0}^{n} a_k * b_{n-k} (convolution) This is the key combinatorial insight: if a_k counts the ways to do Task 1 in k steps, and b_{n-k} counts the ways to do Task 2 in n-k steps, then [x^n](A*B) counts all ways to split n steps between the two tasks. Concrete example: How many ways can you make $n in change using only pennies and nickels (unlimited supply)? - Pennies: 1/(1-x) (each x^k represents using k pennies) - Nickels: 1/(1-x^5) (each x^(5j) represents using j nickels) - Combined: 1/[(1-x)(1-x^5)] - [x^n] of this product counts the number of ways to make n cents in change.
The Fibonacci OGF: A Recurrence Solved
The Fibonacci numbers satisfy F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} for n >= 2. Let F(x) = sum_{n>=0} F_n * x^n. We use the recurrence to find a closed form. Step 1: Write F(x) - x*F(x) - x^2*F(x): - F(x) = F_0 + F_1*x + F_2*x^2 + F_3*x^3 + ... - x*F(x) = F_0*x + F_1*x^2 + F_2*x^3 + ... - x^2*F(x) = F_0*x^2 + F_1*x^3 + ... Step 2: For n >= 2, the coefficient of x^n in F(x) - x*F(x) - x^2*F(x) is: F_n - F_{n-1} - F_{n-2} = 0 (by the recurrence!) Step 3: The surviving terms are from n=0 and n=1: F(x)(1 - x - x^2) = F_0 + (F_1 - F_0)x = 0 + 1*x = x Step 4: Solve: F(x) = x / (1 - x - x^2) This is the generating function for Fibonacci numbers. To find F_n, you can use partial fraction decomposition and the quadratic formula on 1 - x - x^2.
Exponential Generating Functions
Ordinary generating functions work well for combinations (unordered selections). When counting permutations (ordered arrangements), exponential generating functions (EGFs) are more natural. The EGF of a sequence a_0, a_1, a_2, ... is: A(x) = sum_{n>=0} a_n * (x^n / n!) Key example: The EGF of the all-ones sequence 1, 1, 1, ... is: sum_{n>=0} x^n/n! = e^x This is why the EGF for the number of permutations of n elements (which is n!) is: sum_{n>=0} n! * x^n/n! = sum_{n>=0} x^n = 1/(1-x) The division by n! 'absorbs' the factorial counting of orderings, letting you use exponential series identities (like e^x * e^x = e^{2x}) to combine counts.
Match each generating function to the sequence it encodes:
Terms
Definitions
Drag terms onto their definitions, or click a term then click a definition to match.
Using the identity 1/(1-ax) = sum a^n x^n, what is the coefficient of x^4 in 1/(1-3x)?
Why does multiplying two generating functions A(x)*B(x) count combined outcomes?
Derive and Use a Generating Function
Work through this problem step by step. 1. Write the OGF for the number of ways to select n objects from two bins: Bin A (unlimited red balls) and Bin B (unlimited blue balls). Hint: each bin contributes 1/(1-x). 2. Multiply the two generating functions. What closed form do you get? What sequence do its coefficients represent? 3. Now change the problem: Bin A has at most 3 red balls (you can choose 0, 1, 2, or 3). Write its generating function as a finite polynomial. Multiply by 1/(1-x) for Bin B. What is the coefficient of x^5 in the product? 4. Extension: Write the generating function for the number of ways to make change for n cents using pennies, nickels, and dimes only. You do not need to expand it — just write the closed form. Deliverable: Written work showing each step, your final generating functions, and the coefficient you found in step 3.
Flashcards — click each card to reveal the answer
Want to keep learning?
Sign up for free to access the full curriculum — all subjects, all ages.
Start Learning Free