Exponential generating functions and set partitions

Ordinary generating functions suit unlabeled objects: coins, compositions, Dyck paths. Many structures, though, are built on labeled points: permutations of \(\{1, \ldots, n\}\), partitions of a set, graphs on numbered vertices, trees whose nodes carry names. When two labeled structures are combined, their labels must be shuffled together, and that shuffling introduces binomial coefficients. Exponential generating functions absorb those coefficients automatically, and lead to one of the most useful results in enumeration, the exponential formula.

Definition and the labeled product

The exponential generating function of a sequence \(a_n\) is \[\hat{A}(x) = \sum_{n \ge 0}a_n\frac{x^n}{n!}.\] The simplest examples: if \(a_n = 1\) for all \(n\) (there is exactly one set of each size), \(\hat{A}(x) = e^x\). If \(a_n = n!\) (permutations, or linear orders), \(\hat{A}(x) = \sum x^n = \frac{1}{1 - x}\). If \(a_n = (n - 1)!\) for \(n \ge 1\) (cyclic orders), \(\hat{A}(x) = \sum_{n \ge 1}\frac{x^n}{n} = \ln\frac{1}{1 - x}\).

Suppose a structure on a label set \(N\) is formed by splitting \(N\) into two disjoint parts \(K\) and \(N \setminus K\), putting an \(\mathcal{A}\)-structure on \(K\) and a \(\mathcal{B}\)-structure on the rest. The number of such structures on \(n\) labels is \[c_n = \sum_{k=0}^{n}\binom{n}{k}a_kb_{n-k},\] since we choose which \(k\) labels go to the first part. Now \[\hat{A}(x)\hat{B}(x) = \sum_n\Big(\sum_k\frac{a_k}{k!}\frac{b_{n-k}}{(n-k)!}\Big)x^n = \sum_n\Big(\sum_k\binom{n}{k}a_kb_{n-k}\Big)\frac{x^n}{n!},\] so \(\hat{C} = \hat{A}\hat{B}\). The labeled product corresponds to multiplying exponential generating functions, just as ordered pairs corresponded to multiplying ordinary ones.

Example: words. A word of length \(n\) over the alphabet \(\{a, b\}\) is a split of the positions into those holding \(a\) and those holding \(b\), with one set structure on each. So its exponential generating function is \(e^x \cdot e^x = e^{2x} = \sum 2^n\frac{x^n}{n!}\), giving \(2^n\) words, as it should. Words over \(k\) letters in which every letter is used split the positions into \(k\) nonempty sets, so they have function \((e^x - 1)^k\) and count \(k!\,S(n, k)\), the surjections of lesson 3.

Sets of structures and the exponential formula

Taking \(k\) nonempty blocks, but now unordered, divides by \(k!\): \[\sum_n S(n, k)\frac{x^n}{n!} = \frac{(e^x - 1)^k}{k!}.\] Summing over all \(k\) gives the exponential generating function of the Bell numbers, \[\sum_n B_n\frac{x^n}{n!} = \sum_k\frac{(e^x - 1)^k}{k!} = e^{e^x - 1}.\] This was found by Jacques Touchard and others; it encodes every set partition at once.

The same reasoning applies to any kind of connected building block. Suppose every structure of some kind decomposes uniquely into a set of connected components, each of which is a connected structure of the same kind on its own labels. Let \(c_n\) count connected structures and \(a_n\) all structures.

Theorem (the exponential formula). Under this hypothesis, \[\hat{A}(x) = \exp\big(\hat{C}(x)\big).\]

Proof. A structure with exactly \(k\) components is a set of \(k\) connected structures on the blocks of a partition of the labels. If the blocks were ordered, the labeled product rule would give exponential generating function \(\hat{C}(x)^k\). Each unordered collection of \(k\) distinct components arises from exactly \(k!\) orderings, and components are on disjoint label sets so they are always distinct; hence structures with \(k\) components have function \(\hat{C}(x)^k/k!\). Summing over \(k \ge 0\) gives \(\sum_k\hat{C}^k/k! = e^{\hat{C}}\).

Permutations. A permutation is a set of cycles, and cycles on \(m\) labels number \((m - 1)!\), with function \(\ln\frac{1}{1 - x}\). The formula gives \(\exp(\ln\frac{1}{1 - x}) = \frac{1}{1 - x}\), correctly counting \(n!\) permutations. Marking each cycle by a variable \(u\) gives \[\sum_{n,k}c(n, k)u^k\frac{x^n}{n!} = \exp\Big(u\ln\frac{1}{1 - x}\Big) = (1 - x)^{-u},\] and the coefficient of \(x^n/n!\) is \(u(u + 1)\cdots(u + n - 1)\), the rising factorial of lesson 2.

Restricted cycle lengths. Allowing only cycles whose lengths lie in a set \(L\) gives \(\exp\big(\sum_{m \in L}x^m/m\big)\). Derangements forbid cycles of length 1: \[\sum_n D_n\frac{x^n}{n!} = \exp\Big(\ln\frac{1}{1 - x} - x\Big) = \frac{e^{-x}}{1 - x},\] and multiplying out recovers \(D_n = n!\sum_k(-1)^k/k!\). Involutions, permutations with \(\sigma^2 = \mathrm{id}\), have only cycles of length 1 and 2, so their function is \(e^{x + x^2/2}\). Their counts \(1, 1, 2, 4, 10, 26, 76, 232\) satisfy \(t_n = t_{n-1} + (n - 1)t_{n-2}\), by asking whether \(n\) is fixed or paired with one of the others.

Connected graphs. Every labeled graph is a set of connected labeled graphs. There are \(2^{\binom{n}{2}}\) labeled graphs on \(n\) vertices, so the exponential formula runs backwards: \[\sum_n c_n\frac{x^n}{n!} = \ln\Big(\sum_n 2^{\binom n2}\frac{x^n}{n!}\Big).\] This series diverges for every \(x \ne 0\), yet as a formal series it is perfectly meaningful, and it gives the numbers of connected labeled graphs: 1, 1, 4, 38, 728, 26704. Almost all graphs are connected: the fraction tends to 1 rapidly.

Ordered partitions and Dobinski's formula

An ordered set partition, also called a preferential arrangement, is a sequence of nonempty blocks: the outcomes of a race in which ties are allowed. Sequences of nonempty sets have exponential function \(\sum_k(e^x - 1)^k = \frac{1}{2 - e^x}\). The counts \(1, 1, 3, 13, 75, 541\) are the Fubini numbers, equal to \(\sum_k k!\,S(n, k)\). Three runners can finish in 13 ways: 6 with no ties, 6 with one tie of two, and 1 three-way tie.

Dobinski's formula of 1877 expresses the Bell numbers as an infinite series: \[B_n = \frac{1}{e}\sum_{k \ge 0}\frac{k^n}{k!}.\] Proof: \(e^{e^x - 1} = e^{-1}e^{e^x} = e^{-1}\sum_k\frac{e^{kx}}{k!}\), and the coefficient of \(x^n/n!\) in \(e^{kx}\) is \(k^n\). In probability language, \(B_n\) is the \(n\)th moment of a Poisson random variable with mean 1.

Ordinary or exponential?

The choice between the two kinds of generating function is decided by whether the building blocks carry labels that must be shuffled together. Compare two questions about strings of length \(n\) over the alphabet \(\{a, b, c\}\). How many such strings have their letters in alphabetical order? A sorted string is determined by how many of each letter it uses, an unlabeled choice, so ordinary generating functions apply: \(\frac{1}{(1 - x)^3}\), giving \(\binom{n+2}{2}\). How many strings use an even number of \(a\)s? Now the positions are labels and each letter claims a set of positions, so exponential generating functions apply: \(\cosh x \cdot e^x \cdot e^x = \frac12(e^{3x} + e^{x})\), giving \(\frac12(3^n + 1)\) strings. Check with \(n = 2\): the strings with zero or two \(a\)s number \(4 + 1 = 5 = \frac12(9 + 1)\).

A useful rule of thumb: if swapping two objects of the same size gives a different arrangement that should be counted separately, the objects are labeled and the exponential form is natural; if the objects are interchangeable, use the ordinary form. Some problems can be treated either way after a change of variables. The Laplace–Borel transform, pairing \(\sum a_n x^n\) with \(\sum a_n x^n/n!\), converts between them formally, but the combinatorial operations, product and composition, only match the counting in the right setting.

The Bell triangle

The Bell numbers can also be generated by a simple triangle, found by A. C. Aitken in 1933 and also attributed to Charles Peirce. Start a row with 1. Each new row begins with the last entry of the previous row, and each further entry is the sum of the entry to its left and the entry above that one. The rows are 1; 1, 2; 2, 3, 5; 5, 7, 10, 15; 15, 20, 27, 37, 52; and the first entries 1, 1, 2, 5, 15, 52 are the Bell numbers. The entries count set partitions with a restriction on the block containing the largest element, and the triangle gives a quick way to compute \(B_n\) by hand without large binomial coefficients.

Trees and Cayley's formula

A rooted labeled tree is a root vertex together with a set of rooted labeled trees, the subtrees hanging from its children. If \(T(x)\) is the exponential generating function of rooted labeled trees, this decomposition reads \[T(x) = x\,e^{T(x)},\] the factor \(x\) accounting for the root's label. This equation determines \(T\) coefficient by coefficient. Lagrange's inversion theorem says that if \(T = x\phi(T)\) with \(\phi(0) \ne 0\), then \([x^n]T = \frac1n[t^{n-1}]\phi(t)^n\). With \(\phi = e^t\), \([t^{n-1}]e^{nt} = \frac{n^{n-1}}{(n-1)!}\), so \[[x^n]T(x) = \frac{n^{n-1}}{n!}, \qquad\text{that is, } n^{n-1}\text{ rooted trees}.\] Each unrooted tree on \(n\) vertices can be rooted in \(n\) ways, so there are \(n^{n-2}\) labeled trees, Cayley's formula of 1889. MATH-260 proved it with Prüfer codes; here it emerges from a functional equation. Forests of rooted trees, being sets of rooted trees, have function \(e^{T(x)}\) and count \((n + 1)^{n-1}\).

from fractions import Fraction
from math import factorial, comb, e

N = 10

def mul(a, b):
    return [sum(a[k] * b[n - k] for k in range(n + 1)) for n in range(N + 1)]

def exp_series(a):
    """exp of a series with a[0] = 0, using n b_n = sum k a_k b_(n-k)."""
    b = [Fraction(0)] * (N + 1); b[0] = Fraction(1)
    for n in range(1, N + 1):
        b[n] = sum(k * a[k] * b[n - k] for k in range(1, n + 1)) / n
    return b

def log_series(b):
    """log of a series with b[0] = 1."""
    a = [Fraction(0)] * (N + 1)
    for n in range(1, N + 1):
        a[n] = b[n] - sum(k * a[k] * b[n - k] for k in range(1, n)) / n
    return a

def counts(egf):
    return [int(egf[n] * factorial(n)) for n in range(N + 1)]

ex_minus_1 = [Fraction(0)] + [Fraction(1, factorial(n)) for n in range(1, N + 1)]
print("Bell, exp(e^x - 1):     ", counts(exp_series(ex_minus_1)))

minus_x = [Fraction(0), Fraction(-1)] + [Fraction(0)] * (N - 1)
geo = [Fraction(1)] * (N + 1)
print("derangements, e^-x/(1-x):", counts(mul(exp_series(minus_x), geo)))

invol = [Fraction(0), Fraction(1), Fraction(1, 2)] + [Fraction(0)] * (N - 2)
print("involutions, e^(x+x^2/2):", counts(exp_series(invol)))

cyc = [Fraction(0)] + [Fraction(1, n) for n in range(1, N + 1)]
print("permutations, exp(log 1/(1-x)):", counts(exp_series(cyc)))

ordered = [Fraction(0)] * (N + 1); power = [Fraction(1)] + [Fraction(0)] * N
for k in range(N + 1):
    ordered = [o + p for o, p in zip(ordered, power)]
    power = mul(power, ex_minus_1)
print("Fubini, 1/(2 - e^x):    ", counts(ordered))

graphs = [Fraction(2 ** comb(n, 2), factorial(n)) for n in range(N + 1)]
print("connected graphs on numbered vertices:", counts(log_series(graphs))[1:9])

T = [Fraction(0)] * (N + 1)
for _ in range(N + 1):
    eT = exp_series(T)
    T = [Fraction(0)] + eT[:N]
print("rooted trees from T = x e^T:", counts(T)[1:], " n^(n-1):", [n ** (n - 1) for n in range(1, N + 1)])
print("trees on numbered vertices n^(n-2):", [counts(T)[n] // n for n in range(1, N + 1)])

for n in [5, 8, 10]:
    dob = sum(k ** n / factorial(k) for k in range(60)) / e
    print(f"Dobinski estimate of B_{n}: {dob:.6f}")

Bell, exp(e^x - 1):      [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]
derangements, e^-x/(1-x): [1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961]
involutions, e^(x+x^2/2): [1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496]
permutations, exp(log 1/(1-x)): [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
Fubini, 1/(2 - e^x):     [1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563]
connected graphs on numbered vertices: [1, 1, 4, 38, 728, 26704, 1866256, 251548592]
rooted trees from T = x e^T: [1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000]  n^(n-1): [1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000]
trees on numbered vertices n^(n-2): [1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000]
Dobinski estimate of B_5: 52.000000
Dobinski estimate of B_8: 4140.000000
Dobinski estimate of B_10: 115975.000000

The series exponential and logarithm are computed exactly with fractions from the identity \(B' = A'B\) for \(B = e^A\). Every family appears: Bell numbers, derangements, involutions, Fubini numbers, the connected graph counts 1, 1, 4, 38, 728, and the rooted tree counts \(n^{n-1}\), obtained just by iterating \(T \gets xe^T\). Dobinski's series reproduces the Bell numbers to six decimal places.