A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Exponential generating functions (EGFs) are F(x) = Σ(aₙ/n!)xn and encode labeled structures (permutations, labeled graphs). Multiplying EGFs corresponds to merging labeled structures, making them ideal for labeled enumeration. The symbolic method with EGFs elegantly counts labeled graphs, trees, and other structures via transfer between combinatorics and analysis.
You already know that an ordinary generating function (OGF) encodes a sequence (aₙ) as F(x) = Σ aₙxⁿ, where the coefficient of xⁿ is exactly aₙ. An exponential generating function (EGF) makes a small but crucial adjustment: F(x) = Σ (aₙ/n!) xⁿ. You divide each coefficient by n! before encoding it. This means that to *recover* aₙ from the EGF, you extract the coefficient of xⁿ and multiply by n!. The reason for this twist is that EGFs are designed for labeled structures — combinatorial objects whose elements are distinguishable, assigned distinct labels from {1, 2, …, n}.
The key operation that makes EGFs powerful is multiplication. Suppose F(x) counts labeled structures of type A (with aₙ structures on n labeled elements) and G(x) counts type B. Then F(x)·G(x) counts compound structures built by partitioning n labeled elements into two groups — sending k to type A and the remaining n−k to type B — and summing over all ways to split. The n! denominator ensures that the binomial coefficient C(n,k) appears naturally when you expand the product, accounting for all ways to choose which k elements go to part A. This is why OGFs don't work for labeled counting: OGF multiplication doesn't incorporate the combinatorial C(n,k) factor automatically.
The most important EGF is ex = Σ xⁿ/n!, which corresponds to aₙ = 1 for all n — meaning there is exactly one labeled structure of each size. A single element, or a set of n labeled elements with no internal structure, is counted once. The EGF for permutations of n elements is 1/(1−x) (since aₙ = n!), and indeed Σ (n!/n!) xⁿ = Σ xⁿ = 1/(1−x). The product (ex)² = e2x has coefficient of xⁿ equal to 2ⁿ/n!, so aₙ = 2ⁿ — this counts the number of ways to assign each of n labeled elements to one of two groups, which is indeed 2ⁿ.
The symbolic method lets you write down the EGF for a complex labeled structure directly from its combinatorial description. A labeled graph is a set of labeled vertices with edges; a labeled tree satisfies Cayley's formula (aₙ = nⁿ⁻²). By translating recursive decompositions into algebraic equations on EGFs and solving, you can derive exact formulas for counts that would be intractable by direct enumeration. The trade-off with OGFs is one of domain: OGFs excel at unlabeled structures (like integer partitions or binary trees up to symmetry), while EGFs excel wherever labels distinguish otherwise-identical structures.