容斥原理 | Codeboy's Blog

形式陈述

对有限集合 $A_1,\ldots,A_n$ ，它们的并与交按集合运算理解，容斥原理给出

\left|\bigcup_{i=1}^nA_i\right| = \sum_{\varnothing\ne I\subseteq[n]} (-1)^{|I|+1} \left|\bigcap_{i\in I}A_i\right|.

展开后，先加所有单集合大小，再减所有二重交，加回所有三重交，符号依交集阶数交替。对三个集合，公式是

|A\cup B\cup C| = |A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C|.

同一公式可写成指示函数恒等式。对每个元素 $x$ ，

\mathbf1\!\left\{x\in\bigcup_iA_i\right\} = \sum_{\varnothing\ne I\subseteq[n]} (-1)^{|I|+1} \mathbf1\!\left\{x\in\bigcap_{i\in I}A_i\right\}.

对所有 $x$ 求和便得到基数版本。

直觉

直接相加 $|A_i|$ 时，一个同时属于 $r$ 个集合的元素会被计数 $r$ 次。二重交把它减去 $\binom r2$ 次，三重交再加回 $\binom r3$ 次，最终总系数为

\binom{r}{1}-\binom{r}{2}+\binom{r}{3}- \cdots+(-1)^{r+1}\binom{r}{r}=1.

交替符号因此不是记忆口诀，而是逐层修正过度计数。每增加一阶交集，都是在补偿上一层把多重重叠修正过头的部分。

从结构上看，容斥是子集格上的 Möbius 反演。集合交对应选择一组同时满足的条件，并集计数则询问至少满足一个条件；Möbius 函数 $(-1)^{|I|}$ 在两种描述之间转换。

例子与边界

要计数 $1,2,\ldots,N$ 中能被 $2$ 或 $3$ 整除的整数，令 $A_2,A_3$ 分别表示两类。则

|A_2\cup A_3| = \left\lfloor\frac N2\right\rfloor + \left\lfloor\frac N3\right\rfloor - \left\lfloor\frac N6\right\rfloor.

最后一项不是额外技巧，而是在删去同时被 $2$ 与 $3$ 整除、因而被前两项重复计数的整数。

错排计数把事件 $A_i$ 定义为“排列固定位置 $i$ ”。交集 $\bigcap_{i\in I}A_i$ 固定 $|I|$ 个位置，剩余元素可任意排列，因此大小是 $(n-|I|)!$ 。容斥得到

!n = \sum_{k=0}^n (-1)^k\binom nk(n-k)! = n!\sum_{k=0}^n\frac{(-1)^k}{k!}.

这个例子显示，关键仍是让交集大小具有可计算结构。

只截断到某一阶时，得到 Bonferroni 不等式：奇数阶截断给上界，偶数阶截断给下界。对大量事件，完整公式含 $2^n-1$ 项，计算成本可能超过直接方法；容斥是一条精确恒等式，不保证总是高效算法。

无限事件族不能直接把有限公式无条件取极限。需要绝对收敛、单调极限或其他可交换求和条件。无限集合的基数运算也不能照搬有限交替和，因为 $\infty-\infty$ 没有确定含义。

推论与应用

把基数换成概率并对指示函数取期望，就得到有限事件的概率容斥公式。它可精确展开联合失败概率，也可通过前几项获得并集概率的上下界；union bound 正是只保留第一层所得的上界。

筛法、Euler 函数、禁止模式计数和图上覆盖问题都使用同一框架。对象先按“违反了哪些条件”分类，再通过交集计数恢复“没有违反任何条件”或“至少违反一个条件”的数量。

在算法设计中，子集动态规划与快速 zeta/Möbius 变换可以批量计算所有交集或子集和，使某些指数级容斥从 $3^n$ 降到 $n2^n$ 。这里的加速来自复用子集格结构，而不是改变容斥恒等式本身。

参考资料

Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd ed., Cambridge University Press, 2011, Section 2.1.
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994, Section 8.1.
Martin Aigner, A Course in Enumeration, Springer, 2007, inclusion–exclusion and Möbius inversion.