Inclusion-Exclusion Principle and Its Applications | 容斥原理及其应用

📚 Inclusion-Exclusion Principle and Its Applications | 容斥原理及其应用

The Inclusion-Exclusion Principle is a fundamental counting technique in combinatorics. It allows us to calculate the size of the union of multiple sets by adding the sizes of individual sets, subtracting the sizes of pairwise intersections, adding back the sizes of triple intersections, and so on. This alternating process ensures that every element is counted exactly once.

容斥原理是组合数学中一种基本的计数技巧。它通过先加上各集合的大小，再减去两两交集的大小，然后加回三个集合交集的大小，如此交替进行，来计算多个集合并集的大小。这个交替过程确保每个元素恰好被计数一次。

1. Two Sets: The Starting Point | 两个集合：起点

For two finite sets A and B, the number of elements in their union is given by:

对于两个有限集合 A 和 B，它们并集的元素个数为：

|A ∪ B| = |A| + |B| − |A ∩ B|

We add the sizes of both sets, then subtract the intersection, because elements in both A and B were counted twice. This simple formula is the foundation of the whole principle.

我们将两个集合的大小相加，然后减去交集的大小，因为同时属于 A 和 B 的元素被重复计算了两次。这个简单的公式是整个原理的基础。

2. Three Sets: The Classic Formula | 三个集合：经典公式

For three sets A, B, and C, the formula extends naturally:

对于三个集合 A、B 和 C，公式自然扩展为：

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

The pairwise intersections are subtracted because they have been overcounted. However, elements in the triple intersection were subtracted too many times, so we add it back once. This pattern of alternating signs continues for larger numbers of sets.

两两交集被减去，因为它们被过度计数了。然而，属于三个集合交集的元素被减去的次数过多，所以我们需要加回一次。这种正负交替的模式会随着集合数量的增加而继续。

3. General Form: The Inclusion-Exclusion Formula | 一般形式：容斥公式

For n sets A₁, A₂, …, Aₙ, the general principle states:

对于 n 个集合 A₁, A₂, …, Aₙ，一般原理表述为：

|∪ᵢ₌₁ⁿ Aᵢ| = Σ |Aᵢ| − Σ |Aᵢ ∩ Aⱼ| + Σ |Aᵢ ∩ Aⱼ ∩ Aₖ| − … + (−1)ⁿ⁺¹ |A₁ ∩ A₂ ∩ … ∩ Aₙ|

Here the first sum is over all i, the second over all pairs i < j, the third over all triples i < j < k, and so on. The sign alternates: positive for odd-sized intersections and negative for even-sized intersections. This formula works for any finite number of sets.

这里第一个和号对所有 i 求和，第二个和号对所有满足 i < j 的二元组求和，第三个和号对所有满足 i < j < k 的三元组求和，依此类推。符号交替出现：奇数大小交集取正号，偶数大小交集取负号。该公式适用于任意有限数量的集合。

4. Intuition: Why Does It Work? | 直觉：为什么有效？

A Venn diagram provides a vivid illustration. For three overlapping circles, each region is initially included/excluded several times. The alternating sum ensures that an element belonging to exactly k sets is counted exactly once, because:

文氏图提供了直观的说明。对于三个重叠的圆，每个区域最初被多次包含或排除。交替求和确保恰好属于 k 个集合的元素被恰好计数一次，因为：

C(k,1) − C(k,2) + C(k,3) − … + (−1)ᵏ⁺¹ C(k,k) = 1

This binomial identity confirms that no matter how many sets an element belongs to, the inclusion-exclusion sum balances perfectly. The “inclusion” adds broad groups, while “exclusion” removes the overcounted overlaps.

这个二项式恒等式确认了无论一个元素属于多少个集合，容斥求和都能完美平衡。”包含”加入大组，”排除”移除被过度计数的重叠部分。

5. Application: Counting Students in Extracurricular Activities | 应用：统计课外活动学生数

A typical exam problem: In a class of 50 students, 25 play football, 20 play basketball, and 15 play both sports. How many students play at least one sport? Using the two-set formula:

一个典型的考试题目：某班有 50 名学生，25 人踢足球，20 人打篮球，15 人两者都参加。至少参加一项运动的学生有多少人？使用两集合公式：

|F ∪ B| = 25 + 20 − 15 = 30

Thus 30 students play at least one sport. The remaining 20 students participate in neither. This type of problem appears frequently in A-level statistics and probability sections.

因此有 30 名学生至少参加一项运动。其余 20 名学生两项都不参加。这类问题在 A-level 统计与概率部分经常出现。

6. Application: Euler’s Totient Function | 应用：欧拉函数

The principle also appears in number theory. Euler’s totient function φ(n) counts the positive integers up to n that are relatively prime to n. For example, to find φ(30), we first factor 30 = 2 × 3 × 5, then use inclusion-exclusion on the sets of multiples of 2, 3, and 5.

容斥原理也出现在数论中。欧拉函数 φ(n) 计算小于等于 n 且与 n 互质的正整数个数。例如，求 φ(30)，先将 30 分解质因数得 30 = 2 × 3 × 5，然后对 2、3、5 的倍数集合使用容斥原理。

φ(30) = 30 − (15 + 10 + 6) + (5 + 3 + 2) − 1 = 8

The integers relatively prime to 30 among 1 to 30 are 1, 7, 11, 13, 17, 19, 23, 29, exactly 8. This method generalizes to any n using its distinct prime factors.

1 到 30 中与 30 互质的整数为 1, 7, 11, 13, 17, 19, 23, 29，正好 8 个。该方法可通过 n 的不同质因数推广到任意 n。

7. Application: Derangements | 应用：错排问题

A derangement is a permutation where no element appears in its original position. The number of derangements of n items, denoted !n, can be computed by inclusion-exclusion. Let Aᵢ be the set of permutations where item i is fixed. Then the number of permutations with at least one fixed point is |A₁ ∪ A₂ ∪ … ∪ Aₙ|, and the derangements are the complement.

错排是指没有任何元素停留在其原始位置的排列。n 个元素的错排数记为 !n，可通过容斥原理计算。设 Aᵢ 为第 i 个元素固定不变的排列集合。那么至少有一个固定点的排列数为 |A₁ ∪ A₂ ∪ … ∪ Aₙ|，错排就是其补集。

!n = n! − C(n,1)(n−1)! + C(n,2)(n−2)! − … + (−1)ⁿ C(n,n)0!

Simplifying, !n = n! × Σᵢ₌₀ⁿ (−1)ᵢ / i!. For n = 4, !4 = 24 − 12 + 4 − 1 = 9. This elegant result is a classic application of the alternating sum nature of inclusion-exclusion.

化简得 !n = n! × Σᵢ₌₀ⁿ (−1)ᵢ / i!。对于 n = 4，!4 = 24 − 12 + 4 − 1 = 9。这个优雅的结果是容斥原理交替求和特性的经典应用。

8. Application: Probability of Union Events | 应用：并事件的概率

In probability, the inclusion-exclusion principle translates directly to probabilities. For events A and B:

在概率论中，容斥原理直接转化为概率表达式。对于事件 A 和 B：

P(A ∪ B) = P(A) + P(B) − P(A ∩ B)

For three events, the formula becomes:

对于三个事件，公式变为：

P(A ∪ B ∪ C) = P(A) + P(B) + P(C) − P(A∩B) − P(A∩C) − P(B∩C) + P(A∩B∩C)

This is especially useful when the events are not mutually exclusive. For independent events, intersections are simply products of probabilities, making the calculation straightforward.

当事件并非互斥时，这一公式尤其有用。对于独立事件，交集概率就是各概率的乘积，计算因而变得直接简单。

9. Common Mistakes and Pitfalls | 常见错误与陷阱

One common mistake is forgetting to add back the triple intersection when using the three-set formula. Another is misidentifying what the sets represent, especially in word problems. Always check that every element is counted exactly once by testing a small case.

一个常见错误是在使用三集合公式时忘记加回三重交集。另一个错误是在文字题中误判集合所代表的对象。应通过一个小例子来检验每个元素是否恰好被计数一次。

Also, when applying to real-life data, be cautious about categories that overlap in complicated ways. Drawing a Venn diagram and labeling each region with its count can prevent errors. Remember that the complement of a union is the intersection of complements, which is often easier to compute.

另外，将原理应用于现实数据时，要警惕以复杂方式重叠的类别。画出文氏图并标注每个区域的数目可以防止错误。记住：并集的补集等于补集的交集，后者通常更容易计算。

10. Summary and Exam Tips | 总结与考试建议

The inclusion-exclusion principle is a powerful tool for counting unions, complements, and constrained arrangements. Master the two-set and three-set formulas first, then learn to generalise. In exams, define the sets clearly, decide which intersections are known, and apply the alternating sum without skipping terms.

容斥原理是处理并集、补集及有约束排列计数的强大工具。首先掌握两集合和三集合公式，然后学会推广。考试中要清晰定义集合，判断哪些交集已知，并不要跳过任何项地应用交替求和。

Practice with problems involving Venn diagrams, prime factor counting, derangements, and probability. A systematic approach will help you avoid overcounting and undercounting, and ultimately earn full marks on these questions.

多练习涉及文氏图、质因数计数、错排和概率的问题。系统化方法能帮助你避免重复计数或漏计，从而在这些题目上获得满分。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Inclusion-Exclusion Principle and Its Applications | 容斥原理及其应用