一道 / edao.plus
计数#容斥原理

容斥原理

两圈相交要减重合；三圈相交要“加单、减双、加三”。

直观场景

把两个兴趣小组的花名册贴在墙上，一个人同时在两边就被数了两次——要让他只数一次，就得减去重合部分。Venn 图让这个重合看得见。

两圆相交处被数了两次，必须减去一次。

推导思路

  1. 1两集合：|A ∪ B| = |A| + |B| − |A ∩ B|。
  2. 2三集合：|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|。
  3. 3一般地：单项相加、双交相减、三交相加……奇加偶减。

公式 / 要点

  • · “至少参加一项” = 单项和 − 两两交集 + 三交集。
  • · “都不参加” = 总人数 − 至少参加一项。

典型例题

1两圈容斥
全班 42 人，参加数学组 28 人，参加英语组 22 人，两组都参加的 15 人。两组都不参加的几人？
  1. 至少参加一项 = 28 + 22 − 15 = 35。
  2. 都不参加 = 42 − 35 = 7。
2三圈容斥
100 名学生，喜欢语文 50，数学 45，英语 40；语数都喜欢 20，数英都喜欢 15，语英都喜欢 10，三科都喜欢 5。一科都不喜欢的几人？
  1. 至少喜欢一科 = 50 + 45 + 40 − 20 − 15 − 10 + 5 = 95。
  2. 都不喜欢 = 100 − 95 = 5。

小结：三圈时，每个交集出现的符号就是 Venn 图里被盖了几层的修正。

常见误区

  • 注意“既 A 又 B”和“只 A 不 B”的区别，后者等于 |A| − |A ∩ B|。
  • 三交集在题目里常被漏掉，要主动检查是否有“三者同时”这种条件。

用到「容斥原理」的题目

#10066 多重限制排列·甲不排头乙不排尾
计数六年级
#10067 装信错排·欧拉问题
杂题六年级

相关知识点

奇偶性