Generating Functions

Why This Matters

Generating functions are the Swiss Army knife of combinatorics—they transform counting problems into algebraic ones, letting you manipulate sequences as easily as polynomials. You're being tested on your ability to encode combinatorial information, extract specific coefficients, and solve recurrence relations using these tools. The core insight is that a sequence isn't just a list of numbers; it's the coefficients of a power series, and everything you know about algebra suddenly applies.

This topic connects directly to recurrence relations, partition theory, probability distributions, and asymptotic analysis. When you see a counting problem on an exam, generating functions often provide the most elegant path to a closed-form solution. Don't just memorize the formulas—understand when to use an OGF versus an EGF, how convolution encodes combining independent choices, and why certain manipulations extract the information you need.

---

Foundational Structures

These are the building blocks—the different types of generating functions and when each one applies. The key distinction is whether your objects are labeled or unlabeled.

Ordinary Generating Functions (OGFs)

• Defined as $G(x) = \sum_{n=0}^{\infty} a_n x^n$—the sequence $(a_n)$ becomes the coefficients of a power series
• Best for unlabeled counting problems where order doesn't matter, such as combinations, selections with repetition, and partitions
• Multiplication corresponds to convolution—when you multiply two OGFs, you're combining independent choices

Exponential Generating Functions (EGFs)

• Defined as $G(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$—the factorial denominator accounts for labeling
• Best for labeled structures like permutations, arrangements, and labeled graphs
• Multiplication gives labeled product—combining EGFs counts ways to partition labels between two structures

Formal Power Series

• Series $f(x) = \sum_{n=0}^{\infty} a_n x^n$ treated purely algebraically—convergence is irrelevant
• Provides rigorous foundation for all generating function manipulations without analytic concerns
• Supports operations like composition and inversion—essential for advanced techniques like Lagrange inversion

---

Algebraic Operations

These techniques let you build complex generating functions from simple ones. Mastering these operations is how you translate combinatorial reasoning into algebraic calculation.

Generating Function Manipulations

• Addition: $A(x) + B(x)$ gives sequence $(a_n + b_n)$—use when counting objects of type A or type B
• Multiplication: $A(x) \cdot B(x)$ gives convolution $c_n = \sum_{k=0}^{n} a_k b_{n-k}$—use for independent choices
• Differentiation: $\frac{d}{dx}G(x)$ shifts and weights coefficients—extracts $n \cdot a_n$ or finds recurrence relationships

Convolution of Sequences

• Defined as $c_n = \sum_{k=0}^{n} a_k b_{n-k}$—counts ways to split $n$ items between two independent processes
• Encoded by multiplication of generating functions—this is why generating functions are powerful
• Appears constantly in counting problems—anytime you combine choices from two independent sets

Closed Forms of Common Generating Functions

• Geometric series: $\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$—the most fundamental closed form, gives $a_n = 1$
• Variants encode common sequences—$\frac{1}{(1-x)^k}$ gives $\binom{n+k-1}{k-1}$, the stars-and-bars formula
• Recognizing patterns is crucial—closed forms let you read off coefficients without expanding

---

Coefficient Extraction

Getting the answer means pulling out specific coefficients. These techniques convert your algebraic expression back into the number you're counting.

Coefficient Extraction Techniques

• Notation $[x^n]G(x)$ means "the coefficient of $x^n$"—this is your target in every problem
• Binomial theorem handles $(1+x)^n$ and $(1-x)^{-n}$—memorize the generalized binomial coefficients
• Cauchy's integral formula gives $a_n = \frac{1}{2\pi i} \oint \frac{G(z)}{z^{n+1}} dz$—powerful for asymptotic analysis

Partial Fraction Decomposition

• Breaks rational functions into simpler terms—$\frac{P(x)}{Q(x)}$ becomes sum of $\frac{A}{(x-r)^k}$ terms
• Each simple fraction has known coefficient extraction—$[x^n]\frac{1}{1-rx} = r^n$
• Essential for solving linear recurrences—the roots of the denominator determine the closed form

---

Solving Recurrences

Generating functions turn recurrence relations into algebraic equations. This is one of their most powerful applications.

Recurrence Relations and Generating Functions

• Multiply recurrence by $x^n$ and sum over all $n$—transforms the recurrence into an equation for $G(x)$
• Initial conditions become polynomial adjustments—handle them carefully when setting up the equation
• Solve for $G(x)$, then extract coefficients—partial fractions typically finishes the job

Solving Linear Recurrences

• Linear recurrences give rational generating functions—$a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$ yields $G(x) = \frac{P(x)}{Q(x)}$
• Characteristic roots appear in partial fractions—if $Q(x) = (1-r_1 x)(1-r_2 x)\cdots$, solution involves $r_i^n$ terms
• Repeated roots give polynomial factors—$\frac{1}{(1-rx)^2}$ contributes $n \cdot r^n$ to the solution

---

Advanced Extensions

These generalizations extend the basic framework to handle more complex problems. Each encodes additional structure in the generating function.

Bivariate Generating Functions

• Defined as $F(x,y) = \sum_{m,n} a_{m,n} x^m y^n$—tracks two parameters simultaneously
• Useful for two-dimensional counting—lattice paths, statistics on combinatorial objects
• Operations extend naturally—fix one variable to get a univariate function in the other

Generating Functions for Partitions

• Partition function $p(n)$ encoded by $\prod_{k=1}^{\infty} \frac{1}{1-x^k}$—each factor allows any number of parts of size $k$
• Restricted partitions modify the product—distinct parts use $\prod(1+x^k)$, bounded parts truncate the product
• Connects to number theory—Euler's identities, Ramanujan's congruences, and modular forms

Probability Generating Functions

• Defined as $G(s) = E[s^X] = \sum_{k} P(X=k) s^k$—encodes the distribution of discrete random variable $X$
• Convolution gives sum of independent variables—if $X$ and $Y$ are independent, $G_{X+Y}(s) = G_X(s) G_Y(s)$
• Derivatives at $s=1$ give factorial moments—$G'(1) = E[X]$, useful for computing mean and variance

Moment Generating Functions

• Defined as $M(t) = E[e^{tX}]$—exists for distributions with exponentially bounded tails
• Uniquely determines the distribution—if two MGFs match, the distributions are identical
• Derivatives at $t=0$ give ordinary moments—$M^{(n)}(0) = E[X^n]$, powerful for proving limit theorems

---

Quick Reference Table

---

Self-Check Questions

1. When should you use an EGF instead of an OGF? Give an example of a counting problem suited to each.

2. If $G(x) = \frac{1}{(1-x)(1-2x)}$, use partial fractions to find a closed form for $[x^n]G(x)$.

3. Compare convolution of sequences with multiplication of generating functions—why does one encode the other?

4. The Fibonacci recurrence is $F_n = F_{n-1} + F_{n-2}$. Set up the generating function equation and identify what determines the closed-form solution.

5. How does the generating function $\prod_{k=1}^{\infty}(1+x^k)$ differ from $\prod_{k=1}^{\infty}\frac{1}{1-x^k}$, and what partition restriction does each encode?