元素个数与容斥原理

在计数时，为了使重叠部分不被重复计算，我们采取一种新的计数方式，基本想法是：先不考虑重叠情况，把所有包含在其中的部分的元素个数全部计算出来，再把重复计算的数目排除出去，使得计算的结果不重不漏，这种计数方法称为容斥原理．比如，为了统计某班语文成绩或数学成绩在$100$分以上的学生人数，我们可以先计算所有语文成绩在$100$分以上的，再计算所有数学成绩在$100$分以上的，重复计算的部分是语文与数学成绩都在$100$分以上的，所以减去这部分的学生人数就可以得到结果．

---

我们用$|A|$表示有限集合$A$的元素个数．

两个集合的容斥原理可以表示为

$$|A\cup B|=|A|+|B|-|A\cap B|,$$ 三个集合的容斥原理可以表示为 $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|,$$ $n$个集合的容斥原理可以表示为 $$|A_1\cup A_2\cup\cdots\cup A_n|=\sum_{i=1}^n{|A_i|}-\sum_{1\leqslant i<j\leqslant n}|A_i\cap A_j|+\sum_{1\leqslant i<j<k\leqslant n}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap A_2\cap \cdots\cap A_n|.$$

---

例题一　(1)对某班$50$名同学的爱好进行调查，其中喜欢运动和喜欢看电影的人数分别为$31$人和$40$人，两项都不喜欢的有$4$人，那么既喜欢运动又喜欢看电影的人数是_____．

(2)某高校对一些学生进行问卷，在接收调查的学生中，准备参加注册会计师考试的有$63$人，准备参加英语六级考试的有$89$人，准备参加计算机考试的有$47$人，三种考试都准备参加的有$24$人，准备选择两种考试参加的有$46$人，不参加其中任何一种考试的有$15$人，则接受调查的学生共有_____人．

分析与解　(1)设集合$A$是喜欢运动的人，集合$B$是喜欢看电影的人．则$|A|=31,|B|=40,$要求$|A\cap B|$的值．由题意知$|A\cup B|=50-4=46$，由容斥原理知

$$|A\cap B|=|A|+|B|-|A\cup B|=25.$$
(2)设准备参加注册会计师、英语六级、计数机考试的人依次构成集合$A,B,C$，则有 $$\begin{split} &|A|=63,|B|=89,|C|=47,\\&|A\cap B\cap C|=24.\end{split}$$ 关键是搞清楚选择两种考试参加的人的集合是什么？是下图的阴影部分：于是知 $$|A\cap B|+|B\cap C|+|C\cap A|=46+24\times 3=118,$$ 由容斥原理知 $$|A\cup B\cup C|=63+89+47-118+24=105,$$ 所以接受调查的学生共有$105+15=120$人．

注　我们也可以根据韦恩图设出各部分的人数，再列方程求解此题．

---

例题二　$1,2,\cdots,200$中不能被$2,3,5$整除的数的个数．

分析与解　设$1,2,\cdots,200$中能被$2,3,5$整除的数依次构成集合$A,B,C$．则

$$\begin{split} &A=\{2,4,\cdots,200\},|A|=100;\\&B=\{3,6,9,\cdots,198\},|B|=66;\\&C=\{5,10,\cdots,200\},|C|=40.\end{split}$$ 所求值为$200-|A\cup B\cup C|$．集合$A\cap B$表示可以同时被$2,3$整除的数，即可以被$6$整除的数，故 $$A\cap B=\{6,12,\cdots,198\},|A\cap B|=33.$$ 同理可求出 $$|A\cap C|=20,|B\cap C|=13,|A\cap B\cap C|=6.$$ 由容斥原理知 $$|A\cup B\cup C|=100+66+40-33-20-13+6=146.$$ 所以所求的数的个数为$200-146=54$．

注　事实上，$1,2,3,\cdots,n$中能被$m(m\in\mathcal{N}^*)$整除的数的个数为$\left[\dfrac nm\right ]$，其中$[x]$表示不超过$x$的最大整数，称为高斯函数或取整函数，如$[2.1]=2,[1,9]=1$．

---

最后给出两道练习：

练习一　某外语学校有英语、法语、日语教师共$27$人，其中只能教英语的有$8$人，只能教日语的有$6$人，能教英、日语的有$5$人，能教法、日语的有$3$人，能教英、法语的有$4$人，三种都能教的有$2$人，则只能教法语的有_____人．

答案　$5$．

练习二　$1,2,\cdots,100$中不能被$3,7$整除的数的个数．

答案　$57$．