第七十讲 容斥原理讲义-2026年高中数学竞赛

第七十讲 容斥原理

1. 容斥原理的几种形式

利用加法原理进行分类计数时,我们将集合 划分成互不相交的若干个子集 , 。如果 允许相交,则无法应用加法原理,此时可以应用容斥原理。

例如若 ,则

若 ,则

一般形式的容斥原理如下。

容斥原理 设 是有限集。则

证明 记 ,显然 是有限集。对任意 ,及 , 定义

从而有 。记 。要证明的等式左边为

等式右边为

只需证明,对每个 ,有

假设 属于 中 个集合,不妨设 属于 ,不属于 ,这里 。则 当且仅当 。 从而

假设 都是某个有限集 的子集,我们有补集形式的容斥原理。

容斥原理补集形式 设 都是有限集 的子集,则有

上面的补集形式又称为筛法公式,或逐步淘汰原理,这里通常 是具有坏性质 (不需要)的元素集合,通过筛去 的元素而得到所需要的元素个数。

利用集合运算的德 - 摩根定律,如果令 ,则上面的补集形式还可以写成交集形式。

容斥原理交集形式 设 都是有限集合,则有

例 1 (Bonferroni 不等式) 设 是有限集合。则对奇数 ,有

对偶数 ,有

证明 我们沿用容斥原理证明中的记号, ,

只需证明对每个 ,有

设 恰属于 中 个集合, ,则

更一般的容斥原理可以用测度空间来叙述。

容斥原理测度空间形式 设 是一个测度空间, 是 的有限测度的可测子集,则

如果取 是二维欧氏空间, 是通常的面积, 是一些区域,那么上面的容斥原理计算了 的面积。不难将容斥原理的补集形式、 交集形式以及 Bonferroni 不等式都照搬到测度空间上来。