《组合数学课件--第三章第三节广义的容斥原理.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
4、时,m=2时,3.6 广义的容斥原理,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.
5、6 广义的容斥原理,设a包含在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
6、,x2,xn的盒子，允许空盒，,21,例3.6.4 求方程x1+x2+x3=15的整数解的数目， 要求0x15,0x26,0x37。,如果没有附加条件，即求： 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的整数解的数目， 要求0x15,0x26,0x37。,解:令N为全体非负整数解(x1,x2,x3), A1为其中x16的解； A2为其中x27的解；
7、A3为其中x38的解。,3.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求非负整数解的个数。,即求
8、y1+y2+x3=2的非负整数解，其解的个数为 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
9、求非负整数解的个数。,即求y1+y2+y3=-6的非负整数解，其解的个数0,3.7 广义容斥原理的若干应用,27,例3.6.5 求方程x1+x2+x3=15的整数解的数目， 要求3x15,2x26,1x37。,3.7 广义容斥原理的若干应用,作变换 0x1-32,0x2-24,0x3-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、只通过其中
10、两个的路径数。,路径数问题:,29,O(0,0),P(10,5),解：令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,解：
11、设Ai是第i对夫妻排在一起的排列集。,3.10,n对夫妻问题。,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相邻的排列数。,习 题,*,