离散数学：容斥原理与抽屉原理

容斥原理：对有限集合A和B，有|A∪B|=|A|+|B|-|A∩B|.

对n个集合A1，A2，…，An有：|A1∪A2∪…∪An|=∑i|Ai|-∑i＜j|Ai∩Aj|+∑i＜j＜k|Ai∩Aj∩Ak|-…+（-1）n-1|A1∩A2∩…∩An|.

抽屉原理：（1）把多于n个元素的集合S分成n个不相交的子集S1，S2，…，Sn的并集，那么至少存在一个集合Si，它包含至少两个S的元素.

（2）把多于mn个元素的集合S分成n个不相交的子集S1，S2，…，Sn的并集，那么至少存在一个集合Si，它包含S中至少m+1个元素.

乘法原理：如事件E1的发生有n1种方式，事件E2的发生有n2种方式，事件Em的发生有nm种方式，则E1，E2，…，Em发生的方式有n1×n2×…×nm种.

加法原理：若S1，S2，…，Sm是两两不相交的集合，则|S1∪S2∪…∪Sm|=|S1|+|S2|+…+|Sm|.

重点

集合运算的性质.

难点

集合等式的证明：一是利用集合相等的定义A⊆B，B⊆A；二是利用已知的集合恒等式，即等价取代的方法，对A利用有关的集合恒等式，得到B；或证明A=C且B=C，从而A=B.

例题解析

例3.1　求幂集P（Ø）、P（｛Ø｝）、P（｛Ø，｛Ø｝｝）、P（｛1，｛2，3｝｝）.

【分析】特别要注意Ø与｛Ø｝的区别，Ø是不含任何元素的集合，是任意集合的子集，而｛Ø｝是含有一个元素Ø的集合.

解：

P（Ø）=｛Ø｝

P（｛Ø｝）=｛Ø，｛Ø｝｝

P（｛Ø，｛Ø｝｝）=｛Ø，｛Ø｝，｛｛Ø｝｝，｛Ø，｛Ø｝｝｝

P（｛1，｛2，3｝｝）=｛Ø，｛1｝，｛｛2，3｝｝，｛1，｛2，3｝｝｝

例3.2　设U=｛1，2，3，4，5，6，7，8，9｝，A=｛1，2，3，5，6，7，9｝，B=｛2，4，6，8｝，C=｛1，3，5，7，9｝.计算A-B，A∪C，B⊕C（B与C的对称差），A∪（B∩C），（A∪B）C，A∩BC.

【分析】正确理解集合运算的定义.

解：

A-B=｛1，3，5，7，9｝

A∪C=｛1，2，3，5，6，7，9｝

B⊕C=｛1，2，3，4，5，6，7，8，9｝(www.xing528.com)

A∪（B∩C）=｛1，2，3，5，6，7，9｝

（A∪B）C=｛｝

A∩BC=｛1，3，5，7，9｝

例3.3　证明A-（B∩C）=（A-B）∪（A-C）.

【分析】要证明两个集合相等，可以用如下几种方法：A=B⇔A⊆B∧B⊆A；利用集合运算的基本等式和已经得到证明的等式.而证明一个集合是另一个集合的子集，即A⊆B也有几种方法：A⊆B⇔对∀x∈A，有x∈B；A⊆B⇔A∈P（B）；A⊆B⇔A-B=Ø⇔A∪B=B⇔A∩B=A.

证明：

方法一

A-（B∩C）=A∩（B∩C）C=A∩（BC∪CC）=（A∩BC）∪（A∩CC）=（A-B）∪（A-C）

方法二

对于∀x，x∈（A-（B∩C））⇔x∈A∧x∉（B∩C）

⇔x∈A∧（x∉B∨x∉C）⇔（x∈A∧x∉B）∨（x∈A∧x∉C）

⇔x∈（A-B）∨x∈（A-C）⇔x∈（A-B）∪（A-C）

所以A-（B∩C）=（A-B）∪（A-C）

例3.4　在6个人中，或者有3个人，他们中的每两个人都相互认识；或者有3个人，他们中的每两个人都彼此不相识.（对6个顶点的完全图的边用红、蓝二色任意着色，结果至少有一个边都同色的三角形）

【分析】为了用好鸽巢原理，关键存于搞清问题中的什么东西分别作为鸽巢和鸽子.

解：

从6个人任意选定一个人记为a，记F为其余5人中与a相互认识的人的集合，S为其余5人中与a相互不认识的人的集合.则由鸽巢原理可知，|S|或|F|＞2.

若|F|＞2，如果F中有两人相互认识，则他们和a一起满足结论要求.如果F中的人相互不认识，则结论得证.

而若|S|＞2，如果S中的人相互认识，则结论得证.否则F中若有两人相互不认识，则他们和a一起也满足结论要求.

例3.5　一个班有50个学生，在第一次考试中及格的有26人，在第二次考试中及格的有21人，如果两次考试中没有及格的有17人，那么两次考试都及格的有多少人？

解：

设A和B分别表示在第一次和第二次考试中及格的学生的集合.则|A|=26，|B|=21，|（A∪B）c|=17.而|（A∪B）c|=50-|A∪B|=50-（|A|+|B|-|A∩B|），从而|A∩B|=17-50+|A|+|B|=17-50+26+21=14.

所以，两次考试都及格的有14人.