14.2 Exponential Generating Functions

Exponential Generating Functions

Exponential generating functions (EGFs) encode sequences using factorial denominators, which makes them naturally suited for counting labeled structures like permutations, arrangements, and set partitions. Where ordinary generating functions (OGFs) pair coefficients with plain powers of $x$, EGFs divide each coefficient by $n!$, and that single change unlocks a different set of algebraic tools.

This section covers the definition and key properties of EGFs, the exponential formula for set partitions, Bell and Stirling numbers, and connections to moment and probability generating functions.

Exponential Generating Functions

Understanding Exponential Generating Functions

For a sequence $a_0, a_1, a_2, \ldots$, the exponential generating function is defined as:

$G(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$

Compare this with the ordinary generating function $\sum a_n x^n$. The only structural difference is the $\frac{1}{n!}$ factor, but it changes what algebraic operations mean combinatorially.

Why the factorial denominator matters. When you multiply two OGFs, the coefficients combine via convolution, which corresponds to choosing how many objects come from each structure (selections). When you multiply two EGFs, the coefficients combine via exponential convolution, which corresponds to choosing how to label objects across two structures. Concretely, if $A(x)$ and $B(x)$ are EGFs for sequences $a_n$ and $b_n$, then the product $A(x) \cdot B(x)$ is the EGF for:

$c_n = \sum_{k=0}^{n} \binom{n}{k} a_k \, b_{n-k}$

That binomial coefficient is exactly what you need when you're splitting a labeled set of size $n$ into a part of size $k$ and a part of size $n-k$.

Common EGFs to know:

• $e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$ is the EGF for the constant sequence $a_n = 1$ (there's exactly 1 way to arrange $n$ labeled items into a single "all-in" structure).
• $e^{x} - 1$ is the EGF for $a_0 = 0, \, a_n = 1$ for $n \geq 1$ (non-empty sets).
• $\frac{1}{1-x}$ is the EGF for $a_n = n!$ (the number of permutations of $n$ elements).

EGFs also tend to converge more often than OGFs because the $n!$ in the denominator tames rapid growth in the sequence.

Factorial Powers and Their Role

The falling factorial (sometimes called the factorial power) is:

$x^{\underline{n}} = x(x-1)(x-2)\cdots(x-n+1)$

This is the product of $n$ consecutive decreasing integers starting from $x$. It shows up constantly in combinatorics because it directly counts the number of ways to choose and arrange $n$ items from $x$ items (i.e., permutations): $P(x, n) = x^{\underline{n}}$.

A useful identity ties falling factorials to binomial coefficients:

$x^{\underline{n}} = n! \binom{x}{n}$

This means choosing $n$ items from $x$ (the binomial coefficient) is just the falling factorial divided by $n!$, which removes the ordering.

Falling factorials play a role in EGFs because many sequences that arise from labeled counting problems can be expressed neatly using them. They also appear in finite difference calculus, where they serve the same role that ordinary powers $x^n$ serve in standard calculus.

Exponential Formula and Applications

The exponential formula is one of the most powerful results connecting EGFs to set partitions. Here's the setup:

Suppose you have a notion of a "connected" or "block" structure on a non-empty labeled set, and $B(x)$ is the EGF counting the number of such structures by size. Then the EGF for the number of ways to partition a labeled set into any number of these blocks is:

$A(x) = e^{B(x)}$

Why does this work? Expanding the exponential gives:

$e^{B(x)} = \sum_{k=0}^{\infty} \frac{B(x)^k}{k!}$

The term $\frac{B(x)^k}{k!}$ counts ways to split a labeled set into exactly $k$ blocks. The $k!$ in the denominator accounts for the fact that the blocks themselves are unordered (a partition doesn't care which block you list first). Summing over all $k$ gives the total count across all possible numbers of blocks.

Example: If each block is simply a non-empty set (one structure per size), then $B(x) = e^x - 1$, and the number of set partitions is counted by $e^{e^x - 1}$. That's exactly the EGF for Bell numbers, as you'll see below.

Combinatorial Numbers

Bell Numbers and Set Partitions

The Bell number $B_n$ counts the total number of ways to partition a set of $n$ labeled elements into non-empty, non-overlapping subsets. For example, the set $\{1, 2, 3\}$ can be partitioned in 5 ways:

• $\{\{1,2,3\}\}$
• $\{\{1,2\},\{3\}\}$
• $\{\{1,3\},\{2\}\}$
• $\{\{2,3\},\{1\}\}$
• $\{\{1\},\{2\},\{3\}\}$

So $B_3 = 5$.

The first several Bell numbers (starting at $n = 0$): 1, 1, 2, 5, 15, 52, 203, 877.

EGF for Bell numbers:

$\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x - 1}$

This follows directly from the exponential formula: each block is a non-empty set, and $e^x - 1$ is the EGF where every non-empty set has exactly one structure.

Recursive formula (Bell's recurrence):

$B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$

The idea: to build a partition of $\{1, 2, \ldots, n+1\}$, decide which $k$ of the elements $\{1, \ldots, n\}$ share a block with element $n+1$, then partition the remaining $n - k$ elements freely. That gives $\binom{n}{k} B_{n-k}$, and re-indexing yields the formula above.

Bell numbers appear in clustering algorithms, information theory, and the analysis of equivalence relations.

Stirling Numbers and Their Types

Stirling numbers refine the counting that Bell numbers do in aggregate.

Stirling numbers of the second kind, $S(n, k)$, count the number of ways to partition a set of $n$ labeled elements into exactly $k$ non-empty subsets. Since Bell numbers count partitions into any number of subsets:

$B_n = \sum_{k=0}^{n} S(n, k)$

The EGF (with $k$ fixed, summing over $n$) is:

$\sum_{n=k}^{\infty} S(n,k) \frac{x^n}{n!} = \frac{(e^x - 1)^k}{k!}$

Again, this is the exponential formula at work: $(e^x - 1)^k$ counts ordered sequences of $k$ non-empty blocks, and dividing by $k!$ makes the blocks unordered.

Stirling numbers of the first kind, $s(n, k)$ (or sometimes written with square brackets $\left[\begin{smallmatrix} n \\ k \end{smallmatrix}\right]$), count the number of permutations of $n$ elements that consist of exactly $k$ disjoint cycles. These are sometimes called signless Stirling numbers of the first kind (the signed version introduces a factor of $(-1)^{n-k}$).

Both types of Stirling numbers satisfy useful recurrences and appear in problems involving recurrence relations, polynomial basis conversion (between ordinary powers and falling factorials), and algorithm analysis.

Probability and Statistics Applications

Moment Generating Functions

The moment generating function (MGF) of a random variable $X$ is:

$M_X(t) = E[e^{tX}]$

If you expand $e^{tX}$ as a power series, you get:

$M_X(t) = \sum_{n=0}^{\infty} \frac{E[X^n]}{n!} \, t^n$

This is exactly an EGF for the sequence of moments $E[X^n]$. That's the direct connection to this unit: the MGF is an exponential generating function whose coefficients are the moments of the distribution.

To extract the $n$-th moment, differentiate $n$ times and evaluate at $t = 0$:

$E[X^n] = \frac{d^n}{dt^n} M_X(t) \Big|_{t=0}$

Key properties of MGFs:

• If $X$ and $Y$ are independent, then $M_{X+Y}(t) = M_X(t) \cdot M_Y(t)$. This makes working with sums of independent random variables straightforward.
• The MGF (when it exists in a neighborhood of 0) uniquely determines the distribution. Two distributions with the same MGF are the same distribution.
• The variance can be found as $\text{Var}(X) = M_X''(0) - [M_X'(0)]^2$.

Probability Generating Functions and Their Uses

For a discrete random variable $X$ taking non-negative integer values, the probability generating function (PGF) is:

$G_X(z) = E[z^X] = \sum_{k=0}^{\infty} P(X = k) \, z^k$

Notice this is actually an ordinary generating function for the probability sequence $P(X = k)$. To recover individual probabilities:

$P(X = k) = \frac{1}{k!} \frac{d^k}{dz^k} G_X(z) \Big|_{z=0}$

Useful properties:

• $G_X(1) = 1$ (probabilities sum to 1).
• $G_X'(1) = E[X]$.
• $\text{Var}(X) = G_X''(1) + G_X'(1) - [G_X'(1)]^2$.
• For independent $X$ and $Y$: $G_{X+Y}(z) = G_X(z) \cdot G_Y(z)$.

PGFs are widely used in queuing theory, branching processes, and other stochastic models where you need to track distributions of counts. Their connection to EGFs comes through the relationship between PGFs and MGFs: setting $z = e^t$ in the PGF gives the MGF, which bridges the ordinary and exponential generating function perspectives.