从容斥到二项式反演

2008verser · 2025-04-27 22:36:42 · 算法·理论

几个月前连滚带爬发明了一遍二项式反演。本文不打算从二项式反演的式子出发去证明它的正确性，而是用组合意义推出该式。

网上实在难找相关的博客，因此想给入不去门的同学介绍一下。场上忘记结论了甚至可以手推一遍。

容斥和二项式反演。我看来前者是后者的边界。

一种实用性的容斥的定义简化如下：设满足条件 P_i 的对象集合为 A_i，对象全集 U。

则一个条件都不满足（恰满足 0 个）的对象个数为 |U|-\sum |A_i|+\sum|A_i\cap A_j|-\sum|A_i\cap A_j\cap A_k|+\ldots。

若要求“恰满足 k 个条件”的对象个数，从容斥的组合意义出发，得到的式子就是所谓的二项式反演。

这一段回顾一下容斥的组合意义。

众所周知，上面容斥式子之所以正确，是因为考察每个对象在式子里出现几次，每次出现是 +1 还是 -1。

我们按对象实际满足了几个条件分类。

比如一个对象实际满足了 w 个条件，考虑它在式子里出现：

这 w 个条件的每个子集都出现。对于奇数大小的子集，它每出现就 -1，偶数的就 +1。

奇数大小的子集贡献了 -{w\choose 1}-{w\choose 3}-\ldots。算上偶数的，一共就是 {w\choose 0}-{w\choose 1}+{w\choose 2}-{w\choose 3}+\ldots=0。

若这个对象实际满足的条件数量 w 为 0，式子等于 1。

总之，实际满足至少一个条件的对象对式子贡献总和是 0。一个都不满足的贡献是 1。

容斥还可以这样感受，是全拿->拿多了减掉->减多了加上->加多了减掉……

刚才我们对每个对象考虑其对式子的贡献总和。接下来配合上面的感受，我们继续沿用这个方法。

我说“满足 k 个条件的对象个数”就是上面式子有 k 个 A 的那个和式的结果。

注意，这句话不等同于“实际满足 k 个条件的对象个数”，也不等同于“实际满足至少 k 个条件的对象个数”。不要忘记。

为了方便，记 g(k) 表示“满足 k 个条件的对象个数”，而 f(k) 表示恰好，即要求的。

现在要用 g(k) 表示出 f(k)。

一个实际满足了 w 个条件的对象，在 g(k) 里出现了 w\choose k 次，对吧。

先全拿，即 g(k)。对于实际满足了 k 个条件的对象，恰好出现一次（好了接下来做剔除就容易多了），实际满足 w\gt k 个的对象，出现了 w\choose k 次。

实际 w=k+1 的对象，其出现 {k+1\choose k}=k 次。我们不要它，于是减去 kg(k+1)。虽然 g(k+1) 包含了实际满足 k+1 的对象各一个，但是还有别的呢，减多了。

实际 w=k+2 的对象，其在刚才出现 {k+2\choose k}-k{k+2\choose k+1}={k+2\choose 2}-k{k+2\choose 1} 次。真丑。

这个时候打住想要归纳的念头，我们换种方法，不去乘那个 k：

硬着头皮写出 g(k)-g(k+1)+g(k+2)-g(k+3)+\ldots 这样子的鬼东西。考虑每个对象在这个式子中出现了几次，然后修补。

实际 w=k 的对象依旧稳定发挥出现 1 次。

实际 w=k+1 的对象出现 {k+1\choose k}-{k+1\choose k+1} 次。

实际 w=k+2 的对象出现 {k+2\choose k}-{k+2\choose k+1}+{k+2\choose k+2} 次。

……

实际 w\gt k 的对象出现 {w\choose k}-{w\choose k+1}+{w\choose k+2}-{w\choose k+3}+\ldots 次。

出现次数变成了一行组合数的一个后缀的交错求和。

现在我们能做的事情是朝写出的式子的 g 前面添加系数。它会同时添加到下面这些组合数上。

目的就是让这些带上系数的组合数求和为 0。你考虑这样子：

让 w\choose k+i 带上 k+i\choose k。这样它就变成了 {w\choose k}\times{w-k\choose i}。不难想到把 w\choose k 提出去，剩下的就是 w-k 整行的组合数正负求和等于 0。

把系数写回 g 就得到了：