《组合数学课件-第三章第三节广义的容斥原理.ppt》由会员分享，可在线阅读，更多相关《组合数学课件-第三章第三节广义的容斥原理.ppt（40页珍藏版）》请在三一办公上搜索。
1、1,第3章 容斥原理与鸽巢原理,3.1 De Morgan定理 1 3.2 容斥原理 1 3.3 容斥原理举例 1 3.4 棋盘多项式与有限制的排列 2 3.5 有禁区的排列 2 3.6 广义的容斥原理 2 3.7 广义容斥原理的应用 3 2.8 第二类Stirling数的展开式 1 2.9 欧拉函数(n)1 2.10 n对夫妻问题 3*2.11 Mobius反演定理 2.12 鸽巢原理 4 2.13 鸽巢原理举例 4 2.14 鸽巢原理的推广 4*2.15 Ramsey数,2,3.6 广义的容斥原理,容斥原理解决的问题:,广义的容斥原理解决的问题,3,3.6 广义的容斥原理,求只参加了数学课
2、的人数？只参加了物理课的人数？只参加了化学课的人数？,例3.6.1：一个学校只有数学，物理，化学3门课。学这3门课的学生人数分别是170,130,120；同时学数学、物理两门课的学生有45人；同时学数学、化学的有20人；同时学物理、化学的有22人；同时修三门课的学生有3人，问这个学校共有多少学生?,只参加了数学、物理课的人数？只参加了数学、化学课的人数？,4,单修一门数学，即修数学而不修物理和化学的学生数；可如下表示：,解：设M为修数学课的学生集合；P为修物理课的学生集合；C为修化学课的学生集合，,求只参加了数学课的人数？,3.6 广义的容斥原理,5,关于M互为补集,因此：只参加数学课学习的人
3、数有,3.6 广义的容斥原理,6,只学数学、物理两门课,M,P,C,3.6 广义的容斥原理,*,7,3.6.1 一般公式,假定全集是N,其中有A1,A2,An个子集，定义：当m0时,对于特殊情况m=0时定义:,3.6 广义的容斥原理,8,3.6 广义的容斥原理,定义 是正好存在于m个集合的元素的个数,9,例3.6.2 设N=1,2,3,14,4个集合A1,A2,A3,A4。A1=2,5,8,12,13,；A2=1,3,5,6,7,8,10,12,14；A3=1,4,5,7,12,13；A4=1,4,5,7,12,14。,3.6 广义的容斥原理,10,m=0时,m=1时,m=2时,3.6 广义的
4、容斥原理,m=4时,11,3.6 广义的容斥原理,12,定理3.3.4 广义容斥原理的证明,证明：,aN,设它属于t个集合,分tm三种情况来讨论,(1)若tm,那么a与等式的两端无关。,3.6 广义的容斥原理,13,(2)若t=m,这时a只在左端计算了一次，在右端也只计算一次。,设a只属于A1,A2,Am,3.6 广义的容斥原理,aN,设它属于t个集合,14,(3)若tm,因为左端是正好存在于m个集合的元素，因此左端没有计算a，,在右端的情况分析如下：,3.6 广义的容斥原理,15,设a包含在t个集合中,A1,A2,.,At，tm,3.6 广义的容斥原理,16,3.6 广义的容斥原理,设a包含
5、在t个集合中,A1,A2,.,At，tm,因为左端是正好存在于m个集合的元素，因此左端没有计算a，,右端关于a的计算:,17,3.6 广义的容斥原理,利用公式：,18,中括号各项正好是(1-x)t-m的系数,3.6 广义的容斥原理,如果令x=1,得到：,19,综合以上三种情况：,推论3.1,3.6 广义的容斥原理,aN,设它属于t个集合,分tm三种情况来讨论,20,3.7 广义容斥原理的若干应用,线性方程整数解的问题,的零或正整数解的数目，其中x1,x2,xn是变量，n1,r0,n和r都是正整数。,这个方程的任一非负整数解都可以看做是r个无区别的球放进n个有标志x1,x2,xn的盒子，允许空盒
6、，,21,例3.6.4 求方程x1+x2+x3=15的整数解的数目，要求0 x15,0 x26,0 x37。,如果没有附加条件，即求：x1+x2+x3=15的零或正整数解，即要求：x10，x20，x30。,C(3+15-1,15)=C(17,15)=C(17,2),变为讨论问题x1+x2+x3=15的整数解，求：x16，x27，x38。,3.7 广义容斥原理的若干应用,22,例3.6.4 求方程x1+x2+x3=15的整数解的数目，要求0 x15,0 x26,0 x37。,解:令N为全体非负整数解(x1,x2,x3),A1为其中x16的解；A2为其中x27的解；A3为其中x38的解。,3.7
7、广义容斥原理的若干应用,A1的个数，相当于对（y1+6）+x2+x3=15求非负整数解的个数。,C(3+9-1,9)=C(11,2),y1=x1-60的解；y2=x2-70的解；y3=x3-80的解。,23,A2的个数，相当于对x1+(y2+7)+x3=15求非负整数解的个数。,C(3+8-1,8)=C(10,2),A3的个数，相当于对x1+x2+(y3+8)=15求非负整数解的个数。,C(3+7-1,7)=C(9,2),3.7 广义容斥原理的若干应用,24,性质A1A2的个数，相当于对（y1+6）+(y2+7)+x3=15求非负整数解的个数。,即求y1+y2+x3=2的非负整数解，其解的个数
8、为C(3+2-1,2)=C(4,2),性质A1A3的解的个数，相当于对(y1+6)+x2+(y3+8)=15求非负整数解的个数。,即求y1+x2+y3=1的非负整数解，其解的个数为C(3+1-1,1)=C(3,1),3.7 广义容斥原理的若干应用,25,性质A2A3的个数，相当于对x1+(y2+7)+(y3+8)=15求非负整数解的个数。,即求x1+y2+y3=0的非负整数解，其解的个数为C(3+0-1,0)=C(2,0),3.7 广义容斥原理的若干应用,26,性质A1A2A3的个数，相当于对(y1+6)+(y2+7)+(y3+8)=15求非负整数解的个数。,即求y1+y2+y3=-6的非负整
9、数解，其解的个数0,3.7 广义容斥原理的若干应用,27,例3.6.5 求方程x1+x2+x3=15的整数解的数目，要求3x15,2x26,1x37。,3.7 广义容斥原理的若干应用,作变换0 x1-32,0 x2-24,0 x3-16。,28,O(0,0),P(10,5),例3.6.6：如图所示，1、求从O(0,0)点到P(10,5)点的路径中不通过AB,CD,EF,GH中任何一条路径的路径数。坐标分别为:A(2,2),B(3,2),C(4,2),D(5,2),E(6,2),F(6,3),G(7,2),H(7,3)。2、只通过其中两个的路径数。,路径数问题:,29,O(0,0),P(10,5
10、),解：令A1为从O点到P点过AB边的路径；,令A2为从O点到P点过CD边的路径；,令A3为从O点到P点过EF边的路径；,令A4为从O点到P点过GH边的路径；,路径数问题:,30,路径数问题:,O(0,0),P(10,5),31,如果求正好过上述四条线段中两条的路径数,不通过上述四条线段中任何一条的路径数,路径数问题:,*,32,1、求n对夫妻排成一行，夫妻相邻的排列数。,解：,3.10,n对夫妻问题。,2、求n对夫妻排成一行，夫妻不相邻的排列数。,解：设Ai是第i对夫妻排在一起的排列集。,正好有m对夫妻排在一起的方案数,33,解：设Ai是第i对夫妻排在一起的排列集。,3.10,n对夫妻问题。
11、,34,3.10,n对夫妻问题。,正好有m对夫妻排在一起的方案数,35,3,n对夫妻围一圆桌而坐，夫妻相邻的排列数。,3.10,n对夫妻问题。,4、n对夫妻围一圆桌而坐，夫妻不相邻的方案数？,解：设Ai是第i对夫妻排在一起的排列集。,正好有m对夫妻排在一起的方案数,36,3.10,n对夫妻问题。,37,习 题,3.20 在由a,a,a,b,b,b,c,c,c组成的排列中,求满足下列条件的排列数。(1)不存在相邻三元素相同。(2)相邻两元素不相同,设A是有两个a相邻的排列数。B是有两个b相邻的排列数。C是有两个c相邻的排列数。,解(2)：,38,习 题,设A是两个a相邻的排列数。B是两个b相邻的排列数。C是两个c相邻的排列数。,解：,39,习 题,40,设X是a与aa相邻的排列数。Y是b与bb相邻的排列数。Z是c与cc相邻的排列数。,习 题,*,
