Exponential Generating Function

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

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

Basic Operations

The addition and subtraction of exponential generating functions are the same as those of ordinary generating functions, i.e., adding the corresponding coefficients.

Consider the 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} \]

Thus \(\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 \]

Closed Form

We also consider the closed form of 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 \]

because expanding \(\mathrm{e}^x\) as a Taylor series at \(x = 0\) yields its infinite 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 Generating Functions vs. Ordinary Generating Functions

How to understand exponential generating functions? We define the exponential generating function of sequence \(a\) as:

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

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

Both interpretations are valid. That is, different generating functions are just different perspectives on the problem.

Combinatorial Meaning of Polynomial exp in EGF

If you haven't learned polynomial exp yet, please skip this section for now. This meaning arises from understanding exp and can deepen the understanding of EGF in a sense.

In EGF, \(f^n(x)\) assumes \(f\) is an EGF. First consider the product of any two 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 \([x^k]\hat{H}(x)\) obtained by multiplying two EGFs, it is essentially a convolution. If we consider \([x^k]\hat{H}(x)\) obtained by multiplying multiple EGFs, it is the sum of coefficients for each way of choosing a term \(x^{a_i}\) from each EGF such that \(\sum_ia_i=k\). From a set perspective, this counts the number of ways to partition \(n\) labeled elements into \(k>0\) labeled sets.

If \(k=0\), the coefficient is obviously the product of the constant terms of the original EGFs. However, certain requirements in polynomial \(\exp\) force the constant term of \(f(x)\) in \(\exp(f(x))\) to be \(0\). The reason for this will be explained later.

The multinomial coefficient definition (refer to the combinatorial meaning of multinomial coefficients in the combinatorics section) assumes ordered sets by default. But in \(\exp(f(x))\), the \(k\) factors \(f(x)\) are identical, while set partitions are unordered. Therefore, the 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 due to \(\exp\)), and let \(f_i\) be the number of specific combinatorial structures on a set of \(i\) elements (the original EGF, counting schemes for this set, depending only on its 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)\), i.e.:

\[ \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 above is a direct combinatorial derivation. We can also prove the relationship between \(\exp(f(x))\) and \(f(x)\) from a recurrence perspective.

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

From \(n\) elements, choose \(i\) elements to form a separate set; there are \(g_i\) ways. The remaining \(n-i\) elements form \(k-1\) sets in \(F_{k-1}(n-i)\) ways. However, in the final partition, each set will be enumerated as the separately chosen set, so it is overcounted \(k\) times. Thus we need to 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 nonempty set partitions: \(n-(k-1)\geq i\) (each of the first \(k-1\) sets has at least one element). But if we set \(F_{k-1}(n-i)=0\) for indices beyond the bound, it doesn't affect the result.

From the recurrence, we can expand recursively, with the base case \(k=1\): \(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 as partitions into nonempty sets (\(g_0=0\)) aligns with its meaning. If including the empty set (\(g_0=1\)), then \([x^n]G^k\) would include contributions from \([x^n]G^y,y>k\) (choosing the constant term in at least one \(G\)), leading to overcounting and not obtaining the desired quantity.

From the recurrence perspective, the product of multiple EGFs can also be seen as a combinatorial process similar to knapsack (merging two groups of counted objects).

In summary, the meaning of polynomial \(\exp\) is: the number of ways to form a family of sets from labeled elements, or the total number of ways to partition into any number of nonempty subsets.

Permutations and Circular Permutations

The exponential generating function for the number of 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 of \(1,2,\cdots,n\) is an arrangement on a circle, where rotations are considered equivalent (but reflections are not).

The number of circular permutations of \(n\) numbers is clearly \((n-1)!\). Thus the exponential generating function for the number 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)\). But this is just a mathematical derivation. How can we intuitively understand that the \(\exp\) of the EGF for circular permutations is the EGF for permutations?

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

(That is, we draw a directed edge from \(p_i\) to \(i\).)

Different cycles lead to different permutations. For example, changing the second cycle to

corresponds to the permutation \([5,3,2,1,4]\).

In other words, the number of permutations of length \(n\) is the number of ways to:

Partition \(1,2,\cdots,n\) into several sets.
Each set forms a cycle.

The number of ways for a set of size \(m\) to form a cycle is exactly the number of circular permutations of that size. Therefore, the number of permutations of length \(n\) is: partition \(1,2,\cdots,n\) into sets, and take the product of the circular permutation counts for each set.

This is the intuitive understanding of polynomial \(\exp\).

Generalizing:

If the EGF for labeled spanning trees on \(n\) vertices is \(\hat{F}(x)\), then the EGF for labeled spanning forests on \(n\) vertices is \(\exp \hat{F}(x)\)—intuitively, partition the \(n\) vertices into sets, each forming a spanning tree, and multiply the counts.
If the EGF for labeled connected undirected graphs on \(n\) vertices is \(\hat{F}(x)\), then the EGF for labeled undirected graphs on \(n\) vertices is \(\exp \hat{F}(x)\). The latter can be easily computed as

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

Therefore, to compute the former, only one polynomial \(\ln\) is needed.

Next, let's look at some applications of exponential generating functions.

Applications

Derangements

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

Find the exponential generating function for the number of derangements.

From the cycle perspective, a derangement is a permutation with no fixed points (cycles of length 1). The EGF for permutations without fixed points (i.e., excluding cycles of length 1) is

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

Thus the exponential generating function for derangements is \(\exp(-\ln(1-x)-x)\).

Fixed Points

Problem: Count the number of mappings \(f:\{1,2,\cdots,n\}\to \{1,2,\cdots,n\}\) such that

\[ \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\).

Consider drawing an edge from \(i\) to \(f(i)\). The condition means that starting from any \(i\), walking \(k\) steps and walking \(k-1\) steps leads to the same vertex. That is, cycles in the functional graph are self-loops, and the depth (with root depth 1) is at most \(k\). Treating this functional graph as a rooted tree works. Thus our problem reduces to: count the number of labeled rooted forests on \(n\) vertices where the depth of each tree is at most \(k\).

Consider labeled rooted trees on \(n\) vertices with depth at most \(k\). Let their generating function be:

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

We derive a recurrence for \(\hat{F_k}(x)\). A rooted tree of depth at most \(k\) is essentially several rooted trees of depth at most \(k-1\), with their roots all connected to a new root vertex. Therefore

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

Then the EGF for the answer is \(\exp \hat{F}_k(x)\). Compute its \(n\)-th term.

Lust

You are given a sequence \(a_1,a_2,\cdots,a_n\) of \(n\) numbers and a variable \(s\) initially \(0\). Repeat the following operation \(k\) times:

Randomly choose \(x\) uniformly from \(1,2,\cdots,n\).
Add \(\prod_{i\ne x}a_i\) to \(s\).
Decrease \(a_x\) by \(1\).

Find the expected value of \(s\) after \(k\) operations.

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

Suppose after \(k\) operations, \(a_i\) is decreased by \(b_i\). Then actually

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

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

Consider computing the sum of \(\prod_{i=1}^n (a_i- b_i)\) over all possible operation sequences, then divide by \(n^k\).

In a sequence of \(k\) operations, the number of sequences where \(i\) appears \(b_i\) times is

\[ \frac{k!}{b_1!b_2!\cdots b_n!} \]

This resembles the coefficients in EGF multiplication.

Let the EGF for \(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 quickly, we 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} \]

Thus we have

\[ \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 a polynomial of degree \(n\), which can be computed directly. 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} \]

Compute the coefficient of \(x^k\) in this polynomial.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用