Overview

Generating functions encode sequences into algebraic objects. Even simple applications can simplify counting and recurrence problems.

Key Ideas

• The coefficient of $x^n$ in $(1+x+x^2+\cdots)^k$ counts solutions to $x_1+\cdots+x_k=n$ with nonnegative integers.
• Finite options become finite polynomials like $(1+x+x^2)$.
• Multiplying series corresponds to combining choices.

Core Skills

Translate Choices to Factors

Each variable contributes a factor $(1+x+x^2+\cdots)$ or a finite polynomial depending on constraints.

Extract Coefficients

Use known expansions like $(1-x)^{-k}$ or binomial coefficients to read off coefficients.

Use Truncation

When only low-degree terms matter, ignore higher powers after expansion.

Worked Example

Count solutions to $a+b+c=5$ with $a,b,c\ge0$.

The generating function is $(1+x+x^2+\cdots)^3=\frac{1}{(1-x)^3}$. The coefficient of $x^5$ is $\binom{5+3-1}{3-1}=21$.

More Examples

Example 1: Bounded Variables

Count solutions to $x+y+z=4$ with $0\le x,y,z\le 2$.

Use $(1+x+x^2)^3$ and extract the $x^4$ coefficient.

Example 2: Distinct Parts

Count partitions of $n$ into distinct parts.

Use the generating function $\prod_{k\ge1}(1+x^k)$.

Example 3: Recurrence Extraction

If $A(x)=\frac{1}{1-x-x^2}$, then the coefficients satisfy Fibonacci.

Strategy Checklist

• Translate each constraint into a factor.
• Use binomial series for $(1-x)^{-k}$.
• Truncate when only a few coefficients are needed.

Practice Problems