元素个数与容斥原理

在计数时,为了使重叠部分不被重复计算,我们采取一种新的计数方式,基本想法是:先不考虑重叠情况,把所有包含在其中的部分的元素个数全部计算出来,再把重复计算的数目排除出去,使得计算的结果不重不漏,这种计数方法称为容斥原理.比如,为了统计某班语文成绩或数学成绩在$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$人,则接受调查的学生共有_____人.

cover

分析与解 (1)设集合$A$是喜欢运动的人,集合$B$是喜欢看电影的人.则$|A|=31,|B|=40,$要求$|A\cap B|$的值.屏幕快照 2016-07-01 上午9.04.10由题意知$|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} $$关键是搞清楚选择两种考试参加的人的集合是什么?是下图的阴影部分:屏幕快照 2016-07-01 上午9.21.43于是知$$|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$.

此条目发表在方法技巧分类目录,贴了标签。将固定链接加入收藏夹。

发表评论