Enumerating Labeled Structures with Exponential Generating Functions

The Labeled World: Introducing Exponential Generating Functions

An Ordinary Generating Function (OGF) for a sequence $a_n$ is defined as $A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$. The key modification for an EGF is the inclusion of a factorial term.

The Exponential Generating Function for a sequence $a_0,a_1,a_2,\dots$ is defined as:
$A(x)={\sum }_{n=0}^{\infty }{a}_n\frac{x^n}{n!}$

Why this change? The answer lies in the product rule. For OGFs, the product $A(x)B(x)$ corresponds to combining two unlabeled structures. For EGFs, the product corresponds to combining two labeled structures.

To understand this critical distinction, please read the following brief introduction.

The core takeaway is that the multiplication of EGFs, $A(x)B(x)=C(x)$, automatically generates a sequence $c_n$ that follows the rule for partitioning labeled sets. This is the superpower of EGFs.

Application 1: Permutations of a Multiset

Let's see this in action. A classic use of EGFs is counting the number of arrangements (permutations) of a multiset, where some items are repeated but are still distinct types. For instance, how many 4-letter "words" can we form from the letters in PAPAYA?

The letters available are three Ps, two As, and one Y. We want to form a 4-letter word. We can think of this as building a structure of size 4 by picking letters from three different "bins".

The EGF for the P bin (we can choose 0, 1, 2, or 3 Ps) is:
$P(x)=1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}$
The EGF for the A bin (we can choose 0, 1, or 2 As) is:
$A(x)=1+\frac{x^1}{1!}+\frac{x^2}{2!}$
The EGF for the Y bin (we can choose 0 or 1 Y) is:
$Y(x)=1+\frac{x^1}{1!}$

The EGF for the combined problem is the product $F(x)=P(x)A(x)Y(x)$. The number of ways to form a 4-letter word is $a_4$, which we find by looking at the coefficient of $\frac{x^4}{4!}$ in $F(x)$. In other words, $a_4=4!\cdot [x^4]F(x)$.

The following video walks through this exact "PAPAYA" example and explains the mechanics of setting up the EGFs for each available letter and extracting the final count.

Application 2: Labeled Structures and the Exponential Formula

While the multiset permutation problem is a standard application, the true power of EGFs in advanced combinatorics comes from a principle often called the Exponential Formula. This is a framework for counting complex labeled objects by first counting their basic, "connected" components.

A prime example is counting permutations with specific cycle structures. A permutation of $n$ elements can be uniquely decomposed into disjoint cycles. The cycles are the "components."

1. Count the components: First, we find the EGF for a single component. How many ways can we form a single cycle on $k$ labeled elements? The answer is $(k-1)!$. So, the sequence for one cycle is $c_k=(k-1)!$ for $k\ge 1$, and $c_0=0$. The EGF for a single cycle is:
   $C(x)={\sum }_{k=1}^{\infty }{c}_k\frac{x^k}{k!}={\sum }_{k=1}^{\infty }(k-1)!\frac{x^k}{k!}={\sum }_{k=1}^{\infty }\frac{x^k}{k}=-\ln (1-x)$

2. Combine the components: A general permutation is a set of these cycles. If we have $k$ cycles, the EGF would be $\frac{C(x{)}^k}{k!}$ (we divide by $k!$ because the cycles themselves are indistinguishable). To account for any number of cycles, we sum over all possible $k$:
   $F(x)={\sum }_{k=0}^{\infty }\frac{C(x{)}^k}{k!}=\exp (C(x))$

This is the Exponential Formula: if $C(x)$ is the EGF for a single component, then $\exp (C(x))$ is the EGF for a structure made of any number of those components.

For all permutations, the EGF is $\exp (-\ln (1-x))=\frac{1}{1-x}$. The coefficients of this EGF are $a_n=n!$, which is correct!

This framework is incredibly versatile. By modifying $C(x)$, we can count permutations with various restrictions. The following reading explores this idea in detail.

Practice Problems

It's time to apply these concepts.

1. Word Arrangements: How many 5-letter "words" can be formed using the digits {1, 1, 2, 3, 4}? Set up the EGFs for each digit and find the coefficient that gives the answer.

2. Derangements: A derangement is a permutation with no fixed points. This means it has no cycles of length 1.
   (a) Start with the EGF for a single cycle, $C(x)=-\ln (1-x)$. What is the new component EGF, $C_D(x)$, if cycles of length 1 are forbidden?
   (b) The EGF for derangements is $D(x)=\exp (C_D(x))$. Show that this simplifies to $D(x)=\frac{e^{-x}}{1-x}$.
   (c) By multiplying the series for $e^{-x}$ and $\frac{1}{1-x}$, find the coefficient of $\frac{x^n}{n!}$ in $D(x)$ to re-derive the famous formula for the number of derangements, $d_n$.

3. Involutions: An involution is a permutation $p$ such that $p^2$ is the identity. This means all cycles in its decomposition have length 1 or 2.
   (a) What is the EGF, $C_I(x)$, for a single component (a cycle of length 1 or 2)?
   (b) Using the exponential formula, write down the EGF, $I(x)$, for the total number of involutions on $n$ elements.
   (c) Use your result from (b) to calculate the number of involutions on 4 elements, $a_4$. (You'll need to compute $4!\cdot [x^4]I(x)$).

4. A Deeper Dive (Challenge): The video below provides a complete derivation for Lah numbers, which count partitions of $\{1,...,n\}$ into $k$ ordered subsets. It's an excellent case study of the entire generating function pipeline, from recurrence to differential equation to closed form.

Conclusion

In this lesson, you've added a powerful new instrument to your combinatorial toolkit. You learned that while Ordinary Generating Functions count structures on unlabeled sets, Exponential Generating Functions are designed for labeled sets. The key is their product rule, $c_n=\sum \left(\genfrac{}{}{0ex}{}{n}{k}\right)a_k{b}_{n-k}$, which naturally models the process of splitting a labeled set. We saw how to use this for direct counting problems, like word arrangements, and for more abstract structures via the Exponential Formula, $\exp (C(x))$, which allows us to count objects built from smaller, independent components like cycles in a permutation.

This lesson concludes our module on generating functions. You have progressed from basic recurrence relations to the sophisticated machinery used to solve Olympiad-level counting problems. In our next module, we will begin our study of Graph Theory. Many of the concepts we've touched upon—such as permutations as cycles, or network-like problems—are most naturally described using the language of graphs. We will start by defining the fundamental terminology of vertices, edges, paths, and cycles.