容斥原理和二项式反演

容斥原理 (Principle of Inclusion-Exclusion, PIE)

容斥原理是用来解决“并集计数”问题的核心工具。它的基本思想是：为了求几个集合并集的大小，我们先把所有集合的大小加起来，然后减去被重复计算的（两个集合的交集），再加上被错误减去的（三个集合的交集），再减去…如此往复，一加一减，直到最后。

直观理解

两个集合：
- 解释：中，的部分被计算了两次，所以要减掉一次。
三个集合：
- 解释：
  1. 先加上所有单个集合的大小。
  2. 这时，两两相交的部分被多算了一次，所以全部减掉。
  3. 但这样一来，三个集合共同相交的部分被加了3次（在中），又被减了3次（在中），等于一次都没算。所以最后要把它加回来。

一般形式

假设我们有个性质（或集合）。我们想要求至少满足其中一个性质的元素个数。这等价于求集合的大小，其中是具有性质的元素构成的集合。

公式：

更紧凑的求和形式：

是下标集合的一个非空子集。
是子集的大小（即交集的个数）。
表示子集中所有下标对应的集合的交集。

“一个都不满足”的形式（更常用）

在很多问题中，我们想求的是一个性质都不满足的元素个数。设全集为。那么所求的就是：

代入容斥原理公式得到：

更紧凑的形式：

（约定，即空交集为全集）

经典应用：错排问题 (Derangements)

问题：封信和个对应的信封，将所有信随机装入信封，求每封信都未装入正确信封的方案数。

解法：

全集 U：所有可能的排列，共种。
性质：第封信装入了正确的信封。
集合：满足性质的排列的集合。
目标：求一个性质都不满足的方案数，即。

应用容斥原理：

=
：考虑，即第封信在正确位置。剩下的封信可以任意排列，有种方案。一共有个这样的集合，所以这项是。
：考虑，即第和第封信都在正确位置。剩下的封信任意排列，有种方案。我们从个位置中选2个，有种选法。所以这项是。
通项：个集合的交集大小为。

代入公式：

化简，得到：

这就是著名的错排公式。

二项式反演 (Binomial Inversion)

二项式反演是一种代数工具，它揭示了两个序列之间通过二项式系数建立的一种对偶关系。它常用于解决“恰好”与“至少/至多”之间的转换问题。

公式形式

设有两个序列和。

形式一（“至多”形式）：
如果

那么

形式二（“至少”形式，更常用）：
如果
$为上限$
那么

理解和的含义

这是理解和应用二项式反演的关键。

通常代表“恰好有个元素/满足个性质”的方案数。
通常代表一个与相关、但更容易计算的量。常见的含义是：
- 在形式一中，通常是与“个元素构成的子集”相关的某种总和。
- 在形式二中，通常是“至少有个元素/满足个性质”的方案数。

“至少”的解释：
为什么代表“至少”？
考虑一个有“至少个性质”的方案。假设它恰好有个性质（）。那么这个方案在计算时，会被计算多少次呢？
我们从它拥有的这个性质中，任选个，都满足“至少有n个性质”的条件，所以它被计算了次。
因此，把所有恰好有个性质的方案（种）贡献的次数加起来，就是。

应用：再解错排问题

我们用二项式反演来求。

：恰好有个位置正确的排列数。我们的目标是。
：钦定（指定） 个位置是正确的，其余位置任意排列的方案数。这比“至少”更容易计算。
- 如何计算？从个位置中选个作为正确的位置，有种选法。剩下的个位置任意排列，有种方案。
- 所以，。

建立和的关系：
我们使用“至少”形式的变体。一个“钦定”了个位置正确的方案，可能实际上有更多位置是正确的。
可以证明（这正是二项式反演的威力），它们满足关系：

（这个关系和我们之前推导“至少”的逻辑是一样的）

进行反演：
根据二项式反演公式（形式二），我们有：

求我们的目标：
令，则：

因为，且，代入得：

我们得到了和容斥原理完全相同的结果！

二项式反演的证明

证明所需的核心恒等式

在开始之前，我们需要一个关键的组合恒等式。对于整数：

这里的是艾佛森括号 (Iverson bracket)，表示：

如果，表达式的值为 1。
如果，表达式的值为 0。

证明这个恒等式：

首先，对二项式系数进行展开：
我们可以重新组合这个式子：

这个变换非常有用：先从n个里选k个，再从剩下的n-k个里选i-k个。
将这个结果代入原求和式：
由于与求和变量无关，可以提到前面：
进行换元，令。当时，；当时，。
现在我们来分析这个求和。根据二项式定理：

令 , , ，则：
分析求和结果：
- 如果 (即 )，那么。
- 如果 (即 )，那么。
  （约定在组合数学中是标准做法）
所以，。
代回第4步的式子：
- 如果，值为。
- 如果，值为。
  这正是的定义。

恒等式证毕。现在我们可以用它来证明二项式反演了。

证明形式一

已知：
$式$
求证：
$式$

证明过程：

我们将 (式1) 代入 (式2) 的右边，然后化简，目标是得到。

从 (式2) 的右边开始：
将的定义 (式1) 代入，注意 (式1) 中的求和上限是，变量是：
这是一个双重求和。我们可以交换求和次序。
原始的求和范围是。
交换次序后，我们先对求和，再对求和。的范围是到。对于一个固定的，的范围是到。
将与内层求和变量无关的提出来：
应用核心恒等式，将这个结果代回第4步：

这个求和中，只有当时，才为1，其余项都为0。
所以整个和只剩下这一项：

这就证明了 (式2) 成立。

证明形式二

这个形式在组合计数中更常用。

已知：
$式$
求证：
$式$

证明过程：

同样，我们将 (式3) 代入 (式4) 的右边。

从 (式4) 的右边开始：
将的定义 (式3) 代入。注意 (式3) 的求和变量是，下限是：
交换求和次序。
原始的求和范围是。
交换后，我们先对求和，再对求和。的范围是到。对于一个固定的，的范围是到。
将与内层求和变量无关的提出来：
现在，我们聚焦于括号内的求和。这正是我们最开始证明的核心恒等式！

对照核心恒等式。
这里的对应于，对应于，对应于。
令恒等式中的 , , 。
将这个结果代回第4步：

这个求和中，只有当时，才为1，其余项都为0。
所以整个和只剩下这一项：

这就证明了 (式4) 成立。

总结

容斥原理与二项式反演的关系

它们是解决同一类问题的不同视角：

容斥原理是基于集合论的，通过对集合的交、并进行操作，处理“至少一个”和“一个都无”的问题。它的公式形式本身就带有交替的符号。
二项式反演是基于代数的，它是一个关于序列的恒等式。它将难求的“恰好”问题，转化为易求的“钦定”或“至少”问题，然后通过公式反解。

在很多问题中，容斥原理的每一步计算（例如）都对应着二项式反演中的计算。可以说，二项式反演是容斥原理的一种代数抽象和推广。

特性	容斥原理	二项式反演
基础	集合论	代数学
核心思想	对重复计算的部分进行加减校正	建立“恰好”与“至少/钦定”之间的代数关系，然后反解
解决问题	求并集大小，或“至少一个”/“一个都无”的问题	求“恰好k个”的问题
公式外观	交替加减集合交集的大小	两个序列通过二项式系数和交替符号联系
联系	二项式反演可以看作是容斥原理的代数形式和推广	是容斥原理的代数形式，也是更广义的莫比乌斯反演的特例

掌握这两个工具，并理解它们之间的深层联系，将极大地提升你解决复杂组合计数问题的能力。

推广：莫比乌斯反演 (Möbius Inversion)

二项式反演本身是更广义的莫比乌斯反演在特定偏序集上的一个特例。

莫比乌斯反演是定义在**偏序集（Poset）**上的一个泛用性极强的反演关系。
二项式反演是莫比乌斯反演在**“集合包含关系”**这个偏序集上的体现。
另一个著名的数论莫比乌斯反演，是其在**“整除关系”**这个偏序集上的体现。

理解莫比우스反演可以让你从一个更高的维度俯视这些反演技巧，认识到它们共享着相同的底层数学结构。

Min-Max 容斥 (Min-Max Inclusion-Exclusion)

核心思想：Max 与 Min 的相互转换

Min-Max 容斥提供了一种令人惊奇的能力：将一个集合的最大值 (max)，用该集合所有子集的最小值 (min) 来表示；反之亦然。

这为什么有用？在很多问题中，直接计算一个集合中多个随机变量的最大值的期望 (E[max]) 可能非常困难，因为这些变量往往不是独立的。然而，计算它们最小值的期望 (E[min]) 可能要简单得多。Min-Max 容斥搭起了两者之间的桥梁。

基本公式

设是一个由数值（或随机变量）组成的有限集合。

1. 用 min 表示 max

集合的最大值等于其所有非空子集的最小值的交替和：

展开形式（以3个元素为例）：
对于 :

由于，上式即为：

2. 用 max 表示 min

集合的最小值等于其所有非空子集的最大值的交替和：

展开形式（以3个元素为例）：
对于 :

观察：这两个公式的结构与标准的容斥原理完全一致！

证明过程

我们来证明第一个公式：max(S) = ...。证明的思路是一种经典的组合计数思想：我们不直接证明等式两边相等，而是证明集合中的每一个元素在右侧的式子中被计算的总系数，恰好使得最终结果为 max(S)。

准备工作：
将集合的元素从大到小排序，设为。
那么，。
我们的目标是证明右侧的交替和的结果也等于。
分析贡献：
考虑任意一个元素。我们来计算它在整个式子中的总贡献，也就是它的最终系数。
元素会在哪些项中出现？
当且仅当时，才对这一项的值有贡献。
确定条件：
的充要条件是：
- 必须在子集中。
- 所有比小的元素 () 都不能在子集中。
- 中的其他元素只能从比大的元素 () 中选取。
计算系数：
符合上述条件的子集必须由和一个从（这个集合有个元素）中选出的子集构成。即。
我们枚举的大小，设，其中可以从到。
- 当时，子集的大小为。
- 从个元素中选出个元素构成，有种选法。
- 每一种这样的选法，对应的项是。
所以，的总系数是所有这些情况的系数之和：
应用二项式定理：
这个求和式正是二项式定理的一个特例。
令，我们得到：
分情况讨论：
- 对于 (即不是最大的元素 )：
  ，所以。
  这意味着，除了最大元素之外的所有元素的最终系数都是0！它们对总和没有任何贡献。
- 对于 (即是最大的元素 )：
  ，所以。（在组合数学中，约定）
  这意味着，最大元素的最终系数是 1。
结论：
在整个交替和中，只有的系数是 1，其他所有元素的系数都是 0。所以，整个式子的值就是。
而。
证明完毕。

期望形式 (最强大的应用)

Min-Max 容斥最强大的地方在于它可以直接应用于期望。因为期望具有线性性 ()，我们可以将期望算子直接应用到公式的每一项。

设是一个由随机变量组成的集合。

这个公式是解决一类经典概率问题的杀手锏。

经典应用：优惠券收集问题 (Coupon Collector’s Problem)

问题：假设有种不同的优惠券，每次购买商品会随机获得一种。问集齐所有种优惠券所需购买商品次数的期望是多少？

解法：

定义随机变量：设是获得第种优惠券所需的购买次数。
目标：我们要求的是集齐所有优惠券的次数，这等价于所有中的最大值。即求。
困难点：之间不是独立的，直接求非常困难。
应用 Min-Max 容斥：

其中。
计算子问题 ：
是什么意思？它是指在子集所代表的那些优惠券中，第一次获得其中任意一种所需的购买次数的期望。
设。这意味着我们的目标是获得这种优惠券中的任何一种。
在每次购买时，成功的概率（即抽到这种中的一种）是。
这是一个典型的几何分布问题。对于成功概率为的几何分布，其期望是。
所以，。
代回原式：
注意到的值只取决于子集的大小，而与具体是哪些元素无关。
对于一个固定的（），大小为的子集共有个。
所以，我们可以按子集大小来分组求和：
$其中$

这就是优惠券收集问题的期望值的精确公式。
（这个结果可以进一步化简，恰好等于，即乘以调和级数，但 Min-Max 容斥直接给出了这个交替和形式的解）。

扩展：k-th Min-Max 容斥

Min-Max 容斥还有一个更广义的形式，可以用来求第大（或第小）的元素。

设表示集合中第大的元素。

验证一下：
当时，求最大值（第1大）：
。
这与我们最初的 max 公式完全一致。

同样，这个公式也适用于期望。

总结

核心功能：在 max 和 min 之间建立一个基于容斥原理的代数转换。
结构：与标准容斥原理的公式结构完全相同。
证明：通过分析每个元素在求和式中的总系数来证明，利用了二项式定理。
最强应用：期望形式，特别适用于求解多个非独立随机变量最大值的期望，能将一个困难问题分解为一系列简单的子问题。
推广：存在 k-th Min-Max 形式，可以求解第大/小的值。