【数学】容斥原理：从计数技巧到数学艺术

type

Post

status

Published

slug

m00

date

Feb 20, 2026 21:35

summary

容斥原理（Inclusion-Exclusion Principle）是组合数学中的核心计数方法，其核心思想是通过"先包含后排除"的方式，精准计算多个集合的并集大小，避免重复或遗漏计数。

容斥原理：从计数技巧到数学艺术

容斥原理（Inclusion-Exclusion Principle）是组合数学中的核心计数方法，其核心思想是通过"先包含后排除"的方式，精准计算多个集合的并集大小，避免重复或遗漏计数。本文将系统介绍其基本形式、推广公式、证明方法、应用场景及经典例题。

📊 一、基本概念与公式

0. 相关概念的介绍

在学习这部分内容之前，首先来介绍一下如下部分的相关符号是什么含义，对于包含有限个元素的集合，我们使用来表示集合中元素的个数，这里的并非是「卡片」的含义，而是的缩写。

而在本文中，我们会使用来表示。

1. 两个集合的容斥原理

对于集合 A 和 B，其并集大小的计算公式为：

直观解释：直接相加会将交集部分重复计算一次，因此需减去。

示例：某班数学满分15人，语文满分12人，两科均满分4人，则至少一科满分的人数为：

2. 三个集合的容斥原理

对于集合 A、B、C，公式为：

原理：减去两两交集时重复扣除了三个集合的交集，因此需加回。

示例：会篮球的15人、羽毛球17人、网球12人，同时会篮球和羽毛球11人、羽毛球和网球7人、篮球和网球9人，三项都会的设为 x。已知至少会一项的有22人，则：

3. n个集合的推广公式

记忆口诀："奇加偶减"——奇数个集合的交集加，偶数个的交集减。

🧠 二、原理证明

1. 容斥原理的证明（元素计数法）

容斥原理是用于计算多个集合的并集大小的方法。它的核心思想是：先加上所有集合的大小，再减去重复计算的部分（即交集），然后加回多减的部分，以此类推。下面我们用"元素计数"的方法来证明它，即证明每个元素在公式两边都被计算了相同的次数。

1.1 两个集合的情况

对于两个集合和，容斥原理公式为：

证明思路： 考虑任意一个元素，它可能属于、，或者都不属于。我们检查在等式左右两边被计算的次数：

如果不在 也不在 ：

左边：中不计入（计数 0 次）。

右边：和都不计入，也不计入（计数 0 次）。

两边相等。

如果只在 中（不在 ）：

左边：计入 1 次。

右边：计入 1 次，计入 0 次，计入 0 次（因为不在交集中）。

右边总计：次。

两边相等。

如果只在 中（不在 ）：

类似地，左边计数 1 次，右边计数次。

两边相等。

如果 同时在 和中：

左边：只计入 1 次（并集不重复计算）。

右边：计入 1 次，计入 1 次，但也计入 1 次（因为在交集中）。

右边总计：次。

两边相等。

结论： 无论属于哪种情况，它在等式两边都被计算了相同的次数。因此，整个并集的大小也相等。

1.2 三个集合的情况

对于三个集合、、，容斥原理公式为：

证明思路： 同样考虑任意元素，分析它属于哪些集合：

如果 不属于任何集合：

左边计数 0 次，右边所有项都不计入（计数 0 次）。

两边相等。

如果 只属于一个集合（例如只属于 ）：

左边计数 1 次。

右边：只有计入 1 次，其他项（交集）都不计入。

右边总计：次。

两边相等。

如果 属于两个集合（例如属于 和 ，但不属于 ）：

左边计数 1 次。

右边：

和各计入 1 次（共 2 次），
计入 1 次（因为在此交集中），
其他交集（如）不计入。

右边总计：次。

两边相等。

如果 属于所有三个集合：

左边计数 1 次。

右边：

、、各计入 1 次（共 3 次），
、、各计入 1 次（共 3 次），
计入 1 次。

右边总计：次。

两边相等。

结论： 对于三个集合，每个元素在两边也被计算了相同的次数。

1.3 推广到 n 个集合

对于 n 个集合，容斥原理公式为：

证明思路： 设任意元素恰好属于个集合（可以是 0 到 n）。

在左边： 如果，则被计算 1 次（因为并集不重复）；如果，则计算 0 次。

在右边：

第一项（单个集合）：被计算次（因为它属于个集合）。

第二项（两两交集）：被计算次（表示从个集合中选出 2 个的组合数，即属于多少个两两交集）。

第三项（三三交集）：被计算次（从个集合中选出 3 个的组合数）。

以此类推，直到最后一项。

因此，右边对的总计算次数为：

我们可以证明这个和等于 1（当时）：考虑二项式展开，即：

移项得：

所以：

两边同时乘以：

因此，右边对的净计数为：

如果，则为 1 次；

如果，则为 0 次。

这与左边完全一致。

最终结论： 每个元素在容斥原理公式的两边都被计算了相同的次数，因此整个公式成立。

2. 容斥原理的数学归纳法证明

数学归纳法是证明数学命题的常用方法，特别适用于证明与自然数相关的命题。下面我们用数学归纳法来证明容斥原理。

2.1 基础情况（n=2）

当时，容斥原理为：

这个公式是已知成立的（前面已经证明过），作为归纳法的基础。

2.2 归纳假设

假设对于个集合，容斥原理成立，即：

2.3 归纳步骤（证明 n=k+1 时成立）

现在考虑个集合。

令，则：

根据基础情况（n=2）：

现在分别分析这三项：

第一项：

根据归纳假设，这等于：

第二项： 就是第个集合的大小。

第三项：

令（其中），则：

根据归纳假设（对 k 个集合）：

注意到：

以此类推，直到

因此：

2.4 合并各项

现在将三部分合并：

代入各项表达式：

来自 的项：

单个集合：

两两交集：

三三交集：

最后：

来自 的项：

单个集合：

来自 的项：

单个交集：

两两交集：

三三交集：

最后：

将所有同类项合并：

单个集合项：

两两交集项：

三三交集项：

最后一项：

这正是时的容斥原理公式！

2.5 结论

由数学归纳法原理，容斥原理对所有自然数都成立。

🧮 三、应用场景

1. 错位排列（Derangement）的证明

错位排列是指每个元素都不在自己原始位置的排列。n 个元素的错位排列数记作 !n（或 D_n），其公式为：

下面我们用容斥原理来证明这个公式。

1.1 问题描述

考虑 n 个元素的排列，设第 i 个元素的原始位置为 i。我们需要计算有多少种排列方式，使得没有任何一个元素留在自己的原始位置上。

定义集合为所有第 i 个元素留在原始位置 i 的排列的集合（即 "坏排列"）。

那么，错位排列的数量就是所有排列数减去至少有一个元素在原始位置的排列数：

1.2 应用容斥原理

根据容斥原理：

现在计算各项：

单个集合 ：

第 i 个元素固定在位置 i，其他 n-1 个元素可以任意排列

共有 n 个这样的集合，所以

两两交集 ：

第 i 和第 j 个元素都固定在各自位置，其他 n-2 个元素任意排列

从 n 个元素中选 2 个，有种选择方式

所以

三三交集 ：

第 i、j、k 个元素都固定在各自位置，其他 n-3 个元素任意排列

从 n 个元素中选 3 个，有种选择方式

所以

以此类推：

对于任意 k 个指定元素固定在各自位置的情况：

从 n 个元素中选 k 个，有种选择方式

所以第 k 项的和为：

最后一项（所有 n 个元素都固定在各自位置）：

符号为

1.3 代入容斥公式

将各项代入容斥原理公式：

因此，错位排列的数量为：

整理得：

1.4 近似公式的说明

当 n 很大时，错位排列数近似为：

这是因为根据的泰勒展开式有：

所以：

误差项的大小为：

当 n ≥ 1 时，这个误差小于 0.5，因此 !n 就是最接近的整数。

5.5 举例验证

以 n=4 为例：

总排列数：4! = 24

错位排列数：!4 = 24 × (1 - 1 + 1/2 - 1/6 + 1/24) = 24 × (9/24) = 9

实际列出所有错位排列（共9种）：

2,1,4,3
2,3,4,1
2,4,1,3
3,1,4,2
3,4,1,2
3,4,2,1
4,1,2,3
4,3,1,2
4,3,2,1

公式计算结果与实际一致！

结论： 通过容斥原理，我们成功推导出了错位排列数的精确公式和近似公式。

示例：4位厨师各做一道菜，每人尝菜但不得尝自己做的菜，方案数为：

2. 数论与互质问题

求 1 到 n 中与 n 互质的数的个数（欧拉函数）：

设 n 的质因子为，则：

示例：求 1 到 10 中与 10 互质的数的个数（即）：

3. 概率论中的容斥

对事件，至少发生一个的概率：

示例：一对夫妇后代头发为黄色或卷发的概率 = 黄发概率 + 卷发概率 - 黄发且卷发概率

4. 实际生活问题

课程选修：某班学生选课程，已知选数学、物理、化学的人数及两两重叠数，求至少选一门课的人数

语言能力统计：调查群体中掌握英语、法语、西班牙语的人数，求仅会一种语言的人数

📐 四、经典例题分析

例题1（两集合）

某班50人，合唱队30人，美术队25人，两队都不参加的有5人。求两队都参加的人数。

解：

至少参加一队的人数都参加的人数

例题2（三集合极值）

某考试数学、语文、英语满分分别20人，数学英语双满8人，数学语文双满7人，语文英语双满9人，三科均满分未知。班级最多46人，最少39人（根据三科满分人数极值推导）。

例题3（整除问题）

求 1 到 300 中能被 3 或 5 或 7 整除的数的个数。

解：

💡 五、常见误区与技巧

避免重复计算：始终检查交集部分是否被正确扣除或加回

极值问题：

并集最大时，交集最小

并集最小时，交集最大

互补转换：当直接计算"满足条件"的集合复杂时，可先计算"不满足条件"的集合，再用总数减去

📚 六、扩展阅读

容斥原理与筛法：在数论中，容斥原理用于埃拉托斯特尼筛法，以计算素数个数或与n互质的数的个数

概率推广：在测度论中，容斥原理可推广到一般测度空间（如概率空间），公式形式相同

现代应用：在计算机科学中，容斥原理用于算法设计（如组合计数、图论）、软件测试（用例设计）等领域

容斥原理的本质是数学的对称美与精确性的体现——通过交替加减，使计数回归均衡。从小学奥数到高等组合数学，其思想一以贯之：在重叠与分离中寻找不重不漏的真理。

附录：容斥原理的推广形式

对任意测度空间（如概率空间），若为可测集，则：