6.2 Exponential generating functions

Exponential Generating Functions

Definition and Basic Properties

An exponential generating function (EGF) encodes a sequence by attaching a factorial denominator to each term. Where an ordinary generating function (OGF) stores the sequence $(a_n)$ as $\sum a_n x^n$, an EGF stores it as:

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

That $n!$ in the denominator is the whole point. It's what makes EGFs naturally suited to labeled objects, where the order in which you assign labels matters. Dividing by $n!$ bakes in the bookkeeping for all possible labelings, so when you multiply two EGFs together, the algebra automatically handles the combinatorics of merging labeled sets.

A few foundational EGFs to know:

• $e^x = \sum_{n \geq 0} \frac{x^n}{n!}$ is the EGF for the constant sequence $(1, 1, 1, \ldots)$, since every coefficient $a_n = 1$.
• $e^{cx}$ is the EGF for the sequence $(c^n)$, since the coefficient of $\frac{x^n}{n!}$ is $c^n$.
• $e^x - 1$ is the EGF for $(0, 1, 1, 1, \ldots)$, which drops the constant term. This is useful when you need "at least one" of something.

As with OGFs, EGFs are treated as formal power series. You don't worry about whether the series converges; you just manipulate coefficients algebraically.

Why EGFs Instead of OGFs?

The choice between OGF and EGF comes down to whether your objects are unlabeled or labeled.

• OGFs count combinations of unlabeled objects (e.g., how many ways to choose 5 identical balls from 3 bins).
• EGFs count arrangements of labeled objects (e.g., how many ways to assign 5 distinct people to 3 committees).

The product of two EGFs automatically performs a binomial convolution: if $A(x)$ is the EGF for $(a_n)$ and $B(x)$ is the EGF for $(b_n)$, then the coefficient of $\frac{x^n}{n!}$ in $A(x) \cdot B(x)$ is:

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

That binomial coefficient $\binom{n}{k}$ is exactly what you need when you're splitting a set of $n$ labeled objects into a subset of size $k$ and a subset of size $n - k$. This is why multiplication of EGFs corresponds to partitioning labeled objects into two independent structures.

Constructing Exponential Generating Functions

Basic Construction Techniques

To build an EGF for a counting problem:

1. Define the sequence. Let $a_n$ be the number of labeled structures on $n$ elements that you want to count.
2. Write the series. Form $G(x) = \sum_{n \geq 0} a_n \frac{x^n}{n!}$.
3. Recognize or simplify. Try to express $G(x)$ in closed form using known functions.

Some standard EGFs worth memorizing:

• Addition: $A(x) + B(x)$ adds sequences term by term. Use this for unions of disjoint classes of structures.
• Multiplication: $A(x) \cdot B(x)$ performs binomial convolution. Use this when you independently build a structure on one labeled subset and another structure on the remaining labels.

Advanced Construction Methods

• Differentiation of an EGF shifts the sequence: if $G(x)$ is the EGF for $(a_n)$, then $G'(x)$ is the EGF for $(a_{n+1})$. Combinatorially, differentiating often corresponds to marking a distinguished element (choosing one labeled object to treat specially).
• Integration reverses this. Integrating $G(x)$ (with constant of integration 0) gives the EGF for $\left(\frac{a_{n-1}}{1}\right)$, shifted the other way. This can represent "unmarking" or accumulating a sum.
• Composition is where EGFs get really powerful. The compositional formula (also called the exponential formula) says: if $B(x)$ is the EGF for connected structures with $B(0) = 0$, then

$e^{B(x)}$

is the EGF for structures that are sets of those connected components. For example, since the EGF for a single connected cycle on $n \geq 1$ vertices is $\ln\!\left(\frac{1}{1-x}\right)$, the EGF for permutations (which are sets of cycles) is $e^{\ln(1/(1-x))} = \frac{1}{1-x}$, confirming that there are $n!$ permutations of $n$ elements.

More generally, if $C(x)$ is the EGF for structures placed on each block and $B(x)$ is the EGF for the "outer" partitioning structure, then the composition $B(C(x))$ counts the combined labeled structure.

Interpreting Coefficients of EGFs

Basic Interpretation

To extract a count from an EGF:

1. Find the coefficient of $x^n$ in $G(x)$ (call it $[x^n] G(x)$).
2. Multiply by $n!$ to recover $a_n$.

Equivalently, $a_n = n! \cdot [x^n] G(x)$, which is the same as reading off the coefficient of $\frac{x^n}{n!}$.

Why the factorial matters: The $n!$ in the denominator accounts for all possible ways to assign $n$ distinct labels. When you multiply two EGFs, the binomial convolution automatically counts how to split labels between two substructures. So the coefficient you extract already reflects labeled counting.

Interpreting products: If $G(x) = A(x) \cdot B(x)$, then $a_n$ for the product counts the number of ways to choose a subset $S$ of $\{1, 2, \ldots, n\}$, build an $A$-structure on $S$, and build a $B$-structure on the complement.

Advanced Interpretation Techniques

• Alternating signs in the coefficients often signal an inclusion-exclusion argument. For instance, the EGF for derangements involves $e^{-x}$, and expanding it gives the familiar alternating sum $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$.
• Composed EGFs like $e^{B(x)}$ have coefficients that count partitions of $\{1, \ldots, n\}$ into blocks, with each block carrying a $B$-structure. The Bell numbers $B_n$ arise from $e^{e^x - 1}$, where each block is simply a nonempty set.
• Asymptotic analysis of EGF coefficients uses tools from analytic combinatorics (singularity analysis, saddle-point method). For this course, the key idea is that the dominant singularity of $G(x)$ controls the growth rate of $a_n$. For example, $\frac{1}{1-x}$ has a singularity at $x = 1$, consistent with $a_n = n!$ growing factorially.

Counting Labeled Objects with EGFs

Problem-Solving Approach

Here's a general strategy for EGF-based counting problems:

1. Model the structure. Decide what a "labeled structure on $n$ elements" looks like for your problem.
2. Decompose. Break the structure into independent parts (e.g., "partition into blocks, then arrange within each block").
3. Translate to EGFs. Write the EGF for each component. Use multiplication for independent labeled parts, composition for nested structures, and the exponential formula for "sets of connected pieces."
4. Simplify. Use algebra, known series, or differential equations to get a closed form.
5. Extract coefficients. Read off $[x^n/n!]$ from the result to get your answer.

Common Problem Types and Techniques

Derangements: A derangement is a permutation with no fixed points. The EGF is:

$\frac{e^{-x}}{1 - x}$

This comes from the product of the EGF for "all permutations" ($\frac{1}{1-x}$) with an inclusion-exclusion correction ($e^{-x}$). Extracting coefficients gives $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$.

Set partitions and Bell numbers: The number of ways to partition $\{1, \ldots, n\}$ into nonempty subsets is the Bell number $B_n$. Since a set partition is a "set of nonempty sets," the exponential formula gives:

$\text{EGF} = e^{e^x - 1}$

Surjections: The number of surjective functions from an $n$-set onto a $k$-set can be extracted from the EGF $(e^x - 1)^k$, since each of the $k$ target elements must have a nonempty preimage.

Labeled trees: By Cayley's formula, there are $n^{n-2}$ labeled trees on $n$ vertices. The EGF for labeled rooted trees $T(x)$ satisfies $T(x) = x \, e^{T(x)}$, and the EGF for unrooted labeled trees is $T(x) - \frac{T(x)^2}{2}$.

Labeled graphs: The EGF for labeled connected graphs can be obtained from the EGF for all labeled graphs (which is $\sum_{n \geq 0} 2^{\binom{n}{2}} \frac{x^n}{n!}$) via the logarithm of the exponential formula: if $G(x)$ is the EGF for all labeled graphs, then $\ln G(x)$ is the EGF for connected labeled graphs.