指数公式定理

· · 个人记录

指数公式定理

说明

如果存在两个 EGF F(x) 与 G(x)，满足 e^{F(x)}=G(x)，F(x) 是 {f_i} 的 EGF，那么 G(x) 是

g_n=\sum_{\pi=\{S_1,S_2,\dots,S_k\}}\prod_{i=1}^k f_{|S_i|}

的 EGF，其中 \pi 是 [n] 的划分。

证明

定义

物品：一个正整数集合 S 以及一个身份 P。一个物品 T 的权值 |T|=|S|。一个物品可以退化为它的集合 S。
同构：两个物品 T_1,T_2 对于一个集合 S' 同构当且仅当 T_2 等于集合 S' 以及 T_1 的身份。如果 S'=[n]，叫 T_2 标准构。
组：一些物品 \{T_1,T_2,\dots,T_k\}，其中 n=\sum|T_i|，\cup T_i=[n]，T_i\cap T_{j\neq i}=\varnothing，也就是说 \{T_1,T_2,\dots,T_k\} 是 [n] 的划分。这个组的 权值 为 n。h(n,k) 为有多少个 k 物品的权值为 n 组。
堆：一些身份互不相同但是权值相同的物品集合。这个类型的权值为它包含的物品的共同权值。
规划：堆 D_1,D_2,\dots，其中 D_i 权值为 i。一个规划的堆枚举为 \mathbf{D}(x) = \mathbf{d}_i=|D_i| 的 egf。一个规划的组枚举为 H(x,y)=\sum_{0\le n,k}h(n,k)\frac{x^n}{n!}y^k

定理 1

假设 F' 和 F'' 是两个规划。那么我们可以通过“合并”所有堆来形成一个新规划 F=F'\oplus F''。具体说一点，F 的第 i 的堆等于 F’ 的第 i 的堆和 ‘’F 的第 i 的堆的合并。

那么 F 的组枚举 = F' 的堆枚举 乘 F'' 的堆枚举。

证明：显然有

h(n,k)=\sum_{n',k'}\binom{n}{n'}h'(n',k')h''(n-n',k-k')

这个明显是一个卷积形式，所以对应生成函数乘起来就可以。

定理 2

假设一个规划仅仅有一个权值为 r 的物品。那么，因为 |D_i|=[i=r]，这个规划的堆枚举等于 x^r/r!。

那么，对于 k,r，一个权值为 kr 并且 k 物品的组才存在。我们现在想计算这些存在的组有多少个不同的。

个组里面的物品无序，但是因为所有物品互不相同，可以直接统计“有序组”然后除 k!。\{1,2,\dots,kr\} 的 k 组有序划分就是

\binom{kr}{\underbrace{r\ r\ r\cdots r}_k}=\frac{(kr)!}{r!^k}

除 k! 就可以了：

h(kr,k)=\frac{(kr)!}{r!^kk!}

那么来做出来 H(x,y) 了：直接枚举 k

H(x,y)=\sum_k\frac{(kr)!}{r!^kk!}\frac{x^{kr}}{(kr)!}y^{k}=\sum_k\frac{x^{kr}y^k}{r!^kk!}=\sum_k\frac{1}{k!}(\frac{yx^r}{r!})^k=e^{\frac{yx^r}{r!}}

这个规划叫 \Omega_r，对应的组枚举叫 \Omega_r(x,y)。

引理

注意到由于定理 1，任意一个规划可以分成一些（可能无限多）的 \Omega_r 的合并。如果现在的规划是 F，并且它的堆是 D_0,D_1,D_2,\dots，那

F=(\underbrace{\Omega_0\oplus\cdots\oplus\Omega_0}_{|D_0|})\oplus(\underbrace{\Omega_1\oplus\cdots\oplus\Omega_1}_{|D_1|})\oplus\dots

那么，由于定理 1，F 的组枚举等于

H(x,y)=\prod\Omega_i(x,y)^{|D_i|}=\prod (e^{\frac{yx^i}{i!}})^{|D_i|}=(\prod e^{|D_i|\frac{x^i}{i!}})^y=( e^{\sum|D_i|\frac{x^i}{i!}})^y

看到 e 的指数显然是 |D_i| EGF，或者它的堆枚举，所以

H(x,y)=e^{y\mathbf D(x)}

来不限制组的大小，直接插入 y=1，得到 H(x)=e^{\mathbf D(x)}，证明完毕。

等等，还有更多应用！如果把这个式子按 y 系数展开，得到：

H(x,y)=\sum_k\frac{(y\mathbf D(x))^k}{k!}

那么就有

h(n,k)=[\frac{x^n}{n!}][y^k]H(x,y)=[\frac{x^n}{n!}]\frac{(y\mathbf D(x))^k}{k!}=[\frac{x^n}{n!}]\frac{\mathbf D(x)^k}{k!}

例题

P4841 城市规划

物品：一个有标号连通图
组：一些有标号连通图，形成一个有标号（可能不连通）图
堆：所有大小为 n 的连通图

在这里面我们有单变量的组枚举 H(x)，或者 h(x)=2^\binom{x}{2} 的 EGF。我们的答案是 [\frac{x^n}{n!}]\mathbf D(x)，就是以上反问题；直接做 \ln 即可。

P5409 第一类斯特林数·列

物品：一个有标号环
组：一个排列，这个排列给分成几个环了
堆：所有大小为 n 的环

这样，堆枚举是 \mathbf d(x)=(x-1)! 的 EGF，或者 \mathbf D(x)=\ln\frac{1}{1-x}。

直接套入到第二个公式里面，就有

\begin{bmatrix}n\\k\end{bmatrix}=[\frac{x^n}{n!}]\frac{(\ln\frac{1}{1-x})^k}{k!}=n![x^n]\frac{(\ln\frac{1}{1-x})^k}{k!}

用快速幂计算出来并且求出来前 n 系数就可以了。

P5396 第二类斯特林数·列

物品：一个 {1,2,\dots,n} 集合
组：一个集合的划分
堆：唯一的那个物品

这样，堆枚举是 \mathbf d(x)=[x\neq0] 的 EGF，或者 \mathbf D(x)=e^x-1。

直接套入到第二个公式里面，就有

\begin{Bmatrix}n\\k\end{Bmatrix}=[\frac{x^n}{n!}]\frac{(e^x-1)^k}{k!}=n![x^n]\frac{(e^x-1)^k}{k!}

用快速幂计算出来并且求出来前 n 系数就可以了。

P5748 集合划分计数

特别类似与以上的题目，但是这里是一行里里面所有数求和。

其实这个有一个特别好的方法：直接在组枚举里面插入 y=1！

H(x,y)=e^{y\mathbf D(x)}\implies H(x)=e^{\mathbf D(x)}

因为 \mathbf D(x)=e^x-1，则有答案的生成函数了：

e^{e^x-1}