Generating Functions - Examples and Constructions

Generating functions excel at solving counting problems involving combinations with restrictions. These examples demonstrate systematic approaches to constructing and manipulating generating functions for complex enumeration scenarios.

ExampleInteger Partitions

A partition of a positive integer $n$ is a way of writing $n$ as a sum of positive integers, where order doesn't matter. For example, partitions of 4 are: $4, 3+1, 2+2, 2+1+1, 1+1+1+1$ .

The generating function for partitions is: $P(x) = \prod_{k=1}^{\infty} \frac{1}{1-x^k} = \frac{1}{(1-x)(1-x^2)(1-x^3)\cdots}$

The coefficient of $x^n$ in $P(x)$ is $p(n)$ , the number of partitions of $n$ .

Explanation: The factor $\frac{1}{1-x^k} = 1 + x^k + x^{2k} + x^{3k} + \cdots$ represents using 0, 1, 2, ... parts of size $k$ . The product over all $k$ gives all partitions.

ExampleDistributing Identical Objects

How many ways can we distribute $n$ identical balls into 3 distinct boxes, where the first box gets an even number, the second gets at most 4, and the third gets at least 2?

Generating function for each box:

Box 1 (even): $(1 + x^2 + x^4 + \cdots) = \frac{1}{1-x^2}$
Box 2 (at most 4): $(1 + x + x^2 + x^3 + x^4) = \frac{1-x^5}{1-x}$
Box 3 (at least 2): $(x^2 + x^3 + x^4 + \cdots) = \frac{x^2}{1-x}$

Combined generating function: $G(x) = \frac{1}{1-x^2} \cdot \frac{1-x^5}{1-x} \cdot \frac{x^2}{1-x} = \frac{x^2(1-x^5)}{(1-x)^2(1-x^2)}$

The coefficient of $x^n$ gives the answer for $n$ balls.

ExampleSolving Recurrences with Generating Functions

Solve $a_n = 3a_{n-1} - 2a_{n-2}$ with $a_0 = 1$ and $a_1 = 2$ using generating functions.

Let $G(x) = \sum_{n=0}^{\infty} a_n x^n$ . Multiply the recurrence by $x^n$ and sum: $\sum_{n=2}^{\infty} a_n x^n = 3\sum_{n=2}^{\infty} a_{n-1} x^n - 2\sum_{n=2}^{\infty} a_{n-2} x^n$

$G(x) - a_0 - a_1 x = 3x(G(x) - a_0) - 2x^2 G(x)$

$G(x) - 1 - 2x = 3xG(x) - 3x - 2x^2G(x)$

$G(x)(1 - 3x + 2x^2) = 1 - x$

$G(x) = \frac{1-x}{1-3x+2x^2} = \frac{1-x}{(1-x)(1-2x)} = \frac{1}{1-2x}$

Therefore: $a_n = 2^n$ .

ExampleDerangements via EGF

The exponential generating function for derangements is: $D(x) = \frac{e^{-x}}{1-x}$

This follows from the formula $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ : $\sum_{n=0}^{\infty} D_n \frac{x^n}{n!} = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} \frac{(-1)^k}{k!}\right) x^n$

Using series manipulation and the fact that $e^{-x} = \sum_{k=0}^{\infty} \frac{(-1)^k x^k}{k!}$ and $\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$ : $D(x) = e^{-x} \cdot \frac{1}{1-x}$

Remark

Generating functions are particularly powerful for partition problems. Besides ordinary partitions, we can count partitions with distinct parts (using $\prod_{k=1}^{\infty}(1+x^k)$ ), partitions into odd parts, partitions with bounded part size, and many other variants. Euler's partition theorem states that the number of partitions into odd parts equals the number of partitions into distinct parts, proven elegantly by showing their generating functions are equal: $\prod_{k=1}^{\infty}\frac{1}{1-x^{2k-1}} = \prod_{k=1}^{\infty}(1+x^k)$ . The pentagonal number theorem and Rogers-Ramanujan identities represent deep results in this area, connecting partition theory to number theory and modular forms.

These examples illustrate how generating functions transform counting problems into algebraic manipulations, often revealing surprising patterns and connections.