更炫酷的反演魔术

· · 个人记录

本文介绍了两种可能有益的对容斥的看法：一种本质上是在生成函数的层面进行运算而不是容斥系数；另一种则在常规的容斥系数的视角上更近一步，顺带提出了“反演的笛卡尔积”等结果。

我得先说好，这博客里的所有内容差不多都是民科x义x的臆想，如有更好的看法欢迎指出。

容斥是什么

显然它指的已经不是子集反演了……事实上，容斥的定义在 OI 圈是有些混乱的。

以后我们再给出本文讨论的容斥的具体定义。

第一种视角

例子：错排问题

考虑所有置换构成的组合类 \mathcal P。构造 \mathcal Q 是这样的一个组合类，其中元素都是置换，而我们还可以标记一些不动点。也就是说，同一个置换但是一个不动点标不标记是两个在 \mathcal Q 中的对象。\mathcal Q 是容易计数的：标记的点必须守序（标号为 1,2,3,...，毕竟它们是不动点）而其他点不必，从而有

\mathcal Q=\text{SET}(\mathcal Z)\star\mathcal P

我们在 GF 中用一个新的变元 u 指出 \mathcal Q 中元素的标记点的数量：

Q(u,z)=\dfrac{e^{uz}}{1-z}

我们还是用 u 指出 \mathcal P 中不动点的数量，显然 \mathcal P 中的不动点（一个 u 的贡献）都可以选择标记和不被标记，即贡献 u 或贡献 1。从而通过这个 u\to u+1 立即得到

Q(u,z)=P(u+1,z) P(0,z)=\dfrac{e^{-z}}{1-z}

问题得到解决。事实上我们可以直接扩展到一般的二项式反演。

这种看待容斥的方法的确非常优美，可惜它不是很好扩展（悲）

例子：莫比乌斯反演

我们有

f_n=\sum_{d|n}g_d

则 g=?

首先明确，一个整数可以看成它的质因子分解序列，比如 12=(2,1,0,0...) 我们把整个序列作为它的大小函数。单个元素的 GF 就是 x_1^{e_1}x_2^{e_2}...，比如 T(12;x_1,x_2,...)=x_1^2x_2。容易验证这个 GF 在“笛卡尔积”下积性。则我们有

\mathcal F=\mathbb N\times\mathcal G

考虑 \mathbb N 的 GF，它当然是 \prod_{i=1}^{\infty}\dfrac{1}{1-x_i}。那么我们甚至不需要构造新的 \mathcal Q（事实上 \mathcal F 就是我们想要的 \mathcal Q）就直接可以得到 G=F\prod_{i=1}^{\infty}(1-x_i)。而后面那个东西则是我们熟知的莫比乌斯函数。

其实我们只是重新发明了狄利克雷生成函数而已……

初探更高级的容斥

例子：斯特林反演

这是一个清新的一维问题。

现有一排 n 个格子，每个格子皆可涂成 k 种颜色之一。

给定集合 S，定义一个染色合法当且仅当：对于任意格子，记和它颜色相同的格子有 x 个（包括自身），必有 x\in S。

求有多少合法的染色方案。

哦，这不是思博题吗！记 F=\sum_{i\in S}x^i，那么

ans=\left[\dfrac{x^n}{n!}\right](1+F)^k

当然，的确是这样。但还有如下的另外一种思路：

考虑所有 1\sim n 的划分：划分是一串集合的无序列表 L=\{S_1,...,S_{\ell}\}，其中的集合两两不交且并恰为 \{1,...,n\}。

我们希望有一组奥妙重重的贴在所有划分上的容斥系数 c，它满足如下性质：

我们指出，上面的条件已经直接地把 \hat c 的取值可能性缩小到了最多一种。具体来说，取 k=1，则显然 ans=[n\in S\lor n=0]。又注意到根据划分和集合是无序列表的关系，那么直接有

\sum_Lc(L)=\left[\dfrac{x^n}{n!}\right]\text{exp}\left(\sum_i\hat c(i)\dfrac{x^i}{i!}\right)

于是，

\sum_{i}\hat c(i)\dfrac{x^i}{i!}=\ln(1+F)

然后我们只需要指出这组 \hat c 真的是满足第一个条件的。有

\text{exp}(k\ln(1+F))=ans=(1+F)^k

这就得证了。所以说，上面的容斥系数的确是正确的。不过它也只是正确而已，这个问题太容易用别的方法得出解，于是难以看出其优越性。它的优越性得等到下一个问题。

注意到 ans 还可表示为

\sum_{L}k^{|L|}\prod_{i=1}^{|L|}\hat c(S_i)=ans=\sum_{L}k^{\underline{|L|}}\prod_{i=1}^{|L|}[|S_i|\in S]

取 S=\{1\}，我们就证明了斯特林反演。

反演的精确定义，也即第二种视角

现在有一个集合 X，其上有一个偏序关系 \le（如果可能引起歧义，则记为 \le_X）。我们有两个函数 f,g:X\rightarrow\mathbb R，这两个函数 f,g 有某种关系，具体来说：

g(x)=\sum_{y\le x}f(y)

我们当然可以用 g 表示 f，这就是所谓的反演。

f(x)=\sum_{y}c(x,y)g(y)=\sum_{y}c(x,y)\sum_{z\le y}f(z)

于是其实我们真正要找的关系式，不妨称为这个容斥的核心（我自己瞎取的）就是：

\boxed{[z=x]=\sum_{y\ge z}c(x,y)}

对于子集反演，X 就是所有 \{1...n\} 的子集，偏序关系就是包含关系，核心则是经典的

\boxed{[T=S]=\sum_{T\le R\le S}(-1)^{|S|-|R|}}

二项式反演是子集反演的特殊情形；莫比乌斯反演是子集反演的一个小扩展。min-max 容斥只是玩了一点小数字花样，这里把它开除容斥籍。

“斯特林反演”的结构就完全不同了，此处 X 变为所有 \{1...n\} 的划分，而偏序关系变为“前者是否可以通过若干次合并操作变为后者”。

从组合意义出发，我们其实显然有

k^{|x|}=\sum_{y{\color{red}\ge}x}k^{\underline{|y|}}

它的核心比较不同，我们没法提取出特定的 T=S，而是可以判定 L 是否满足“某个性质”，这个性质必须能对它的各个集合分别判定最后再 \land 起来。具体地，在“斯特林反演”中

\boxed{\prod_{i}[S_i\in S]=\sum_{L'\le L}\prod_{i}\hat c(|S'_i|)}

上式的正确性也很好理解，首先各个 S_i 可独立考虑，然后根据 \hat c 的 \ln 定义就立刻得知了。

例子：U 群把妹王

这是一个恐怖的二维问题。

现有 n\times m 个格子，每个格子皆可涂成 k 种颜色之一。

给定集合 S,T，定义一个染色合法当且仅当：

  • 对于任意一行，记和它图案相同的行有 x 个（包括自身），必有 x\in S。
  • 对于任意一列，记和它图案相同的列有 x 个（包括自身），必有 x\in T。

求有多少合法的染色方案。

$$ ans=\sum_{L_1}\sum_{L_2}c(L_1)d(L_2)k^{|L_1||L_2|} $$ 这回我们根本无法用另一种方法数出 $ans$，之前的证明方法自然完蛋了。下面我们引入反演的笛卡尔积（还是我自己瞎取的名字）。 考虑两个分别定义在 $X,Y$ 上的反演，定义它们的笛卡尔积是一个在 $X\times Y$ 上的反演。它们的核心分别为 $$ \boxed{check(x)=\sum_{x'\ge x}c(x')}$$ $$ \boxed{check(y)=\sum_{y'\ge y}c(y')} $$ - 其偏序关系定义为：$(x_1,y_1)\le_{X\times Y}(x_2,y_2)$ 当且仅当 $x_1\le_Xx_2\land y_1\le_Yy_2$。 - 定义 $check((x,y))=check(x)\land check(y)=check(x)\cdot check(y)$。 - 显然，其核心为 - $$ \boxed{check((x,y))=\sum_{x'\ge x,y'\ge y}c(x')c(y')} $$ 于是就直接得到了原式的正确性。