Generating functions turn sequences into power series β and then algebra does the counting for you. Multiply polynomials, and the coefficients give you the number of combinations. It sounds abstract, but it's one of the most powerful tools in combinatorics for solving "how many ways to make change" and recurrence problems.
The ordinary generating function (OGF) of a sequence \(a_{0}, a_{1}, a_{2}, ...\) is:
\[ A(x) = \sum_{n=0}^{\infty} a_n x^n \]
The coefficient of \(x^n\), denoted \([x^n]A(x)\), equals \(a_n\).
We encode the sequence as a power series, then manipulate the series algebraically.
"How many ways to make 10 cents using pennies (1Β’) and nickels (5Β’)?"
Pennies generating function: \(1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}\) (each term \(x^k\) = using k pennies)
Nickels generating function: \(1 + x^5 + x^{10} + \cdots = \frac{1}{1-x^5}\) (each term \(x^{5k}\) = using k nickels)
Multiply them: \((1+x+x^2+\cdots)(1+x^5+x^{10}+\cdots)\). The coefficient of \(x^{10}\) is the answer.
Why multiply? Each combination of k pennies + m nickels contributes 1 to \(x^{k+5m}\).
The workhorse of generating functions:
\[ \frac{1}{1-x} = 1 + x + x^2 + x^3 + ... = \sum_{n=0}^{\infty} x^n \]
More generally:
\[ \frac{1}{1-x^k} = 1 + x^k + x^{2k} + x^{3k} + ... \]
And the generalized binomial theorem for negative exponents:
\[ \frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n \]
Note: \(\binom{n+k-1}{k-1}\) is the stars-and-bars formula! Generating functions derive it automatically.
For each type of item/choice, create a factor where the exponent represents the "weight" (cost, number, value) and the coefficient represents how many ways to achieve that weight with that item type.
Multiply all factors together. The coefficient of \(x^n\) in the product = number of ways to achieve total weight n.
Convolution of sequences β multiplication of generating functions.
Ordinary (OGF): \(A(x) = \sum a_n x^n\) β for unlabeled objects, combinations, integer partitions.
Exponential (EGF): \(A(x) = \sum a_n \frac{x^n}{n!}\) β for labeled objects, permutations, set partitions.
Rough rule: if order matters in the combined structure, use EGF; if not, use OGF.
For competition math, ordinary generating functions are usually what you need.
Method: take recurrence \(\to\) multiply by \(x^n\) \(\to\) sum over n \(\to\) solve for \(G(x)\) \(\to\) expand \(\to\) read off coefficients.
Example: Fibonacci. \(F_n = F_{n-1} + F_{n-2}\), \(F_0 = 0\), \(F_1 = 1\).
\(G(x) = \dfrac{x}{1-x-x^2}\)
Expanding gives the Fibonacci numbers as coefficients.
This is a systematic way to solve any linear recurrence.
Generating functions give elegant proofs of identities like Vandermonde:
\((1+x)^m(1+x)^n = (1+x)^{m+n}\)
Coefficient of \(x^k\) on left: \(\sum \binom{m}{i}\binom{n}{k-i}\). On right: \(\binom{m+n}{k}\). Hence Vandermonde.
Many identities fall out by computing the same product two ways.
Number of non-negative integer solutions to \(x_1 + x_2 + \cdots + x_k = n\).
Each variable: \(1 + x + x^2 + \cdots = \frac{1}{1-x}\)
Product: \(\frac{1}{(1-x)^k} = \sum \binom{n+k-1}{k-1} x^n\)
Coefficient of \(x^n = \binom{n+k-1}{k-1}\). There's the stars-and-bars formula, derived automatically!
Generating function approach: multiply factors for each coin type.
Step 1: Build generating function for each coin.
1-cent coins: can use 0, 1, 2, ... of them. Factor \(= 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + \cdots\)
2-cent coins: can use 0, 1, 2, ... of them. Each contributes 2 to total. Factor \(= 1 + x^2 + x^4 + x^6 + \cdots\)
Step 2: Multiply and find coefficient of \(x^6\).
\((1 + x + x^2 + x^3 + x^4 + x^5 + x^6)(1 + x^2 + x^4 + x^6)\)
Step 3: Compute \(x^6\) terms.
\(x^0 \times x^6 = x^6\) (0 pennies, 3 two-cent)
\(x^2 \times x^4 = x^6\) (2 pennies, 2 two-cent)
\(x^4 \times x^2 = x^6\) (4 pennies, 1 two-cent)
\(x^6 \times x^0 = x^6\) (6 pennies, 0 two-cent)
Coefficient = 4 ways
List them: \(\{6 \times 1Β’\}, \{4 \times 1Β’ + 1 \times 2Β’\}, \{2 \times 1Β’ + 2 \times 2Β’\}, \{3 \times 2Β’\}\) = 4 ways β
Answer: 4
Each die: generating function \(x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6}\) (exponent = face value).
Step 1: One die: \(x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6}\)
Step 2: Two dice: square it.
\[ (x + x^2 + x^3 + x^4 + x^5 + x^6)^2 \]
Step 3: Find coefficient of \(x^7\).
We need pairs \((i, j)\) where \(i + j = 7\), with \(1 \leq i,j \leq 6\).
(1,6), (2,5), (3,4), (4,3), (5,2), (6,1) = 6 pairs
Coefficient of \(x^7 = 6\)
Direct check: 6 ordered pairs give sum 7. Same answer β
Why it works: When you multiply, each \(x^i\) from first die times \(x^j\) from second die gives \(x^{i+j}\). The total coefficient of \(x^7\) counts all such pairs β exactly the number of ways to roll sum = 7.
Answer: 6
Each variable has generating function \(1 + x + x^2 + \cdots = \frac{1}{1-x}\). Three variables: \(\frac{1}{(1-x)^3}\).
Step 1: Generating function per variable.
Variable a: can be 0, 1, 2, ... \(\to\) factor \(= 1 + x + x^2 + x^3 + x^4 + \cdots\)
Same for b and c.
Step 2: Product = \((1 + x + x^2 + \cdots)^3 = \frac{1}{(1-x)^3}\)
Step 3: Generalized binomial theorem:
\[ \frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n \]
With k = 3, coefficient of \(x^4 = \binom{4+3-1}{3-1} = \binom{6}{2}\)
\[ \binom{6}{2} = \frac{6 \times 5}{2} = 15 \]
Stars and bars check: n=4 stars, k=3 bins \(\to\) 2 bars. \(\binom{4+3-1}{3-1} = \binom{6}{2} = 15\) β
Answer: 15