跳转至

指數生成函數

序列 \(a\) 的指數生成函數（exponential generating function，EGF）定義為形式冪級數：

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

基本運算

指數生成函數的加減法與普通生成函數是相同的，也就是對應項係數相加。

考慮指數生成函數的乘法運算。對於兩個序列 \(a,b\)，設它們的指數生成函數分別為 \(\hat{F}(x),\hat{G}(x)\)，那麼

\[ \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} \]

因此 \(\hat{F}(x)\hat{G}(x)\) 是序列

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

的指數生成函數。

封閉形式

我們同樣考慮指數生成函數的封閉形式。

序列 \(\langle 1,1,1,\cdots\rangle\) 的指數生成函數是：

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

因為你將 \(\mathrm{e}^x\) 在 \(x = 0\) 處泰勒展開就得到了它的無窮級數形式。

類似地，等比數列 \(\langle 1,p,p^2,\cdots\rangle\) 的指數生成函數是：

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

指數生成函數與普通生成函數

如何理解指數生成函數？我們定義序列 \(a\) 的指數生成函數是：

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

但 \(F(x)\) 實際上也是序列 \(\left\langle \dfrac{a_n}{n!} \right\rangle\) 的普通生成函數。

這兩種理解沒有任何問題。也就是説，不同的生成函數只是對問題理解方式的轉變。

EGF 中多項式 exp 的組合意義

如果您還沒有學習多項式 exp 請先跳過這裏，這是由 exp 理解引出的意義，從某種意義上來説可以加深對 EGF 的理解。

EGF 中 \(f^n(x)\) 的 \(f\) 默認是一個 EGF，那麼我們首先考慮任意兩個 EGF 的乘積

\[ \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!} \]

對於兩個 EGF 相乘得到的 \([x^k]\hat{H}(x)\)，實際上是一個卷積。而如果考慮多個 EGF 相乘得到的 \([x^k]\hat{H}(x)\)，實際上就是對每個 EGF 選擇一項 \(x^{a_i}\) 使得 \(\sum_ia_i=k\) 時每種情況係數的和。 從集合的角度來理解就是把 \(n\) 個有標號元素劃分為 \(k>0\) 個有標號集合的方案數。

如果 \(k=0\) 則係數顯然為原 EGF 各項常數的積，但是多項式 \(\exp\) 中某些要求導致 \(\exp\) 的 \(f(x)\) 常數項必須為 \(0\)，具體的原因在下文中會做出一些説明。

多項式係數定義（具體請參考排列組合一欄中的多項式係數組合意義）裏是默認集合有序的，但是 \(\exp(f(x))\) 中 \(f^k(x)\)，\(k\) 個 \(f(x)\) 相乘得到的 EGF 相同，而集合劃分顯然是無序的，因此其係數應該乘上 \(\dfrac{1}{k!}\)。

設 \(F_k(n)\) 為 \(n\) 個有標號元素劃分成 \(k\) 個非空無序集合（因為是 \(\exp\) 所以有非空要求）的情況，\(f_i\) 為 \(i\) 個元素組成一個集合時，\(i\) 個元素的有限集上特定組合結構的數量（是原有的 EGF，對這一個集合元素計數的方案，僅僅與該集合大小有關），那麼 \(F_k(n)\)

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

設 \(f_n\) 的 EGF 為 \(\hat{F}(x)\)，即：

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

設 \(F_k(n)\) 的 EGF 為 \(G_k(x)\)，則：

\[ \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} \]

對於所有的 \(k \geq 0\)：

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

上面是從組合角度直接列式理解，我們也可以從遞推方面來證明 \(\exp(f(x))\) 和 \(f(x)\) 兩者間的關係。

同樣設 \(F_k(n)\) 為 \(n\) 個有標號元素劃分成 \(k\) 個非空集合（無標號）的情況，\(g_i\) 為 \(i\) 個元素組成一個集合內部的方案數（意義同上文中的 \(f_i\)），並令 \(G(x)\) 為 \(\{g_i\}\) 的 EGF，\(H_k(x)\) 為 \(\{F_k(n)\}\) 的 EGF。

\(n\) 個元素中取出 \(i\) 個元素作為一個單獨劃分出去的集合共有 \(g_i\) 種方案，剩下的 \(n-i\) 個元素構成 \(k-1\) 個集合共 \(F_{k-1}(n-i)\) 種方案，但最後的劃分方案中，一個方案裏的每個集合都會被枚舉為單獨劃分出去的集合，所以重複計算了 \(k\) 次，故還需要除以 \(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} \]

上界是由非空集合劃分推出的 \(n-(k-1)\geq i\)（前 \(k-1\) 個集合每個集合最少有一個元素），但是如果超過枚舉上界涉及的 \(F_{k-1}(n-i)\) 設為 \(0\)，那麼就沒有影響。

得到遞推式之後可遞歸展開，邊界為 \(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} \]

同樣的有：

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

顯然 定義成劃分為非空集合（\(g_0=0\)）是符合本身的意義的，如果 包含空集（\(g_0=1\)），那麼對應 \([x^n]G^k\) 中就會有 \([x^n]G^y,y>k\) 的貢獻（在至少一個 \(G\) 中選擇常數項），有計重，得不到所求量。

從遞推式的角度講，多個 EGF 的乘積也可以看作一個類似於揹包的組合（合併兩組計數對象的過程）。

總結多項式 \(\exp\) 的意義就是：有標號元素構成的集合的生成集族有多少種情況，或劃分為任意個非空子集的總方案數。

排列與圓排列

長度為 \(n\) 的排列數的指數生成函數是

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

圓排列的定義是把 \(1,2,\cdots,n\) 排成一個環的方案數。也就是説旋轉後的方案的等價的（但翻轉是不等價的）。

\(n\) 個數的圓排列數顯然是 \((n-1)!\)。因此 \(n\) 個數的圓排列數的指數生成函數是

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

也就是説 \(\exp \hat{Q}(x)=\hat{P}(x)\)。但這只是數學層面的推導。我們該怎樣直觀理解：圓排列數的 EGF 的 \(\exp\) 是排列數的 EGF？

一個排列，是由若干個置換環構成的。例如 \(p=[4,3,2,5,1]\) 有兩個置換環：

（也就是説我們從 \(p_i\) 向 \(i\) 連有向邊）

而不同的置換環，會導出不同的排列。例如將第二個置換環改成

那麼它對應的排列就是 \([5,3,2,1,4]\)。

也就是説，長度為 \(n\) 的排列的方案數是

  1. 把 \(1,2,\cdots,n\) 分成若干個集合
  2. 每個集合形成一個置換環

的方案數。而一個集合的數形成置換環的方案數顯然就是這個集合大小的圓排列方案數。因此長度為 \(n\) 的排列的方案數就是：把 \(1,2,\cdots,n\) 分成若干個集合，每個集合的圓排列方案數之積。

這就是多項式 \(\exp\) 的直觀理解。

推廣之

  • 如果 \(n\) 個點 帶標號 生成樹的 EGF 是 \(\hat{F}(x)\)，那麼 \(n\) 個點 帶標號 生成森林的 EGF 就是 \(\exp \hat{F}(x)\)——直觀理解為，將 \(n\) 個點分成若干個集合，每個集合構成一個生成樹的方案數之積。

  • 如果 \(n\) 個點帶標號無向連通圖的 EGF 是 \(\hat{F}(x)\)，那麼 \(n\) 個點帶標號無向圖的 EGF 就是 \(\exp \hat{F}(x)\)，後者可以很容易計算得到

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

    因此要計算前者，只需要一次多項式 \(\ln\) 即可。

接下來我們來看一些指數生成函數的應用。

應用

錯排數

錯排數

定義長度為 \(n\) 的一個錯排是滿足 \(p_i\ne i\) 的排列。

求錯排數的指數生成函數。

從置換環的角度考慮，錯排就是指置換環中不存在自環的排列。也就是説不存在長度為 \(1\) 的置換環。後者的指數生成函數是

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

因此錯排數的指數生成函數就是 \(\exp(-\ln(1-x)-x)\)。

不動點

不動點

題意：求有多少個映射 \(f:\{1,2,\cdots,n\}\to \{1,2,\cdots,n\}\)，使得

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

考慮 \(i\) 向 \(f(i)\) 連邊。相當於我們從任意一個 \(i\) 走 \(k\) 步和走 \(k-1\) 步到達的是同一個點。也就是説基環樹的環是自環且深度不超過 \(k\)（根結點深度為 \(1\)）。把這個基環樹當成有根樹是一樣的。因此我們的問題轉化為：\(n\) 個點帶標號，深度不超過 \(k\) 的有根樹森林的計數。

考慮 \(n\) 個點帶標號深度不超過 \(k\) 的有根樹，假設它的生成函數是：

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

考慮遞推求 \(\hat{F_k}(x)\)。深度不超過 \(k\) 的有根樹，實際上就是深度不超過 \(k-1\) 的若干棵有根樹，把它們的根結點全部連到一個結點上去。因此

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

那麼答案的指數生成函數就是 \(\exp \hat{F}_k(x)\)。求它的第 \(n\) 項即可。

Lust

Lust

給你一個 \(n\) 個數的序列 \(a_1,a_2,\cdots,a_n\)，和一個初值為 \(0\) 的變量 \(s\)，要求你重複以下操作 \(k\) 次：

  • 在 \(1,2,\cdots,n\) 中等概率隨機選擇一個 \(x\)。
  • 令 \(s\) 加上 \(\prod_{i\ne x}a_i\)。
  • 令 \(a_x\) 減一。

求 \(k\) 次操作後 \(s\) 的期望。

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

假設 \(k\) 次操作後 \(a_i\) 減少了 \(b_i\)，那麼實際上

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

因此實際上我們的問題轉化為，求 \(k\) 次操作後 \(\prod_{i=1}^n (a_i- b_i)\) 的期望。

不妨考慮計算每種方案的的 \(\prod_{i=1}^n (a_i- b_i)\) 的和，最後除以 \(n^k\)。

而 \(k\) 次操作序列中，要使得 \(i\) 出現了 \(b_i\) 次的方案數是

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

這與指數生成函數乘法的係數類似。

設 \(a_j\) 的指數生成函數是

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

那麼答案就是

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

為了快速計算答案，我們需要將 \(F_j(x)\) 轉化為封閉形式：

\[ \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} \]

因此我們得到

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

其中 \(\prod_{j=1}^n(a_j-x)\) 是一個 \(n\) 次多項式，可以暴力計算出來。假設它的展開式是 \(\sum_{i=0}^nc_ix^i\)，那麼

\[ \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} \]

計算這個多項式的 \(x^k\) 項係數即可。

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