6.4 Solving counting problems using generating functions

Generating functions transform counting problems into algebra problems. Instead of reasoning directly about how many ways to arrange or select objects, you encode the counts as coefficients of a power series, manipulate the series using standard algebra, and then read off the answer. This technique is especially useful when direct counting gets messy or when you need to solve recurrence relations.

There are two main types: ordinary generating functions (OGFs) for problems involving unlabeled or distinct objects, and exponential generating functions (EGFs) for problems involving labeled structures. Choosing the right type depends on whether the objects in your problem are distinguishable and how they combine.

Generating functions for counting problems

Understanding generating functions

A generating function encodes a sequence $a_0, a_1, a_2, \ldots$ as a formal power series:

$A(x) = \sum_{n \geq 0} a_n x^n$

The coefficient of $x^n$ tells you the count for objects of size $n$. You don't need the series to converge; you're treating it as a formal algebraic object.

OGF vs. EGF: Use an OGF when you're counting unordered selections or compositions of unlabeled pieces. Use an EGF (where the series is $\sum a_n \frac{x^n}{n!}$) when objects carry labels and you care about how labels are distributed. For example, counting the number of ways to partition a set of labeled elements into groups calls for an EGF, while distributing identical coins into distinct bins calls for an OGF.

Basic building blocks and operations

A few fundamental generating functions appear over and over:

• $\frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots$ represents unrestricted selection with repetition (every non-negative integer is allowed).
• $1 + x$ represents choosing either zero or one copy of an item.
• $e^x = \sum_{n \geq 0} \frac{x^n}{n!}$ is the EGF for unrestricted labeled selection.

Combining these building blocks mirrors combinatorial operations:

• Multiplication of two OGFs corresponds to forming ordered pairs (or concatenating independent choices). If $A(x)$ counts ways to fill one slot and $B(x)$ counts ways to fill another, then $A(x) \cdot B(x)$ counts ways to fill both.
• Addition corresponds to taking the union of disjoint alternatives.
• Composition $A(B(x))$ arises when you substitute one structure inside another (e.g., partitions of partitions).

From these pieces you can build generating functions for many familiar sequences. For instance, the OGF for the Fibonacci numbers is $\frac{1}{1-x-x^2}$, and the OGF for the Catalan numbers is $\frac{1-\sqrt{1-4x}}{2x}$.

Adapting generating functions for specific problems

Real problems come with constraints, and you handle them by modifying the building blocks:

• Minimum or maximum size: If each part must have size at least 2, replace $\frac{1}{1-x}$ with $\frac{x^2}{1-x}$ (shifting the index).
• Alternating signs: Replacing $x$ with $-x$ gives $\frac{1}{1+x} = 1 - x + x^2 - x^3 + \cdots$, useful for inclusion-exclusion arguments.
• Periodic sequences: Combine roots of unity filters. For example, to pick out only even-indexed coefficients of $f(x)$, use $\frac{f(x) + f(-x)}{2}$.
• Weighted counts: If each object of size $n$ carries a weight $w_n$, just use $w_n$ as the coefficient instead of a pure count.

Extracting coefficients from generating functions

Once you have a generating function, the whole point is to read off $[x^n] f(x)$, the coefficient of $x^n$. Several techniques exist, ranging from elementary to advanced.

Direct expansion and algebraic techniques

Binomial Theorem. For expressions of the form $(1+x)^n$:

$[x^k](1+x)^n = \binom{n}{k}$

This generalizes to negative and fractional exponents. The generalized binomial series gives:

$[x^k](1+x)^{-n} = (-1)^k \binom{n+k-1}{k}$

which counts multiset selections (choosing $k$ items from $n$ types with repetition).

Partial fraction decomposition. When your generating function is a ratio of polynomials, decompose it into simpler fractions. For example, to extract coefficients from $\frac{1}{(1-2x)(1-3x)}$:

1. Write $\frac{1}{(1-2x)(1-3x)} = \frac{A}{1-2x} + \frac{B}{1-3x}$.
2. Solve for $A$ and $B$ (here $A = -1$, $B = 2$ after clearing denominators... but always check by plugging in convenient values of $x$). Actually: setting $x = 1/2$ gives $A \cdot \frac{1}{1-3/2}$, and setting $x = 1/3$ gives $B \cdot \frac{1}{1-2/3}$. You get $A = -2, B = 3$.
3. Since $[x^n]\frac{1}{1-cx} = c^n$, the coefficient of $x^n$ is $-2 \cdot 2^n + 3 \cdot 3^n = 3^{n+1} - 2^{n+1}$.

Undetermined coefficients. If you suspect the coefficient sequence has a particular form (e.g., $a_n = \alpha \cdot r_1^n + \beta \cdot r_2^n$), plug in known values of $a_n$ to solve for the unknowns.

Advanced extraction techniques

• Differentiation and integration shift indices. Multiplying $f(x)$ by $x$ and differentiating produces $\sum n a_n x^n$, which is handy when you need weighted sums. Integrating does the reverse.
• Taylor series comparison. Expand known functions and match coefficients. For instance, $[x^n] e^{x^2} = \frac{1}{(n/2)!}$ when $n$ is even, and 0 when $n$ is odd.
• Cauchy's Integral Formula. For asymptotic estimates of coefficients:

$[x^n] f(x) = \frac{1}{2\pi i} \oint \frac{f(z)}{z^{n+1}} dz$

This is the starting point for singularity analysis, where you estimate the integral by studying the dominant singularity of $f(z)$. For example, the $n$th Catalan number (from $C(x) = \frac{1-\sqrt{1-4x}}{2x}$) grows asymptotically as $\frac{4^n}{n^{3/2}\sqrt{\pi}}$.

Solving recurrence relations with generating functions

This is one of the most practical applications. The strategy is always the same:

1. Multiply both sides of the recurrence by $x^n$ and sum over all valid $n$.
2. Recognize the sums as the generating function $A(x)$ (or shifted versions of it).
3. Solve the resulting algebraic equation for $A(x)$.
4. Extract coefficients to get a closed form for $a_n$.

Translating recurrence relations to functional equations

Example: Fibonacci numbers. The recurrence is $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0, F_1 = 1$.

1. Define $F(x) = \sum_{n \geq 0} F_n x^n$.

2. Multiply the recurrence by $x^n$ and sum for $n \geq 2$: $\sum_{n \geq 2} F_n x^n = x \sum_{n \geq 2} F_{n-1} x^{n-1} + x^2 \sum_{n \geq 2} F_{n-2} x^{n-2}$

3. Rewrite in terms of $F(x)$: $F(x) - F_0 - F_1 x = x(F(x) - F_0) + x^2 F(x)$

4. Substitute initial conditions ($F_0 = 0, F_1 = 1$): $F(x) - x = xF(x) + x^2 F(x)$

5. Solve: $F(x) = \frac{x}{1 - x - x^2}$.

Example: Non-homogeneous recurrence. For $a_n = 2a_{n-1} + 1$ with $a_0 = 0$:

1. The same multiply-and-sum procedure gives $A(x) = 2xA(x) + \frac{x}{1-x}$.
2. Solving: $A(x) = \frac{x}{(1-x)(1-2x)}$.
3. Partial fractions and coefficient extraction yield $a_n = 2^n - 1$.

Solving and analyzing functional equations

After isolating $A(x)$, you typically get a rational function. Apply partial fraction decomposition to break it into terms of the form $\frac{c}{1 - rx}$, each contributing $c \cdot r^n$ to the coefficient of $x^n$.

For the Fibonacci example, the denominator $1 - x - x^2$ factors using the roots of the characteristic equation $r^2 - r - 1 = 0$, giving $r = \frac{1 \pm \sqrt{5}}{2}$. Partial fractions then produce the famous Binet formula:

$F_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$

Techniques for non-homogeneous recurrences

When the recurrence has a non-homogeneous term (like $+n$ or $+3^n$), the generating function approach handles it naturally: the non-homogeneous term just adds an extra known function to the equation. You solve for $A(x)$ algebraically, and the partial fraction decomposition automatically separates the homogeneous and particular parts of the solution.

This is a real advantage over the classical method of "guess the particular solution form," because the generating function framework doesn't require any guessing.

Advanced combinatorial problems with generating functions

Multivariate generating functions

Some problems track two or more parameters at once. A bivariate generating function $f(x,y) = \sum_{m,n} a_{m,n} x^m y^n$ encodes a doubly-indexed sequence. For instance, lattice paths on a rectangular grid that take unit steps right or up can be counted with a bivariate GF where $x$ tracks horizontal steps and $y$ tracks vertical steps.

Multivariate GFs also appear in partition theory. The generating function for partitions into distinct odd parts is:

$\prod_{k \geq 1}(1 + x^{2k-1}) = (1+x)(1+x^3)(1+x^5)\cdots$

Here the coefficient of $x^n$ counts the number of such partitions of $n$.

Implicit and functional equation techniques

Not every generating function can be written in closed form. Sometimes the GF satisfies an implicit equation, and you need specialized tools:

• Lagrange Inversion Theorem. If $T(x) = x \cdot \phi(T(x))$ for some known function $\phi$, then: $[x^n] T(x) = \frac{1}{n} [t^{n-1}] \phi(t)^n$ This is the standard way to count labeled rooted trees (where $T(x) = x e^{T(x)}$ gives Cayley's formula: $n^{n-1}$ labeled trees on $n$ vertices).

• The kernel method. For functional equations involving, say, $F(x, y)$ where one variable can be set to a specific algebraic function of the other to "kill" one term, simplifying the equation. This comes up frequently in lattice path problems with boundary constraints.

• The quadratic method. When a GF satisfies a quadratic equation (often involving a square root), you can solve directly and choose the branch consistent with initial conditions. The Catalan number GF is the classic example.

Exponential generating functions and labeled structures

For labeled structures, the EGF is the natural choice. If there are $a_n$ labeled structures of size $n$, the EGF is:

$\hat{A}(x) = \sum_{n \geq 0} a_n \frac{x^n}{n!}$

The key property: multiplying two EGFs corresponds to forming labeled products, where you split the label set $\{1, 2, \ldots, n\}$ into two parts in all possible ways and build one structure on each part.

The exponential formula is especially powerful: if $C(x)$ is the EGF for connected labeled structures, then $e^{C(x)}$ is the EGF for sets of such structures (allowing any number of connected components). For example:

• The EGF for labeled rooted trees is $T(x)$, so the EGF for labeled forests is $e^{T(x)}$.
• The EGF for cycles (cyclic permutations) is $\log\frac{1}{1-x}$, so the EGF for sets of cycles (all permutations) is $e^{\log\frac{1}{1-x}} = \frac{1}{1-x}$, confirming there are $n!$ permutations of $n$ elements.

The symbolic method provides a dictionary: the SET construction translates to $\exp(\cdot)$, the SEQUENCE construction to $\frac{1}{1-(\cdot)}$, and the CYCLE construction to $\log\frac{1}{1-(\cdot)}$ in the EGF world.

Analyzing algorithms and data structures

Generating functions connect combinatorics to algorithm analysis. The average number of comparisons in quicksort, for instance, can be derived by setting up a recurrence for the expected cost, translating it into a generating function equation, and solving.

Bivariate GFs are particularly useful here: one variable tracks the size of the input, and the other tracks the cost or some structural parameter (like tree height). Singularity analysis of the resulting GF then gives asymptotic estimates for typical behavior on large inputs.