组合数学-第九节：容斥原理

《组合数学-第九节：容斥原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.2容斥原理将3.1节讨论的原理进一步推广，总结成一般性规律，就得到定理3.2.1所描述的容斥原理。定理3.2.1设S是有限集合，是同集合S有关的m个性质，设是S中具有性质的元素构成的集合，是S中不具有性质的元素构成的集合，则S中不具有性质的元素个数为（3.2.1）证明可以利用等式（3.1.1），通过对m作归纳进行证明。下面通过其组合意义来证明。等式（3.2.1）的左端表示的是S中不具有性质的元素的个数。下面我们来证明：对于S中每个元素，若不具有性质，则对等式（3.2.1）的右端贡献1；否则，若x具有某个性质，则对等式（3.2.1）的右端贡献0，从而证（3.2.1）式。任给，则（1

2、）若x不具有性质，即，则x在集合S中，但不在（3.2.1）式右端的任一其他集合中。所以，x对（3.2.1）式右端的贡献为（2）若x恰具有中的个性质，则x对的贡献为因x恰具有n个性质，所以x恰属于集合，共n个。于是，x对的贡献为从中选出两个性质，共有种，所以x恰在个形如的集合中，x对的贡献为；……；同理，x对的贡献为。而当时，。所以x对（3.2.1）式右端的贡献为综上所述，（3.2.1）式的右端是集合S中不具有性质的元素的个数。证毕。若，则（3.2.1）式变成上面等式的右端共有项。若，则（3.2.1）式变成例2求由四个字符构成的n位符号串中，至少出现一次的符号串的数目。解设分别为不出现

3、的n位符号串的集合。由于n位符号串的每一位都可取四个符号中的任一个，所以共有个。其中，不出现的符号串的每一位都可取中的任一个，共有个。类似地，有而至少出现一次的符号串集合即为，于是例3欧拉函数表示小于n且与n互素的整数的个数。求。解将n分解成素因子的乘积形式：设为不大于n且为的倍数的自然数的集合，则：因与互素，所以与的最小公倍数为，所以……。小于n并与n互素的自然数是集合中那些不属任何一个集合的数，由容斥原理知上面的和式正好是下列乘积的展开式：欧拉函数常用于数论中。例如，若，则小于12并与12互素的正整数为1，5，7和11例4若图G有n个顶点，且不含有完全k子图，则它的顶点的次数满足

4、不等式（3.2.3）其中，X为图G的顶点集。证明设若不等式（3.2.3）不成立，则对任意的，均有。在图G中任取一个顶点，用和相应的集合，由容斥原理得到这是因为集合和中的每一个至少包含个元素，而中至多只有n个元素（G中全部顶点）。再任取一个顶点，同上，由容斥原理可得等等。这样，我们可由归纳法得到对于，取G中与相邻的顶点集，有因此，至少有一个顶点。由的定义知之间相互相邻，所以顶点集合构成的导出子图是图G的完全k子图，这与题设矛盾。故不等式（3.2.3）成立。利用定理3.2.1和推论3.2.1，我们可以算出S中不具有性质的元素个数和S中具有中某个性质的元素个数。下面我们将其推广到更一般的情

5、形。设S是一有限集合，是S上的性质集合。现在的问题是要求出集合S中恰好具有P中r个性质的元素个数。现用表示S中具有性质的元素个数，规定，令若S中某元素x恰好具有P中个性质，则从中取出k个性质的方法数为，因而x在中计算了次。而对于SK具有P中少于k个性质的元素，则不计算在内。例如，在本节的例1中，有于是在中，对具有3个性质的元素，在和中各计算了一次，共3次。例如，120能被5，6，8整除，所以，，即120在中共计算了3次。定理3.2.2设集合S中具有性质集合恰好r个性质的元素个数为，则（3.2.4）证明设x是集合S的一个元素，则（1）若x具有少于r个性质，则x对的贡献均为0，从而对（3

6、.2.4）式右端的贡献为0。（2）若x恰好具有r个性质，则x对的贡献为1，而对的贡献均为0，从而对（3.2.4）式右端的贡献为1。（3）若x恰好具有个性质，则它对的贡献为，对的贡献为对的贡献为；当时，它对的贡献为0。从而，它对（3.2.4）式右端的贡献为综上所述，（3.2.4）式的右端是S中恰好具有r个性质的元素个数。在例1中，有它是S中不能被5，6，8整除的整数个数，这正是容斥原理所反映的事实。它是S中只能被5，6，8之一整除的整数个数。它是S中只能被5，6，8中的两个整数的整数个数。由此可见了，定理3.2.2是定理3.2.1的推广。例5某学校有12位教师，已知教数学课的教师有8位

7、，教物理课的教师有6位，教化学课的教师有5位。其中，有5位教师既教数学又教物理，有4位教师兼教数学和化学，兼教物理和化学的有3位教师，还有3位教师兼教这三门课。试问：（1）教数、理、化以外的课的教师有几位？（2）只教数、理、化中一门课的教师有几位？（3）正好教数、理、化中两门课的教师有几位？解令12位教师中教数学课的教师属于集合，教物理课的教师属于集合，教化学的教师属于集合，则有（1）不教数学、物理、化学课的教师数目为（2）只教数、理、化中一门课的教师数目