再谈容斥

Authored : 𝒫

这不是一份讲稿，只是初步思考的记录。非常，非常不成熟，不具备任何参考价值与研究价值，仅作备忘使用。

H：开始吧。

N：好，我们今天要谈的是另一种容斥的理解。

H：从哪里开始？

N：你能试着回忆一下经典容斥吗？

H：好，让我想想，经典容斥是说这样一个事情：假设我们有一个全集 \(U\)，又有一个大小为 \(n\) 的性质集合 \(P\)。

H：我们希望统计出至少具有一个 \(P\) 中的性质的元素数量。假如用 \(S_i\) 表示拥有第 \(i\) 个性质的元素集合，我们就是希望计算：

\[ \left\lvert\bigcup_{i=1}^{n}S_i\right\rvert \]

H：经典容斥给出的做法是，我们先计算 \(\sum_{i=1}^{n}|S_i|\)，然后发现具有至少两个性质的元素被算重了，减去 \(\sum_{i<j}|S_i\cap S_j|\)，然后发现具有至少三个性质的元素又多减了，再加回去……我们凭直觉列出这样一个式子：

\[ \sum_{m=1}^{n}(-1)^{m-1}\qty(\sum_{T\subseteq P,|T|=m}\left\lvert\bigcap_{x\in T}S_x\right\rvert) \]

H：最后，对每个元素施用二项式定理，我们会发现，所有至少有一个性质的元素，会被恰好被统计一次，而一个都没有的完全不参与上面的运算，所以上式就等于我们要求的值。

N：在讨论这些和式的时候，我们总是从性质的角度去讨论，即考虑具有性质 \(i\) 的元素集 \(S_i\)。你能从元素的角度给出一些初步的想法吗？

H：从元素的角度观察……我们需要统计具有至少一个性质的元素，呃，我们给 \(U\) 一个到 \(\{0,1\}\) 的映射 \(\varphi\)，假设 \(x\) 具有至少一个性质，那么 \(\varphi(x)=1\)，否则 \(\varphi(x)=0\)。这样，\(\sum_{x\in U}\varphi(x)\) 就是我们要的答案了……这看起来没什么用啊。

N：用补集转化，变为统计一个性质都不具有的元素个数呢？

H：那就是说，若 \(x\) 不具有任何的性质，则 \(\varphi(x)=1\)，否则 \(\varphi(x)=0\)，让我想想……也就是说输入 \(0\) 会得到 \(1\)，输入其它所有正整数都会得到 \(0\)……啊！我知道了，令 \(\psi(x)\) 表示 \(x\) 具有的性质个数，那么我们有 \(\varphi(x)=(1-1)^{\psi(x)}\)！

H：然后我们用二项式定理展开这个式子，再交换求和号，因为，当 \(i>\psi(x)\) 时，\(\binom{\psi(x)}{i}=0\)，我们立即得到下面的结果

\[ \begin{aligned} \sum_{x\in U}(1-1)^{\psi(x)}&=\sum_{x\in U}\sum_{i=0}^{\psi(x)}(-1)^i\binom{\psi(x)}{i}\\ &=\sum_{i=0}^{n}(-1)^i\sum_{x\in U}\binom{\psi(x)}{i} \end{aligned} \]

N：你能回顾一些经典的容斥计数，并用这个方法解决吗？

H：最经典的容斥计数……那当然非错排莫属，让我来试试。那么，这里的 \(U\) 就是全部排列 \(p\) 组成的集合，而 \(\psi(p)\) 就是排列 \(p\) 的不动点个数。

H：看起来我们需要先固定住内层的 \(\psi(p)\)，那我们就枚举不动点的个数 \(k\)，然后计算不动点个数为 \(k\) 的排列……不对，这太困难了。

N：我们需要另寻他路，观察我们的和式，我们是在枚举了 \(i\) 之后，对所有排列 \(p\) 计算 \(\binom{\psi(p)}{i}\) 之和。

H：嗯……那我们就先从 \(i\) 下手吧。让我想想，这个式子就是说，对于每个排列 \(p\)，我们求出在它的 \(\psi(p)\) 个不动点中选择 \(i\) 个的方案数。反过来，我们考虑钦定 \(i\) 个点作为不动点，考虑有多少种排列会计算到它，这当然就是 \((n-i)!\)。所以，后半部分的求和就是 \(\binom{n}{i}(n-i)!\)。这样一来，就得到了最终的结果。可这看起来比起传统方法甚至更难了。

H：啊，我懂了，在计算后面的部分的时候，我们总是可以再交换一次求和，先去枚举这 \(i\) 个性质，再计算具有它们的结构个数……我们得到了下面这条式子，又回到了传统的视角。

\[ \sum_{x\in U}\binom{\psi(x)}{i}=\qty(\sum_{T\subseteq P,|T|=i}\left\lvert\bigcap_{x\in T}S_x\right\rvert) \]

N：不要心急！形式的变化有时候也能给我们新的视角。想一想，我们在什么样的地方见过二项式系数？

H：既要有二项式系数，又要和容斥相关……我想最经典的例子无非是二项式反演。让我回忆一下它的其中一个形式：

假设恰好具有 \(n\) 条性质的组合结构数是 \(g(n)\)，而 \(f(n)\) 为先钦定 \(n\) 条性质，再计算所有具有这 \(n\) 条性质的结构个数，最后把所有钦定方法得到的结构个数加起来。

H：啊！这也就是说：

\[ f(n)=\qty(\sum_{T\subseteq P,|T|=n}\left\lvert\bigcap_{x\in T}S_x\right\rvert)=\sum_{x\in U}\binom{\psi(x)}{n} \]

H：现在回到二项式反演，根据算两次原理，我们有：

\[ f(n)=\sum_{i=n}^{m}\binom{i}{n}g(i) \]

这是因为，每个 \(g(i)\) 都在 \(\binom{i}{n}\) 中钦定 \(n\) 条属性的方法中被计算了一次。

N：反演的部分呢？你能从我们上面的理论，导出用 \(f(n)\) 算 \(g(n)\) 的方法吗？

H：让我来试试，我们把待证明的式子列出来：

\[ g(n)=\sum_{i=n}^{m}(-1)^{i-n}\binom{i}{n}f(i) \]

H：根据我们上面的想法，我们计算所有 \(\psi(x)\ge n\) 的 \(x\) 的 \((1-1)^{\psi(x)-n}\) 之和……

\[ \begin{aligned} g(n)&=\sum_{\psi(x)\ge n,x\in U}(1-1)^{\psi(x)-n}\\ &=\sum_{\psi(x)\ge n,x\in U}\sum_{i=0}^{\psi(x)-n}(-1)^i\binom{\psi(x)-n}{i} \end{aligned} \]

H：想一想，我要怎么才能凑出上面的形式呢……有了，我令 \(i\leftarrow i+n\)。

\[ g(n)=\sum_{\psi(x)\ge n,x\in U}\sum_{i=n}^{\psi(x)}(-1)^{i-n}\binom{\psi(x)-n}{i-n} \]

N：我们要找到一条含有 \(\displaystyle \binom{a-c}{b-c}\) 的组合恒等式，看起来 \(\displaystyle \binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c}\) 正是我们要的。

H：那就是说

\[ \begin{aligned} g(n)&=\sum_{\psi(x)\ge n,x\in U}\sum_{i=n}^{\psi(x)}(-1)^{i-n}\dfrac{\binom{\psi(x)}{i}\binom{i}{n}}{\binom{\psi(x)}{n}}\\ &=\sum_{i=n}^{m}(-1)^{i-n}\binom{i}{n}\sum_{x\in U}\dfrac{\binom{\psi(x)}{i}}{\binom{\psi(x)}{n}} \end{aligned} \]

H：不对，我算错了吗？这不是我们想要的形式，让我想想……

N：我明白你的疑惑。我们注意到这个式子只和 \(x\) 与常量 \(n\) 有关。让我们回到最开始的式子，并把它改成

\[ g(n)=\sum_{\psi(x)\ge n,x\in U}\binom{\psi(x)}{n}(1-1)^{\psi(x)-n} \]

N：注意到当 \(\psi(x)=n\) 时，\(\binom{\psi(x)}{n}=1\)，而 \(\psi(x)\neq n\) 时，\((1-1)^{\psi(x)-n}=0\)，所以这条式子和原来是相等的，现在，你再试试？

H：我来计算一下……这条东西是常量，不参与运算。所以前面的推导不变，我们快进到

\[ \begin{aligned} g(n)&=\sum_{\psi(x)\ge n,x\in U}\binom{\psi(x)}{n}\sum_{i=n}^{\psi(x)}(-1)^{i-n}\dfrac{\binom{\psi(x)}{i}\binom{i}{n}}{\binom{\psi(x)}{n}}\\ &=\sum_{i=n}^{m}(-1)^{i-n}\binom{i}{n}\sum_{x\in U}\dfrac{\binom{\psi(x)}{i}}{\binom{\psi(x)}{n}}\cdot \binom{\psi(x)}{n}\\ &=\sum_{i=n}^{m}(-1)^{i-n}\binom{i}{n}f(i) \end{aligned} \]

H：啊！它刚好消掉了那个多余的分母，两条不同的式子却是同一个结果，这是为什么？

N：原因正是我们上面说的：\(\psi(x)\neq n\) 时，\((1-1)^{\psi(x)-n}=0\)。我们把和式按 \(\psi(x)\) 分类，每一类提出来一个 \(\binom{\psi(x)}{n}\)，除了 \(\psi(x)=n\) 的那一类，求和的结果都是 \(0\)。

H：真是神奇！这就代表我们总能给 \(\displaystyle \sum_{x\in U,\psi(x)\ge k}(1-1)^{\psi(x)-k}\) 的求和中乘上一个只与常量和 \(x\) 相关，且 \(\psi(x)=k\) 时取到 \(1\) 的函数，以便计算。

N：很好，你可以证明另一个方向上的二项式反演吗？