「组合数 ☆ GF ☆ 容斥 ☆ burnside」

· · 个人记录

标题味太重了，吓到我了，博主快赔钱。

前排提醒：这篇文章整活居多，实际干货不多。

\text{\red{crashed}} 要推广组合数，于是组合数得到了推广。

\text{\red{crashed}} 见推广是好的，便把它留了下来。

——《\text{\red{crashed}} 为什么是神 · 旧约》

本篇文章内容大多纯属胡编，如相关现实人物产生不适，我立刻删。

以下默认读者有过九年义务教育。

根据大家小学一年级就学过的知识：从 n 个物品里面选 k 个的方案数为 \binom{n}{k} = \frac{\prod_{t = 0}^{k - 1}(n - t)}{k!}。

但是，假如说这些个物品不是相同的 —— 第 i 个物品竟然带有权值 u_i！（不是 u_i 的阶乘）

我们需要对于所有 s = 0,1,\dots 求出，选出 k 个物品使得权值总和 \sum u_i = s 的方案数。哦，上帝，这对于一年级学生而言是多么困难的问题啊！

但是 —— 好在我们二年级就引入了 GF。直接列出答案：

F_k(x) = [y^k]\prod_{i = 1}^{n}(1 + x^{u_i}y)

利用三年级所学到的 exp/ln 化简连乘式的技巧（以下设 \sum_{i = 1}^{n}x^{u_i} = G(x)）：

F_k(x) = (-1)^k[y^k]\prod_{p=1}^{k}e^{-y^pG(x^p)/p}

推导过程被 King Crimson 削去了。

但是まだまだ，这个形式，对于已经在一年级接触过组合数公式的人而言（话说，读者应该已经发现当 u_i = 1,\forall i\in[1, n] 时，上述问题等价于组合数问题了吧），毫无疑问，实在是太丑陋了 简直就像隔壁苏珊婶婶做的苹果派。

注意力集中！不要忘记使用我们四年级充分学习的猜结论技巧。我们猜测：

F_k(x) = \frac{\prod_{t=0}^{k-1}(G(x) - t\mathscr E)}{k!}

其中 \mathscr E 是 “虽然不知道它具体什么含义但是总觉得一定是很厉害的使得式子成立的算子”，简称 “不明觉厉算子”。

继续使用在五年级充分学习的展开验证技巧，搭配充分学习的猜结论技巧，我们猜测 \mathscr E 满足：

G(x^k)\mathscr E = G(x^{k+1})

哦，天哪，竟然找不出反例！

在六年级没有引入合适的工具，但是综合我们学到的知识，我们可以证明上面两个答案的等价性 （留作小升初毕业考习题） 。

考察每个单项的系数，设有 a_1 个 G(x)，a_2 个 G(x^2)，。。。，a_n 个 G(x^n)，使得满足 \sum_{i=1}^{n}ia_i = n。

先看符号，exp/ln 方法给出的符号为 (-1)^{k + \sum_{i=1}^{n}a_i}，猜测方法给出的符号为 (-1)^{k - \sum_{i=1}^{n}a_i}。

然后看系数绝对值。exp/ln 方法给出的值为 \prod_{i=1}^{n}\frac{1}{a_i!i^{a_i}}。

至于猜测方法，观察，每个单项一共 \sum_{i=1}^{n}a_i 个乘积因子，假设按展开顺序从前往后分别为 G(x^{b_1}),G(x^{b_2}),\dots,G(x^{b_{\sum a}})。

假设定义的 “下降幂” 第 r 个因子 (G(x) - r\mathscr E) 选择了 G(x)，则给系数乘以因子 1/r。r = 0 一定选择 G(x)，所以我们乘以 1/k。

那么总系数其实就是 b_1,b_2,\dots,b_{\sum a} 全排列，每个排列贡献 \prod_{i=1}^{\sum a}\frac{1}{\sum_{j=1}^{i}b_j}，所有排列贡献之和。

这是个经典问题，答案为 \prod_{i=1}^{\sum a}\frac{1}{b_i}，放在这个情境下就是 \prod_{i=1}^{n}\frac{1}{i^{a_i}}。

最后需要给方案数乘上因子 \prod_{i=1}^{n}\frac{1}{a_i!} 去重，因此系数绝对值为 \prod_{i=1}^{n}\frac{1}{a_i!i^{a_i}}。

“这个也太麻烦了” 读者这样抱怨道，“难道不能直接推吗”。

根据我们初中一年级所掌握的群作用计数相关知识，容易发现这个问题就是 polya 容斥。

就是 polya 容斥！就是 polya 容斥！（魔怔人的上升）

\sum_{g\in S_n}\frac{\operatorname{sgn}(g)|X^g|}{n!}

其中 |X^g| 表示 g 下的不动点。

我们来解释式子：

从后往前看连乘式的每个因子，选 G(x) 表示结束当前循环的考虑，如果 t\neq 0 则新考虑一个循环；选 -t\mathscr E 表示给之前的循环末尾加一个元素（此时剩下 t 个未定的位置，所以系数为 t），同时调整排列的符号。

也就是说，单个 G(x) + 连续极长 \mathscr E 段（假设共 l 个）表示一个循环，它对于不动点的贡献就是 G(x^l)

错了，是 G(x^{l + 1})。

赞叹！

什么，你问我初中二三年级在干什么？

摆！

寄！