更更炫酷的反演魔术

· · 个人记录

更好的阅读体验

前置知识：这里。

之前在这篇文章里我们给出了一种对反演的很有意思的看法（"第一种视角"），现在我们要扩展它。

这个视角可能会在容斥结构较复杂的情况下有思路上的优势？

回忆错排问题

考虑所有排列的集合 \mathcal P​，对于排列 p，我们直接令它的 GF 为 \prod_{i}[p_i=i]u_i。

定义一个函数 \Gamma​​​ 为选择器，它可以从 \mathcal P​​​ 中筛出我们想要的元素，在本题中我们只需要令 \Gamma:u_*\mapsto 0​​。

然而 \mathcal P​​​ 的 GF 并不好表达。现在考虑一个新集合 \mathcal P^{\star}​​​，它的元素仍是所有排列，但其 GF 为 \prod_i[p_i=i](u_i+1)​​，也即它的不动点可以任意选择"隐藏"或被标记。

$$ P^*=\left[\dfrac{x^n}{n!}\right]\sum_{i=0}^{\infty}x^i\times\sum_{i=0}^{\infty}\dfrac{x^i}{i!} $$ 定义一个函数 $\Xi$​​​​ 为**转换器**，满足 $\Xi\,P=P^{*}$​​​。在本题中，$\Xi:u_*\mapsto(u_*+1)$​​​。 我们所欲求的是 $\Gamma\,P$​​，自然也就是 $\Gamma\,\Xi^{-1}\,P^*$​​。**我们只需要求解 $\Gamma\,\Xi^{-1}$​​​。** 本题中，$\Gamma\,\Xi^{-1}:u\mapsto -1$。这就是子集反演。 ### 回忆斯特林反演 考虑特定集合划分方案 $\{s_i\}$​（一个集合的无序列表），我们直接暴力地令它的 GF 为 $k^{\underline\ell}\prod u_{s_i}$​。（$\ell$​ 表示该列表的长度）（是的你没看错，$u$​ 的指标集是所有 $\{1\sim n\}$​ 的子集）令 $\mathcal L$​​​​ 是所有这样的染色方案的集合。 选择器 $\Gamma$​ 是显然的：$\Gamma:u_s\mapsto[|s|\in S]$​。 下面定义 $\mathcal L^{\star}$​：它的元素仍是所有集合划分方案，但是其 GF 是 $k^{\ell}\prod u_{s_i}$​​​。不难发现 $$ L^*=[z^{\{1\sim n\}}]\exp\left(k\sum_{s}u_sz^s\right) $$ 其中 $z$ 维上遵从子集卷积。 考虑 $\Xi$，可见 $\Xi$ 应当是一个把集合拆散的变换，听起来非常大力，但没有关系！ $$ \Xi:u_s\mapsto[z^{s}]\exp\sum_{t\subseteq s}u_tz^t $$ 于是 $$ \Gamma\,\Xi^{-1}:[z^{s}]\exp\sum_{t\subseteq s}u_tz^t\mapsto [|s|\in S] $$ 似乎并不可做。 下面我们请出容斥中的重要要素：**容斥系数**。具体来说，我们编出一组系数 $w(s)$​，使得 $$ u_s\mapsto w(s) $$ 与 $\Gamma\,\Xi^{-1}$ 等价，这也就找到了一个能合理地计算 $\Gamma\,\Xi^{-1}$​ 的方法。 回到本题，根据对称性，$w$ 应当只与 $|s|$ 有关，于是 $$ \exp\sum_{i=0}^{\infty}\dfrac{w(i)x^i}{i!}=1+\sum_{i\in S}\dfrac{x^i}{i!} $$ 剩下的工作已经很显然了。 ### 回忆二维斯特林反演 只需要考虑集合划分方案对 $(\{s_i\},\{t_i\})$​​​。这次我们连 $\mathcal L$​​ 的哪怕暴力的生成函数表达都很难写出了！然而 $\Xi$​​​（现在定义为在两维上分别拆散）的递推关系却仍存在。 不难发现两维无论是在权值、$\Xi$​ 还是 $\Gamma$​​ 的意义上都独立，于是新容斥系数是两维的容斥系数相乘这点也就十分合理了。 ### [树上斯特林反演](https://www.luogu.com.cn/blog/your-alpha1022/ji-yi-ge-xiao-qiao-di-rong-chi-wen-ti) 只提一句：注意这题中容斥系数不完全由连通块大小决定，而是与连通块形态有关。这一点也不影响问题的解决，具体看原文吧。