组合数学-第二章-容斥原理

1、第二章容斥原理 本章重点介绍容斥原理及其在排列组合中的应用： 容斥原理 容斥原理的应用 有限制排列与棋盘多项式2.1 基本技术定律2.1 容斥原理2.1.1 引论 SA SAB 容斥原理（包含排除原理）通过研究若干有限集合的交与并等基本运算，解决实际中的计数问题。主要依据： 若A为S 的子集，则 ， 。 De Morgan定律：若A、B为S的子集，则 注：De Morgan定律可推广到n个有限子集。2.1 容斥原理定理1-12.1 容斥原理2.1.2 计数定理定理 2.1可用Venn图说明该定理的正确性。或通过组合分析法，若A代表具有性质a的元素集合，B代表具有性质b的元素集合，等式左端表示至

2、少具有性质a、b之一的元素个数，|A|表示具有性质a的元素个数，|B|表示具有性质b的元素个数，但二者相加时，同时具有性质a、b的元素计数重复加了一次，故需要减去重复的数|AB|。注：加法法则相当于该等式AB=的一个特例。2.1 容斥原理定理1-22.1 容斥原理2.1.2 计数定理定理 2.1同样可用Venn图说明该定理的正确性。该等式表示同时不具有性质a、b的元素个数的计数方法。同时不具有性质a、b的元素个数应该在全集S中去掉|A|和|B|，但此时同时具有性质a、b的元素计数重复减了一次，故需要加上重复的数|AB|。2.1 容斥原理定理22.1 容斥原理2.1.2 计数定理定理 2.22.

3、1 容斥原理例12.1 容斥原理2.1.2 计数定理例 题例1、一个学校只有三门课程：数学、物理、化学。已知修这三门科的学生分别有170、130、120人；同时修数学物理两门课的学生有45人；同时修数学、化学的20人；同时修物理、化学的22人；同时修三门科的学生3人。问这学校有多少学生？解：令M为修数学课的学生集合，P为修物理课的学生集合，C为修化学课的学生集合。据题意有|M|=170，|P|=120，|C|=130，|MP|=45，|PC|=22，|CM|=20，|MPC|=3 ， 则该学校的学生数为|MPC|=|M|+|P|+|C|-|MP|-|PC|-|CM|+|MPC|=3362.1

4、容斥原理定理32.1 容斥原理2.1.3 容斥原理定理 2.3若Ai (i=1,2,n) S，且Ai是S中具有性质pi的元素的子集，则S中不具有性质pi (i=1,2,n)的元素的个数为：证明：可以利用数学归纳法证明。或用组合分析方法如下：为证明等式成立，只需证明等式右端不具有性质pi (i=1,2,n)的元素被计算的次数净值为1，而至少具有性质pi 中之一的元素被计算的次数净值为0即可。考虑S中一个不具有n个性质中任何一个性质的元素x，因为xAi(i=1,2,n)，故x被计算的次数净值为1-0+0-(-1)n *0=1。考虑S中一个恰好具有n个性质中的m(1mn)个性质的一个元素y，由于yS

5、 ，故在S中被计算的次数为C(m,0)；又由于y恰好具有m个性质，故它是Ai(i=1,2,n)中的m个集合的元素，因而在 中被计算的次数为C(m,1) ；又因为在m个性质中取出一对性质的方法有C(m,2)个，故y是C(m,2)个集合AiAj(ij)的一个元素，在 中被计算的次数为C(m,2)，因此y在等式右端被计算的次数净值C(m,0)-C(m,1)+C(m,2)+(-1)nC(m,n)，由于mk时，C(m,k)=0，有C(m,0)-C(m,1)+C(m,2)+(-1)nC(m,n)= C(m,0)-C(m,1)+C(m,2)+(-1)mC(m,m)=0。因此y具有n个性质中至少一个性质时，被

6、计算的次数净值为0。 定理得证。2.1 容斥原理定理42.1 容斥原理2.1.3 容斥原理定理 2.4若Ai (i=1,2,n) S，且Ai是S中具有性质pi的元素的子集，则S中至少具有性质pi (i=1,2,n)的一个性质的元素个数为：证明：由于集合 是S中至少具有n个性质中一个性质元素所组成的子集，所以有代入上述定理，即可得证。2.1 容斥原理例22.1 容斥原理2.1.3 容斥原理例 题例2、求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图像的排列数。解：令S为这六个字母的全排列集合，A为ace作为一个元素出现的排列集合，B为df作为一个元素出现的排列集合。根据题意有|

7、S|=6!，|A|=4!，|B|=5!，|AB|=3!，根据容斥原理，不允许出现ace和df的排列数为2.1 容斥原理例32.1 容斥原理2.1.3 容斥原理例 题例3、求从1到500的整数中被3或5除尽的数的个数。解：令A为1500中能被3除尽的整数集合，B为1500中能被5除尽的整数集合。根据题意有根据容斥原理，从1到500的整数中被3或5除尽的数的个数为2.1 容斥原理例42.1 容斥原理2.1.3 容斥原理例 题例4、求有a,b,c,d四个字符构成的n位符号串中，a,b,c至少出现一次的符号串的数目。解：令S为四个字符的所有n位符号串集合，A,B,C分别为n位符号串中不出现a,b,c的

8、集合。根据题意有根据容斥原理， a,b,c至少出现一次的符号串数目为2.1 容斥原理例52.1 容斥原理2.1.3 容斥原理例 题例5、求不超过120的素数个数。解：设S=1,2,120，因为102120112，故120以内的合数必然是2,3,5,7的倍数，令Ai为120以内数i的倍数集，i=2,3,5,7，有根据容斥原理，有但该计算过程排除了素数2,3,5,7，又包含1这个非合数，故所求120以内的素数数目为27+4-1=302.1 容斥原理例62.1 容斥原理2.1.3 容斥原理例 题例6、用26个英文字母做不允许重复的全排列，要求排除dog, god, gum, depth, thing

9、字样的出现，求满足这些条件的排列数。解：设S为26个字母的全排列集，令Ai分别为出现dog, god, gum,depth, thing的排列集，i=1,2,3,4,5。出现dog的排列，可把dog作为一个元素看，|A1|=24!，同理|A2|=|A3|=24!，|A4|=|A5|= 22!。因dog, god不可能同时出现，故|A1A2|=0，同理|A2A3|=|A1A4|= |A1A5|= 0，gum, dog可以在dogum中同时出现，故|A3A1|=22!，同理|A2A4|=|A3A4|=|A5A2|=|A5A3|=20!, |A4A5|=19!。同理|A1A2A3|=|A1A2A4|

10、=|A1A2A5| =|A2A3A4|=|A2A3A5|=|A1A4A5|=|A1A3A4|=|A1A3A5|=|A2A4A5|= 0，|A3A4A5|=17!，其他4个、5个子集的交集均为空集。根据容斥原理，所求的排列数为26!-324!-22!+420!+19!-17!2.1 容斥原理例72.1 容斥原理2.1.3 容斥原理例 题例7、欧拉函数(n)是求小于n且与n互素的自然数的个数。 (nN)求欧拉函数表达式。解：对任一大于1的正整数n都可惟一地分解为其中p1p2pk都是不超过n的素数，且1,2,k都是正整数。设S=1,2, n， Ai为S中能被pk整除的子集，i=1,2,k。显然有|S

11、|=n, |Ai|=n/pi, (i=1,2,k), |AiAj|=n/(pi pj), (i,j=1,2,k; ij),|A1A2 Ak|=n/(p1p2pk)，根据容斥原理，有2.1 容斥原理例82.1 容斥原理2.1.3 容斥原理例 题例8、某校甲班共有学生60名，其中24个学生喜爱数学，28个学生喜爱物理，26个学生喜爱化学，10个学生既喜爱数学又喜爱物理，8个学生既喜爱数学又喜爱化学，14个学生既喜爱物理又喜爱化学，6个学生对这三门学科都喜爱，问有多少学生对这三门学科都不喜爱？解：设S为60名学生的集合，令M为喜欢数学课的学生集合，P为喜欢物理课的学生集合，C为喜欢化学课的学生集合。

12、根据题意有|S|=60，|M|=24，|P|=28，|C|=26，|MP|=10，|PC|=14， |CM|=8， |MPC |=6 ，根据容斥原理，则该班级三门学科都不喜欢的学生数为|S|-(|M|+|P|+|C|)+(|MP|+|PC|+|CM|)-|MPC |=82.1 容斥原理例92.1 容斥原理2.1.3 容斥原理例 题例9、求从1到1000的整数中不能被5，6和8中任何一个整除的整数个数。解：用lcma1,a2,an表示n个整数a1,a2,an的最小公倍数。设S=1,2,1000，令A,B,C分别为11000中能被5,6,8除尽的整数集合。显然，其补集代表不具备被整除性质的集合。根据题意有根据容斥原理，不能被5,6,8中任何一个数整除的数目为2.1 容斥原理例102.1 容斥原理2.1.3 容斥原理例 题例10、把n本不同的书放入m个有编号的箱子中去（nm)，使得没有一个箱子为空。共有多少种方法？解：设S表示n本不同的书任意放入m个有编号的箱子里的所有方法的集合，显然|S|=mn 。令pi(i=1,2,m)表示箱子i为空这一性质，Ai(i=1,2,m)表示S中具有性质pi的元素组成的集