容斥原理

容斥原理用交集修正“把各类数量直接相加”时的重复计数。对两个有限集合 $A,B$， $$|A\cup B|=|A|+|B|-|A\cap B|.$$ 交集里的每个元素在前两项被数了两遍，减去一次才回到一遍；只属于其中一个集合的元素始终只数一遍。

一个能逐个核对的例子

在 1 至 30 的整数中，能被 2 整除的有 $\lfloor 30/2\rfloor =15$ 个，能被 3 整除的有 10 个；同时满足两项的正是 6 的倍数，有 5 个。因此能被 2 或 3 整除的共有 $15+10-5=20$ 个。若直接相加得 25，错误恰是把 6、12、18、24、30 各算了两遍。

三类时补回三重交集

对 $A,B,C$，先把三个单集相加，再减去三个两两交集。但一个同时在三类中的元素先被算三次，又被减三次，最后为零，还需补回一次： $$\begin{array}{cc}|A\cup B\cup C|=& |A|+|B|+|C|\\ & -|A\cap B|-|A\cap C|-|B\cap C|\\ & +|A\cap B\cap C|.\end{array}$$ 这种“加单集、减两两、加三重”的交替继续推广到更多集合。使用前要固定全集和统计对象；若同一人可以属于多类，不能把类别计数当作互斥概率直接相加。欧拉函数的乘积公式也可由排除不同素因子的倍数得到。

参考资料

• MIT，Mathematics for Computer Science，Counting 章节。
• MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
• 继续阅读：组合数学、概率、欧拉函数。