Generating Functions in Combinatorics

Generating functions transform complex combinatorial enumeration problems into manageable algebraic operations. By encoding an infinite sequence of numbers into the coefficients of a formal power series, you gain access to the powerful machinery of algebra and calculus to find closed forms, discover patterns, and solve recurrences. This technique is a cornerstone of advanced combinatorial analysis, providing a unified framework for counting objects from partitions to permutations.

Ordinary Generating Functions: The Foundation

An ordinary generating function (OGF) is a formal power series that packages a sequence $a_0,a_1,a_2,...$ into a single algebraic object. For a sequence $(a_n)$, its OGF is defined as $A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$. The variable $x$ is a formal placeholder; we are not concerned with convergence but with the algebraic rules for manipulating the series. This shift in perspective—from a sequence to a series—is powerful because combinatorial operations often translate into simple algebraic operations on their OGFs.

For example, let $p_n$ be the number of integer partitions of $n$. The generating function for this sequence has an elegant infinite product form, derived from combinatorial reasoning about choosing parts: $$P(x)=\sum _{n=0}^{\infty }{p}_n{x}^n=\prod _{k=1}^{\infty }\frac{1}{1-x^k}.$$ Each factor $(1-x^k{)}^{-1}=1+x^k+x^{2k}+x^{3k}+...$ represents the choice of how many copies of the part size $k$ to include (zero, one, two, etc.). Multiplying these choices for all $k$ builds every possible partition exactly once, and the coefficient of $x^n$ collects all combinations that sum to $n$.

The true utility of OGFs emerges when you model combinatorial constructions. If two disjoint sets of objects have OGFs $A(x)$ and $B(x)$, then the OGF for their union is $A(x)+B(x)$. If you form ordered pairs, where one object from a set with OGF $A(x)$ is combined with one from a set with OGF $B(x)$, the OGF for the pairs is $A(x)\cdot B(x)$. This correspondence allows you to build generating functions for complex objects from simpler ones.

Solving Recurrence Relations

A primary application of generating functions is solving recurrence relations, which are ubiquitous in combinatorial definitions. The process is methodical: translate the recurrence into an equation for the generating function, solve that algebraic equation, and then extract the coefficients to find a closed-form expression for the sequence.

Consider the classic recurrence for the Fibonacci numbers: $F_0=0,F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for $n\ge 2$. Let $F(x)={\sum }_{n=0}^{\infty }{F}_n{x}^n$ be its OGF.

1. Translate: Multiply the recurrence by $x^n$ and sum over all $n\ge 2$:

$$\sum _{n=2}^{\infty }{F}_n{x}^n=\sum _{n=2}^{\infty }{F}_{n-1}{x}^n+\sum _{n=2}^{\infty }{F}_{n-2}{x}^n.$$

1. Express in terms of F(x): The left side is $F(x)-F_0-F_{1}x=F(x)-x$. The first sum on the right is $x{\sum }_{n=2}^{\infty }{F}_{n-1}{x}^{n-1}=x(F(x)-F_0)=xF(x)$. The second is $x^2{\sum }_{n=2}^{\infty }{F}_{n-2}{x}^{n-2}=x^{2}F(x)$.
2. Solve the Algebraic Equation: This yields $F(x)-x=xF(x)+x^{2}F(x)$. Solving for $F(x)$ gives:

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

1. Extract Coefficients: The denominator factors as $1-x-x^2=(1-\varphi x)(1-\hat{\varphi }x)$, where $\varphi$ is the golden ratio. Using partial fraction decomposition, we rewrite $F(x)$ as a sum of simpler geometric series:

$$F(x)=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\varphi x}-\frac{1}{1-\hat{\varphi }x}\right).$$ Expanding each term as a geometric series, $\frac{1}{1-\varphi x}={\sum }_{n=0}^{\infty }{\varphi }^n{x}^n$, allows us to read off the coefficient $F_n$: $$F_n=\frac{1}{\sqrt{5}}({\varphi }^n-{\hat{\varphi }}^n),$$ which is Binet's famous formula.

This workflow—recurrence to generating function equation to algebraic solution to coefficient extraction via partial fractions or series expansion—is a general and powerful technique.

Exponential Generating Functions for Labeled Structures

When counting labeled structures—like permutations, set partitions, or mappings where the $n$ underlying elements are distinct—exponential generating functions (EGFs) are the natural tool. For a sequence $(a_n)$, its EGF is $\hat{A}(x)={\sum }_{n=0}^{\infty }{a}_n\frac{x^n}{n!}$. The division by $n!$ elegantly accounts for the labeling of the $n$ distinct elements.

A quintessential example is the EGF for the number of permutations, $p_n=n!$. Its EGF is: $$\hat{P}(x)=\sum _{n=0}^{\infty }n!\frac{x^n}{n!}=\sum _{n=0}^{\infty }{x}^n=\frac{1}{1-x}.$$ The simplicity of this result is not a coincidence; it reflects the fact that constructing a permutation on a labeled set is akin to forming an ordered sequence of all elements.

The combinatorial construction rules for EGFs differ from OGFs to accommodate labels. If you take two disjoint labeled structures with EGFs $\hat{A}(x)$ and $\hat{B}(x)$, their union has EGF $\hat{A}(x)+\hat{B}(x)$. The powerful operation is the labelled product. If you have two types of labeled structures, and you combine them by partitioning the $n$ distinct labels into two groups, assigning one group to the first structure and the other to the second, and then assembling the results, the EGF for this composite structure is $\hat{A}(x)\cdot \hat{B}(x)$. This product rule is the key to solving problems involving arrangements of distinct objects.

Applications to Partition, Composition, and Lattice Paths

Generating functions provide closed-form solutions to many classic enumeration problems.

• Integer Compositions: A composition of $n$ is an ordered sequence of positive integers summing to $n$. Let $c_n$ be the number of compositions of $n$. You can think of building a composition as choosing a sequence of parts, each of size at least 1. The generating function for a single part is $x+x^2+x^3+...=\frac{x}{1-x}$. Since a composition is an ordered sequence of such parts, the OGF for all compositions is given by the geometric series of this building block:

$$C(x)=1+\left(\frac{x}{1-x}\right)+{\left(\frac{x}{1-x}\right)}^2+...=\frac{1}{1-\frac{x}{1-x}}=\frac{1-x}{1-2x}.$$ Expanding this, you find $C(x)=1+x+2x^2+4x^3+8x^4+...$, so $c_n=2^{n-1}$ for $n\ge 1$.

• Lattice Path Counting: Consider counting the number of monotonic paths from $(0,0)$ to $(m,n)$ using only steps East $(1,0)$ and North $(0,1)$. Each path is a sequence of $m+n$ steps containing exactly $m$ East steps and $n$ North steps. This is counted by the binomial coefficient $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$. The OGF for the number of paths to points on a diagonal can be insightful. For example, the generating function for Catalan numbers (which count certain lattice paths) satisfies a quadratic equation derived by decomposing a path at its first return to the diagonal.

• Partition Problems: Beyond the unrestricted partition function $P(x)$, you can use generating functions to count restricted partitions. For instance, the OGF for partitions into distinct parts (no repetitions) is ${\prod }_{k=1}^{\infty }(1+x^k)$, as for each part $k$, you have a choice: include it (once) or not. The OGF for partitions into odd parts is ${\prod }_{k=1}^{\infty }\frac{1}{1-x^{2k-1}}$. The celebrated theorem that these two counts are equal for every $n$ becomes the startling, non-obvious algebraic identity:

$$\prod _{k=1}^{\infty }(1+x^k)=\prod _{k=1}^{\infty }\frac{1}{1-x^{2k-1}}.$$ Proving this identity combinatorially, by finding a bijection, is a classic challenge, but the generating function proof is straightforward manipulation of series.

Common Pitfalls

1. Confusing Formal and Analytic Viewpoints: The most common error is to treat the generating function variable $x$ as a real number and worry about convergence from the start. In combinatorial enumeration, you work with formal power series. You manipulate them algebraically using the rules of addition, multiplication, and composition where defined. Questions of convergence are relevant only later, when you need to use analytic methods (like contour integration) to extract coefficients. Begin by thinking formally.

1. Incorrectly Translating Recurrences: When summing a recurrence to derive the generating function equation, it's easy to make off-by-one errors in the indices. Always write out the first few terms of the sum explicitly to ensure your adjustment (e.g., $F(x)-F_0-F_{1}x$) is correct. A systematic approach is to multiply the recurrence by $x^n$, sum over all $n$ for which it holds, and then carefully adjust sums to express everything in terms of the full generating function $F(x)$.

1. Misapplying Exponential vs. Ordinary: Using an OGF for a labeled problem or an EGF for an unlabeled one will lead to incorrect factors of $n!$. Ask: Are the objects I'm counting built from distinct, labeled elements (like permutations of a set, partitions of a labeled set)? If yes, use an EGF. Are they built from identical or unlabeled units (like compositions of an integer, partitions of an unlabeled set)? If yes, use an OGF. Mixing them up scrambles the combinatorial accounting.

1. Overlooking the "1 +" in Product Forms: When constructing generating functions via products, remember the "empty" object. For example, in the product for partitions ${\prod }_{k=1}^{\infty }(1+x^k+x^{2k}+...)$, the term "1" in each factor represents choosing zero copies of part $k$. Omitting it would incorrectly force every part to be used at least once. Always include the choice of non-selection.

Summary

• Ordinary generating functions (OGFs) encode sequences and are ideal for counting unlabeled structures like integer partitions and compositions. The algebraic operations of addition and multiplication correspond directly to combinatorial union and ordered pairing.
• The standard method for solving recurrences involves translating the recurrence into an equation for the generating function, solving that equation algebraically, and then extracting coefficients using tools like partial fraction decomposition and known series expansions.
• Exponential generating functions (EGFs) are the correct tool for counting labeled structures, as the division by $n!$ accounts for permutations of distinct labels. Their product rule corresponds to the labelled product of combinatorial structures.
• Generating functions provide a unifying framework for proving combinatorial identities and deriving closed forms for problems involving partitions, compositions, and lattice paths, often revealing surprising connections through simple algebraic manipulations.
• To avoid errors, maintain a formal power series perspective initially, carefully handle indices when translating recurrences, and choose between OGFs and EGFs based on whether your problem involves labeled or unlabeled objects.