第六讲容斥原理及其应用（一）容斥原理是一种计数的方法，它在许多领域广泛的应用。第六和第七讲介绍容斥原理的内容以及它的几个简单的应用。本讲主要包括以下几个内容:1.1引入1.2容斥原理的一般形式1.3容斥原理的推广形式1.4四个例子1.5两个练习1.1引入设集合A是一有限集,我们用｜A｜表示集合A所含有的元素的个数。设S是一个有限集，A1和A2是S的子集，如下图所示。SA1A2类似地，SA1A2A31.2容斥原理的一般形式定理1设S是一有限集，P1,P2,…,Pm是m个性质，令Ai表示S中所有具有性质Pi的元素构成的集合。则S中不具有性质P1,P2,…,Pm的元素的数目为思考：试用数学归纳法证明定理1。下面我们用组合的方法证明定理1。证明只需证明，对S中的任何元素x，它对等式两边的计数的贡献都相同。（贡献是组合数学中常用的一个词。简单的说，若x∈A，则x对｜A｜的贡献为1，否则贡献就为0）现将S中的元素根据其恰好具有性质的个数进行分类，然后我们证明对每类中的任何一元素都证明它对等式两边的计数的贡献都相同。设x不具有性质P1,P2,…,Pm，那么x∉Ai，i＝1，2，…m。则它对等式左边计数的贡献为1，对等式右边的计数的贡献也是1。根据牛顿二项式定理不难得到上面式子的结果是0．而由于x具有n个性质，它对等式左边的贡献也为0，1.3容斥原理的推广形式定理2设S是一有限集，P1,P2,…,Pm是m个性质，令Ai表示S中所有具有性质Pi的元素构成的集合。则S中恰具有r个性质的元素数N(r)为rrw(r)-Cr+1w(r+1)+Cr+2w(r+2)m-rrL+(-1)Cmw(m),这里w(k)=∑N(Pi1,Pi2,…,Pik),其中N(Pi1,Pi2,…,Pik)为S中具有性质Pi1,Pi2,…和Pik的元素的数目。证明:略1.4几个例子例1:求1-1000之间(包括1和1000)不能被5,也不能被6,还不能被8整除的整数有多少个?例2:欧拉函数φ(n):表示小于等于n且与n互素的整数的个数,求φ(n).a1a2…ak解：若n分解成素数的乘积。n=p1p2pk设1到n的n个数中为pi的倍数的集合为Ai,则｜Ai｜=n/pi｜Ai∩Aj｜=n/(pipj),依此类推。由容斥原理得φ(n)=n-(n/p1+n/p2+…+n/pk)+(n/p1p2+n/p1p3+…+kn/pk-1pk)+…+(-1)n/p1p2…pk=n(1-1/p1)(1-1/p2)…(1-1/pk).例3：第二类Stirling数公式。解：我们回忆S(n,m)表示将n个有区别的球放到m个相同的盒子中使得无一空盒的方法数.我们用T(n,m)表示将n个有区别的球放到m个不同的盒子中使得无一空盒的方法数.则T(n,m)=m!S(n,m).现在我们计算T(n,m)。设Pi为第i个盒子为空盒的方法，则由容斥原理容易得到T(n,m)=mn-C(m,1)(m-1)n+C(m,2)(m-2)n-…+(-1)m-1C(m,m-1)1n.例4:某学校有12位教师,已知有8位老师可以教数学,6位可教物理,5位可教化学.其中有5位教师既教数学又教物理.4位老师兼教数学和化学,3位老师兼教物理和化学,3位老师兼教这三门课.1.求不教任何课的老师有几位?2.只教一门课的老师有几位?3.正好教其中两门课的老师有几位?1.5两个练习练习1：求由a,b,c,d构成的n位符号串中，a,b,c,d都至少出现一次的符号串的数目。练习2：求a,b,c,d,e,f六个字母的全排列中不允许出现ace，也不允许出现df图象的排列数。