容斥原理 | Codeboy's Blog

形式陈述

设 $n\ge1$ ，记 $[n]=\{1,\ldots,n\}$ 。对有限集 $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|.

记 $\mathbf1\{P\}$ 为命题 $P$ 的指示值：成立时取 $1$ ，不成立时取 $0$ 。同一公式可写成逐元素的恒等式：

\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.

这里假定 $r\ge1$ 。由二项式定理， $(1-1)^r=0$ ；把展开式的首项 $1$ 移到另一侧，正得到上面的等式。因此并集内每个元素的最终系数都是 $1$ ，并集外元素从未被计入，系数为 $0$ 。这就完成了有限公式的逐元素证明。

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

从结构上看，容斥是子集格上的 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.

以 $N=12$ 为例，偶数有 $6$ 个， $3$ 的倍数有 $4$ 个； $6,12$ 在两份名单中都出现，所以答案是 $6+4-2=8$ 。最后一项删去的是每个重叠元素多出的那一次记录，并没有把这些合法元素从并集中删除。

错排是每个元素都离开原位的排列。计数时，把不合法事件 $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!}.

例如 $n=3$ 时，得到 $6-3\cdot2+3\cdot1-1=2$ ，恰是单行记号 $231$ 和 $312$ 。式中从 $k=0$ 开始，是因为要从全部 $n!$ 个排列中扣除“至少固定一个位置”的并集；它数的是补集。这个例子显示，关键仍是让交集大小具有可计算结构。

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

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

推论与应用

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

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

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

对于一般禁位排列，强迫若干格子 $(i,j)$ 同时被占用时，交集不再只由选格数决定：共行或共列就为空。车多项式将兼容的选格记录为非攻击车数 $r_k$ ，于是合法数为 $\sum_k(-1)^kr_k(n-k)!$ ；命中数变换进一步恢复“恰违反几条”的分布。这是对交集结构的补充，仍使用本页的有限容斥恒等式。

参考资料

Oscar Levin, Discrete Mathematics: An Open Introduction, 3rd ed., 2019，§1.6 Advanced Counting Using PIE，上界约束与 Counting Derangements。
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.

形式陈述 ​

反向链接

形式陈述