Exponential Generating Functions

The exponential generating function (EGF) of a sequence $a$ is the formal power series:

$$\hat{F}(x)=\sum_{n}a_n \frac{x^n}{n!}$$

Basic operations

Addition and subtraction of exponential generating functions are the same as for ordinary generating functions: add the coefficients of corresponding terms.

Consider multiplication of exponential generating functions. For two sequences $a,b$, let their exponential generating functions be $\hat{F}(x),\hat{G}(x)$, respectively. Then

$$\begin{aligned} \hat{F}(x)\hat{G}(x) &=\sum_{i\ge 0}a_i\frac{x^i}{i!}\sum_{j\ge 0}b_j\frac{x^j}{j!}\\ &=\sum_{n\ge 0}x^{n}\sum_{i=0}^na_ib_{n-i}\frac{1}{i!(n-i)!}\\ &=\sum_{n\ge 0}\frac{x^{n}}{n!}\sum_{i=0}^n\binom{n}{i}a_ib_{n-i} \end{aligned}$$

Therefore, $\hat{F}(x)\hat{G}(x)$ is the exponential generating function of the sequence

$$\left\langle \sum_{i=0}^n \binom{n}{i}a_ib_{n-i} \right\rangle$$

It is therefore the exponential generating function of this sequence.

Closed forms

We likewise consider closed forms for exponential generating functions.

The exponential generating function of the sequence $\langle 1,1,1,\cdots\rangle$ is

$$\hat{F}(x) = \sum_{n \ge 0}\frac{x^n}{n!} = \mathrm{e}^x$$

This is because the Taylor expansion of $\mathrm{e}^x$ at $x = 0$ gives exactly its power-series form.

Similarly, the exponential generating function of the geometric sequence $\langle 1,p,p^2,\cdots\rangle$ is

$$\hat{F}(x) = \sum_{n\ge 0}\frac{p^nx^n}{n!}=\mathrm{e}^{px}$$

Exponential and ordinary generating functions

How should we understand exponential generating functions? Define the exponential generating function of a sequence $a$ as

$$F(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!}$$

But $F(x)$ is also the ordinary generating function of the sequence $\left\langle \dfrac{a_n}{n!} \right\rangle$.

There is no contradiction between these two interpretations. In other words, different generating functions merely reflect different ways of viewing a problem.

The combinatorial meaning of polynomial exp in EGF

If you have not learned polynomial exp, skip this section for now. It develops the meaning of exp and can deepen your understanding of EGF.

In an EGF, the function $f^n(x)$ contains $f$, which is itself an EGF. First consider the product of two arbitrary EGFs:

$$\hat{H}(x) = \hat{F}(x)\hat{G}(x) = \sum_{n\geq 0} \left[ \sum_{i = 0}^n\binom {n}{i}f_ig_{n-i} \right] \frac{x^n}{n!}$$

For the product of two EGFs, the coefficient $[x^k]\hat{H}(x)$ is a convolution. If we consider the product of several EGFs, $[x^k]\hat{H}(x)$ is the sum of the coefficients of all cases in which one term $x^{a_i}$ is selected from each EGF and $\sum_ia_i=k$. From the set-theoretic perspective, this counts the ways to partition $n$ labeled elements into $k>0$ labeled sets.

If $k=0$, the coefficient is clearly the product of the constant terms of the original EGFs. However, some requirements in polynomial $\exp$ force the constant term of $\exp$'s $f(x)$ to be $0$; the details are explained below.

In the definition of polynomial coefficients (see the combinatorial meaning of polynomial coefficients in the permutations and combinations section), sets are implicitly ordered; however, in $\exp(f(x))$, multiplying $f^k(x)$—that is, $k$ copies of $f(x)$—gives the same EGF regardless of order, while a partition of sets is clearly unordered. Therefore, its coefficient should be multiplied by $\dfrac{1}{k!}$.

Let $F_k(n)$ be the number of ways to partition $n$ labeled elements into $k$ nonempty unordered sets (nonempty because of $\exp$), and let $f_i$ be the number of specific combinatorial structures on a finite set of $i$ elements (the original EGF counts structures for an $i$-element set and depends only on the set size). Then $F_k(n)$ is

$$F_k(n)=\frac{n!}{k!}\sum_{\sum_{i}^ka_i=n}\prod_{j=1}^{k}\frac{f_{a_j}}{a_j!}$$

Let the EGF of $f_n$ be $\hat{F}(x)$, namely:

$$\hat{F}(x) = \sum_{n \geq 0} f_n\frac{x^n}{n!}$$

Let the EGF of $F_k(n)$ be $G_k(x)$. Then

$$\begin{aligned} G_k(x)&=\sum_{n \geq 0} F_k(n)\frac{x^n}{n!}\\ &=\sum_{n \geq 0} x^n\frac{1}{k!}\sum_{\sum_i^k a_i=n}\prod_{j=1}^{k}\frac{f_{a_j}}{a_j!}\\ &=\frac{1}{k!}\sum_{n \geq 0}\sum_{\sum_i^k a_i=n}\prod_{j=1}^{k}\frac{f_{a_j}x^{a_j}}{a_j!}\\ &=\frac{1}{k!}\hat{F}^k(x) \end{aligned}$$

For all $k \geq 0$,

$$\sum_{k \geq 0}G_k(x) = \sum_{k \geq 0}\frac{\hat{F}^k(x)}{k!} = \exp{\hat{F}(x)}$$

The derivation above directly writes the expression from the combinatorial viewpoint. We can also prove the relationship between $\exp(f(x))$ and $f(x)$ recursively.

Again let $F_k(n)$ be the number of ways to partition $n$ labeled elements into $k$ nonempty unordered sets, let $g_i$ be the number of structures on a set of $i$ elements (with the same meaning as $f_i$ above), and let $G(x)$ be the EGF of $\{g_i\}$ and $H_k(x)$ the EGF of $\{F_k(n)\}$.

Among the $n$ elements, choosing $i$ of them as one separate set gives $g_i$ choices; the remaining $n-i$ elements form $k-1$ sets in $F_{k-1}(n-i)$ ways. But each set in a partition is enumerated as the separate set once, so every partition is counted $k$ times and we must divide by $k$.

$$\begin{aligned} H_k(x) &= \sum_{n\ge 0}\cfrac{x^n}{n!}F_k(n)\\ &=\sum_{n\ge 0}\cfrac{x^n}{n!}\sum_{i=1}^{n-k+1}\binom n {i} F_{k-1}(n-i)\times g_i\times \cfrac{1}{k}\\ &=\cfrac{1}{k}\sum_{n\ge 0}\cfrac{x^n}{n!}\sum_{i=0}^{n}\binom n {i}F_{k-1}(n-i)\times g_i\\ &=\cfrac{1}{k}\cdot H_{k-1}(x)G(x) \end{aligned}$$

The upper bound comes from partitioning into nonempty sets, which gives $n-(k-1)\geq i$ because each of the first $k-1$ sets contains at least one element. If we define $F_{k-1}(n-i)$ to be $0$ beyond this bound, there is no effect.

After obtaining the recurrence, expand it recursively; when $k=1$, the boundary is $H_1(x)=G(x)$.

$$\begin{aligned} H_k(x) &= \cfrac{1}{k}\cdot H_{k-1}(x)G(x)\\ &= \cfrac{1}{k}\cdot\cfrac{1}{k-1}\cdot H_{k-2}(x)G^2(x)\\ &=\cdots \\ &= \cfrac{1}{k}\cdot\cfrac{1}{k-1} \cdots\cfrac{1}{2}\cdot H_{1}(x)G^{k-1}(x)\\ &= \cfrac{1}{k!}G^{k}(x)\\ \end{aligned}$$

Similarly,

$$\begin{aligned} \sum_{k\ge 0}H_k(x)=\sum_{k\ge 0}\cfrac{G^k(x)}{k!}=\exp G(x) \end{aligned}$$

Clearly, defining the structures as partitions into nonempty sets ($g_0=0$) matches the intended meaning. If the empty set is included ($g_0=1$), then $[x^n]G^k$ contains contributions from $[x^n]G^y,y>k$ (by choosing a constant term from at least one $G$), causing overcounting and failing to give the desired quantity.

From the recursive viewpoint, a product of several EGFs can also be viewed as a knapsack-like combination: the process of combining two groups of counted objects.

In summary, the meaning of polynomial $\exp$ is: the generating family of sets formed by labeled elements, or the total number of ways to partition them into any number of nonempty subsets.

Permutations and circular permutations

The exponential generating function for permutations of length $n$ is

$$\hat{P}(x)=\sum_{n\ge 0}\frac{n!x^n}{n!}=\sum_{n\ge 0}x^n=\frac{1}{1-x}$$

A circular permutation is a way to arrange $1,2,\cdots,n$ in a ring. Rotations of the same arrangement are equivalent, but reversals are not.

The number of circular permutations of $n$ numbers is clearly $(n-1)!$. Therefore, the exponential generating function of circular permutations of $n$ numbers is

$$\hat{Q}(x)=\sum_{n\ge 1}\frac{(n-1)!x^n}{n!}=\sum_{n\ge 1}\frac{x^n}{n}=-\ln(1-x)=\ln\left( \frac{1}{1-x} \right)$$

That is, $\exp \hat{Q}(x)=\hat{P}(x)$. This is only a mathematical derivation, however. How can we intuitively understand why the $\exp$ of the EGF of circular permutations is the EGF of permutations?

A permutation is composed of several permutation cycles. For example, $p=[4,3,2,5,1]$ has two permutation cycles:

(In other words, we draw a directed edge from $p_i$ to $i$.)

Different permutation cycles produce different permutations. For example, if we change the second permutation cycle to

the corresponding permutation becomes $[5,3,2,1,4]$.

Thus, the number of permutations of length $n$ is the number of ways to:

1. Divide $1,2,\cdots,n$ into several sets.
2. Turn each set into a permutation cycle.

The number of ways for the elements of one set to form a permutation cycle is exactly the number of circular permutations of that set. Therefore, the number of permutations of length $n$ is obtained by partitioning $1,2,\cdots,n$ into several sets and multiplying the circular-permutation counts for the sets.

This is the intuitive meaning of polynomial $\exp$.

More generally:

• If the EGF of labeled spanning trees on $n$ vertices is $\hat{F}(x)$, then the EGF of labeled spanning forests on $n$ vertices is $\exp \hat{F}(x)$—intuitively, partition the $n$ vertices into several sets and multiply the number of ways for each set to form a spanning tree.

• If the EGF of labeled undirected connected graphs on $n$ vertices is $\hat{F}(x)$, then the EGF of labeled undirected graphs on $n$ vertices is $\exp \hat{F}(x)$, which is easy to compute:

  $$\exp \hat{F}(x)=\sum_{n\ge 0}2^{\binom{n}{2}}\frac{x^n}{n!}$$

  Therefore, computing the former requires only one polynomial $\ln$.

Next we look at some applications of exponential generating functions.

Applications

Derangements

Derangements

A derangement of length $n$ is a permutation satisfying $p_i\ne i$.

Find the exponential generating function of the derangements.

From the perspective of permutation cycles, a derangement is a permutation with no self-loop in its cycles. In other words, it has no cycle of length $1$. The EGF of the latter is

$$\sum_{n\ge 2}\frac{x^n}{n}=-\ln\left(1-x\right)-x$$

Therefore, the EGF of derangements is $\exp(-\ln(1-x)-x)$.

Fixed points

Fixed points

Problem: Count the mappings $f:\{1,2,\cdots,n\}\to \{1,2,\cdots,n\}$ satisfying

$$\underbrace{f\circ f\circ\cdots\circ f}_{k}=\underbrace{f\circ f\circ\cdots\circ f}_{k-1}$$

$nk\le 2\times 10^6,1\le k\le 3$.

Draw an edge from $i$ to $f(i)$. The condition says that starting from any $i$, after $k$ steps and after $k-1$ steps we reach the same point. Thus every cycle in the functional graph is a self-loop and its depth is at most $k$ (the root has depth $1$). Treating this functional graph as a rooted tree gives the same result. The problem therefore becomes counting forests of rooted trees on $n$ labeled vertices with depth at most $k$.

Consider a rooted tree on $n$ labeled vertices with depth at most $k$, and suppose its generating function is

$$\hat{F_k}(x)=\sum_{n\ge 0}f_{n,k}\frac{x^n}{n!}$$

To derive $\hat{F_k}(x)$ recursively, observe that a rooted tree of depth at most $k$ consists of several rooted trees of depth at most $k-1$ whose roots are all connected to one new vertex. Hence

$$\hat{F_k}(x)=x\exp \hat{F}_{k-1}(x)$$

The answer's exponential generating function is therefore $\exp \hat{F}_k(x)$; compute its $n$-th term.

Lust

Lust

You are given a sequence of $n$ numbers $a_1,a_2,\cdots,a_n$ and a variable initially equal to $0$ named $s$. Repeat the following operations $k$ times:

• Choose an element from $1,2,\cdots,n$ uniformly at random and call it $x$.
• Increase $s$ by $\prod_{i\ne x}a_i$.
• Decrease $a_x$ by one.

After $k$ operations, find the expected value of $s$.

$1\le n\le 5000,1\le k\le 10^9,0\le a_i\le 10^9$.

Suppose that after $k$ operations, $a_i$ has decreased by $b_i$. Then in fact

$$s=\prod_{i=1}^n a_i-\prod_{i=1}^n(a_i- b_i)$$

Thus the problem is equivalent to, after $k$ operations, finding the expected value of $\prod_{i=1}^n (a_i- b_i)$.

Consider the sum of $\prod_{i=1}^n (a_i- b_i)$ over every sequence of choices, and divide by $n^k$ at the end.

In a sequence of $k$ operations, the number of sequences in which $i$ appears $b_i$ times is

$$\frac{k!}{b_1!b_2!\cdots b_n!}$$

which resembles the coefficient in multiplication of exponential generating functions.

Let the exponential generating function associated with $a_j$ be

$$F_j(x)=\sum_{i\ge 0}(a_j-i)\frac{x^i}{i!}$$

Then the answer is

$$[x^k]\prod_{j=1}^nF_j(x)$$

To compute the answer quickly, convert $F_j(x)$ to closed form:

$$\begin{aligned} F_j(x)&=\sum_{i\ge 0}a_j\frac{x^i}{i!}-\sum_{i\ge 1}\frac{x^i}{(i-1)!}\\ &=a_j\mathrm{e}^x-x\mathrm{e}^x\\ &=(a_j-x)\mathrm{e}^x \end{aligned}$$

Therefore,

$$\prod_{j=1}^nF_j(x)=\mathrm{e}^{nx}\prod_{j=1}^n(a_j-x)$$

Here $\prod_{j=1}^n(a_j-x)$ is an $n$-degree polynomial, which can be computed by brute force. Suppose its expansion is $\sum_{i=0}^nc_ix^i$. Then

$$\begin{aligned} \prod_{j=1}^nF_j(x) &=\left(\sum_{i\ge 0} \frac{n^ix^i}{i!}\right)\left(\sum_{i=0}^nc_ix^i\right)\\ &=\sum_{i\ge 0}\sum_{j=0}^i c_jx^j\frac{n^{i-j}x^{i-j}}{(i-j)!}\\ &=\sum_{i\ge 0}\frac{x^{i}}{i!}\sum_{j=0}^i n^{i-j}i^{\underline{j}}c_j \end{aligned}$$

It is enough to compute the coefficient of $x^k$ in this polynomial.