组合数学课件-第三章第三节广义的容斥原理.ppt

1、1第第3章章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.1 De Morgan 3.1 De Morgan定理定理 1 1 3.2 3.2 容斥原理容斥原理 1 1 3.3 3.3 容斥原理举例容斥原理举例 1 1 3.4 3.4 棋盘多项式与有限制的排列棋盘多项式与有限制的排列 2 2 3.5 3.5 有禁区的排列有禁区的排列 2 2 3.6 3.6 广义的容斥原理广义的容斥原理 2 2 3.7 3.7 广义容斥原理的应用广义容斥原理的应用 3 3 2.8 2.8 第二类第二类StirlingStirling数的展开式数的展开式 1 1 2.9 2.9 欧拉函数欧拉函数(n)1(n)1 2.

2、10 n2.10 n对夫妻问题对夫妻问题 3 3 *2.11 Mobius2.11 Mobius反演定理反演定理 2.12 2.12 鸽巢原理鸽巢原理 4 4 2.13 2.13 鸽巢原理举例鸽巢原理举例 4 4 2.14 2.14 鸽巢原理的推广鸽巢原理的推广 4 4 *2.15 Ramsey2.15 Ramsey数数 23.6 广义的容斥原理广义的容斥原理容斥原理解决的问题容斥原理解决的问题:nAAA.21 nA.AA21广义的容斥原理解决的问题广义的容斥原理解决的问题niiA.A.AAA12133.6 广义的容斥原理广义的容斥原理 求只参加了数学课的人数？求只参加了数学课的人数？只参加了

3、物理课的人数？只参加了物理课的人数？只参加了化学课的人数？只参加了化学课的人数？例例3.6.1：一个学校只有数学，物理，化：一个学校只有数学，物理，化学学3门课门课。学这。学这3门课的学生人数分别是门课的学生人数分别是170,130,120；同时学数学、物理两门课的学；同时学数学、物理两门课的学生有生有45人；同时学数学、化学的有人；同时学数学、化学的有20人；同人；同时学物理、化学的有时学物理、化学的有22人；同时修三门课的人；同时修三门课的学生有学生有3人，问这个学校共有多少学生人，问这个学校共有多少学生?只参加了数学、物理课的人数？只参加了数学、物理课的人数？只参加了数学、化学课的人数？

4、只参加了数学、化学课的人数？4CPM 单修一门数学，即修数学而不修物理和单修一门数学，即修数学而不修物理和化学的学生数；可如下表示：化学的学生数；可如下表示：解：设解：设M为修数学课的学生集合；为修数学课的学生集合；P为修为修物理课的学生集合；物理课的学生集合；C为修化学课的学生集合，为修化学课的学生集合，求只参加了数学课的人数？求只参加了数学课的人数？3.6 广义的容斥原理广义的容斥原理5CPM)()(CMPMMCPM关于关于M M互为补集互为补集1083)2045(170MPC)()()(CPMCMPMM)()(CMPM因此：只参加数学课因此：只参加数学课学习的人数有学习的人数有3.6 广

5、义的容斥原理广义的容斥原理6只学数学、物理两门课只学数学、物理两门课CPM)()(CPMPM42345MPC3.6 广义的容斥原理广义的容斥原理*73.6.1 3.6.1 一般公式一般公式假定全集是假定全集是N,N,其中有其中有A A1 1,A,A2 2,A,An n个子集，个子集，定义：当定义：当m0m0时时miiiAAAm.)(21对于特殊情况对于特殊情况m=0m=0时定义时定义:N)0(3.6 广义的容斥原理广义的容斥原理nAAA.21nnniijjhhjiniijjiniiAAAAAAAAAN.)1(.21111 8)(mnmmmiiiiiiAAAAAAm.)(2121nAAA.)0(

6、213.6 广义的容斥原理广义的容斥原理 定义定义 是正好存在于是正好存在于m m个集合的元素个集合的元素的个数的个数9 例例3.6.2 3.6.2 设设N=1,2,3,N=1,2,3,14,4,14,4个集合个集合A A1 1,A,A2 2,A,A3 3,A,A4 4。A A1 1=2,5,8,12,13,=2,5,8,12,13,；A A2 2=1,3,5,6,7,8,10,12,14=1,3,5,6,7,8,10,12,14；A A3 3=1,4,5,7,12,13=1,4,5,7,12,13；A A4 4=1,4,5,7,12,14=1,4,5,7,12,14。3.6 广义的容斥原理广

7、义的容斥原理10N123456789 10 11 12 13 14A1A2A3A4m=0m=0时时,14)0(Nm=1m=1时时,266695)1(4321AAAAm=2m=2时时,434232413121 )2(AAAAAAAAAAAA225542333.6 广义的容斥原理广义的容斥原理m=4m=4时时,2)4(4321AAAA114321)0(AAAA4321432143214321)1(AAAAAAAAAAAAAAAA 432143214321432143214321 )2(AAAAAAAAAAAAAAAAAAAAAAAA440031211,93.6 广义的容斥原理广义的容斥原理N123

8、456789 10 11 12 13 14A1A2A3A412定理定理3.3.4 3.3.4 广义容斥原理的证明广义容斥原理的证明)(),()1(.)2(),2()1(),1()()(nmnCmmmCmmmCmmmn证明：证明：miiiAAAm.)(21 aNaN,设它属于设它属于t t个集合个集合分分tm,t=m,ttmm三种情况来讨论三种情况来讨论(1)(1)若若tm,tm,tm,因为左端是正好存在于因为左端是正好存在于m m个集合的元素，因个集合的元素，因此左端没有计算此左端没有计算a a，在右端的情况分析如下：在右端的情况分析如下：3.6 广义的容斥原理广义的容斥原理)(),()1(.

9、)2(),2()1(),1()()(nmnCmmmCmmmCmmmnmiiiAAAm.)(21nmmmiiiiiiAAAAAAm.)(212115.次中计算了在),()(ttCta设设a a包含在包含在t t个集合中个集合中,A,A1 1,A,A2 2,.,A,.,At t，tm,tm,?)(中计算了多少次在ma),(mtC3.6 广义的容斥原理广义的容斥原理)1,(mtC？m中计算多少次在)1(a)(),()1(.)2(),2()1(),1()()(nmnCmmmCmmmCmmmnmiiiAAAm.)(2116),(),()1(.)2,(),2()1,(),1(),(ttCmtCmtCmmC

10、mtCmmCmtClmt3.6 广义的容斥原理广义的容斥原理设设a a包含在包含在t t个集合中个集合中,A,A1 1,A,A2 2,.,A,.,At t，tm,tm,因为左端是正好存在于因为左端是正好存在于m m个集合的元素，因个集合的元素，因此左端没有计算此左端没有计算a a，右端关于右端关于a a的计算的计算:),(),()1(.),2()2,(),1()1,(),(mtCttCmmCmtCmmCmtCmtClmt17),(),()1(.),2()2,(),1()1,(),(mtCttCmmCmtCmmCmtCmtClmt3.6 广义的容斥原理广义的容斥原理利用公式：利用公式：),(),

11、(),(),(rkrnCrnCrkCknC),(),()1(.)2,(),()1,(),(),(mtmtCmtCmtCmtCmtCmtCmtClmt),()1(.)2,()1,(1),(mtmtCmtCmtCmtCmt18),()1(.)2,()1,(1),(mtmtCmtCmtCmtCmt 中括号各项正好是中括号各项正好是(1-x)(1-x)t-mt-m的系数的系数,mtmtmtxmtmtCxmtCxmtCx),()1(.)2,()1,(1)1(23.6 广义的容斥原理广义的容斥原理如果令如果令x=1,x=1,得到：得到：0),()1(.)2,()1,(1mtmtCmtCmtCmt19综合以

12、上三种情况：综合以上三种情况：)(),()1(.)2(),2()1(),1()()(nmnCmmmCmmmCmmmn推论推论3.13.1)()1(.)2()1()0()0(nn3.6 广义的容斥原理广义的容斥原理 aNaN,设它属于设它属于t t个集合个集合分分tm,t=m,ttmm三种情况来讨论三种情况来讨论203.7 广义容斥原理的若干应用广义容斥原理的若干应用线性方程整数解的问题线性方程整数解的问题rxxxn.21 的零或正整数解的数目，其中的零或正整数解的数目，其中x x1 1,x,x2 2,x,xn n是变是变量，量，n1,r0,nn1,r0,n和和r r都是正整数。都是正整数。这个

13、方程的任一非负整数解都可以看做是这个方程的任一非负整数解都可以看做是r r个无个无区别的球放进区别的球放进n n个有标志个有标志x x1 1,x,x2 2,x,xn n的盒子，允许的盒子，允许空盒，空盒，),1(rrnC21例例3.6.4 3.6.4 求方程求方程x x1 1+x+x2 2+x+x3 3=15=15的整数解的数目，的整数解的数目，要求要求0 x0 x1 15,0 x5,0 x2 26,0 x6,0 x3 377。如果没有附加条件，即求：如果没有附加条件，即求：x x1 1+x+x2 2+x+x3 3=15=15的零或正的零或正整数解，即要求：整数解，即要求：x x1 100，x

14、 x2 200，x x3 300。C(3+15-1,15)=C(17,15)=C(17,2)C(3+15-1,15)=C(17,15)=C(17,2)变为讨论问题变为讨论问题x x1 1+x+x2 2+x+x3 3=15=15的整数解，求：的整数解，求：x x1 166，x x2 277，x x3 388。3.7 广义容斥原理的若干应用广义容斥原理的若干应用22例例3.6.4 3.6.4 求方程求方程x x1 1+x+x2 2+x+x3 3=15=15的整数解的数目，的整数解的数目，要求要求0 x0 x1 15,0 x5,0 x2 26,0 x6,0 x3 377。解解:令令N N为全体非负整

15、数解为全体非负整数解(x(x1 1,x,x2 2,x,x3 3),),A A1 1为其中为其中x x1 166的解；的解；A A2 2为其中为其中x x2 277的解；的解；A A3 3为其中为其中x x3 388的解。的解。3.7 广义容斥原理的若干应用广义容斥原理的若干应用 A A1 1的个数，相当于对（的个数，相当于对（y y1 1+6+6）+x+x2 2+x+x3 3=15=15求非负求非负整数解的个数。整数解的个数。C(3+9-1,9)=C(11,2)C(3+9-1,9)=C(11,2)y y1 1=x=x1 1-60-60的解；的解；y y2 2=x=x2 2-70-70的解；的解

16、；y y3 3=x=x3 3-80-80的解。的解。23A A2 2的个数，相当于对的个数，相当于对x x1 1+(y+(y2 2+7)+x+7)+x3 3=15=15求非负整求非负整数解的个数。数解的个数。C(3+8-1,8)=C(10,2)C(3+8-1,8)=C(10,2)A A3 3的个数，相当于对的个数，相当于对x x1 1+x+x2 2+(y+(y3 3+8)=15+8)=15求非负整求非负整数解的个数。数解的个数。C(3+7-1,7)=C(9,2)C(3+7-1,7)=C(9,2)3.7 广义容斥原理的若干应用广义容斥原理的若干应用24)2,9(),2,10(),2,11(),2

17、,17(321CACACACN性质性质A A1 1AA2 2的个数，相当于对的个数，相当于对（y y1 1+6+6）+(y+(y2 2+7)+x+7)+x3 3=15=15求非负整数解的个数。求非负整数解的个数。即求即求y y1 1+y+y2 2+x+x3 3=2=2的非负整数解，其解的个数为的非负整数解，其解的个数为C(3+2-1,2)=C(4,2)C(3+2-1,2)=C(4,2)性质性质A A1 1AA3 3的解的个数，相当于对的解的个数，相当于对(y(y1 1+6)+x+6)+x2 2+(y+(y3 3+8)=15+8)=15求非负整数解的个数。求非负整数解的个数。即求即求y y1 1

18、+x+x2 2+y+y3 3=1=1的非负整数解，其解的个数为的非负整数解，其解的个数为C(3+1-1,1)=C(3,1)C(3+1-1,1)=C(3,1)3.7 广义容斥原理的若干应用广义容斥原理的若干应用25性质性质A A2 2AA3 3的个数，相当于对的个数，相当于对x x1 1+(y+(y2 2+7)+(y+7)+(y3 3+8)=15+8)=15求非负整数解的个数。求非负整数解的个数。即求即求x x1 1+y+y2 2+y+y3 3=0=0的非负整数解，其解的个数为的非负整数解，其解的个数为C(3+0-1,0)=C(2,0)C(3+0-1,0)=C(2,0)2,9(),2,10(),

19、2,11(),2,17(321CACACACN)0,2(),1,3(),2,4(323121CAACAACAA3.7 广义容斥原理的若干应用广义容斥原理的若干应用26 性质性质A A1 1AA2 2AA3 3的个数，相当于对的个数，相当于对(y(y1 1+6)+(y+6)+(y2 2+7)+(y+7)+(y3 3+8)=15+8)=15求非负整数解的个数。求非负整数解的个数。即求即求y y1 1+y+y2 2+y+y3 3=-6=-6的非负整数解，其解的个数的非负整数解，其解的个数0 00321AAA)3()2()1()0()0(100)0,2()1,3()2,4()2,9()2,10()2,

20、11()2,17(CCCCCCC3.7 广义容斥原理的若干应用广义容斥原理的若干应用27例例3.6.5 3.6.5 求方程求方程x x1 1+x+x2 2+x+x3 3=15=15的整数解的数目，的整数解的数目，要求要求3x3x1 15,2x5,2x2 26,1x6,1x3 377。3.7 广义容斥原理的若干应用广义容斥原理的若干应用作变换作变换0 x0 x1 1-32,0 x-32,0 x2 2-24,0 x-24,0 x3 3-16-16。28FHABCDEGO(0,0)P(10,5)例例3.6.63.6.6：如图所示，：如图所示，1 1、求从、求从O(0,0)O(0,0)点到点到P(10

21、,5)P(10,5)点的路径中不点的路径中不通过通过AB,CD,EF,GHAB,CD,EF,GH中任何一条路径的路径数。中任何一条路径的路径数。坐标分别为坐标分别为:A(2,2),B(3,2),C(4,2),:A(2,2),B(3,2),C(4,2),D(5,2),E(6,2),F(6,3),G(7,2),H(7,3)D(5,2),E(6,2),F(6,3),G(7,2),H(7,3)。2 2、只通过其中两个的路径数。、只通过其中两个的路径数。路径数问题路径数问题:29FHABCDEGO(0,0)P(10,5)解：令解：令A A1 1为从为从O点到点到P P点过点过ABAB边的路径；边的路径；

22、令令A A2 2为从为从O点到点到P P点过点过CDCD边的路径；边的路径；令令A A3 3为从为从O点到点到P P点过点过EFEF边的路径；边的路径；令令A A4 4为从为从O点到点到P P点过点过GHGH边的路径；边的路径；)3,10()2,4(1CCA)3,8()2,6(2CCA)2,6()2,8(3CCA)2,5()2,9(4CCA 路径数问题路径数问题:30)2,6)(2,4(321CAAA)2,5)(2,4(421CAAA0431AAA0432AAA04321AAAA)3,8()2,4(21CCAA)2,6()2,4(31CCAA)2,5()2,4(41CCAA)2,6()2,6(

23、32CCAA)2,5()2,6(42CCAA043AA 路径数问题路径数问题:FHABCDEGO(0,0)P(10,5)31如果求正好过上述四条线段中两条的路径数如果求正好过上述四条线段中两条的路径数)4()2,4()3()2,3()2()2(CC)2,5()2,6()2,6()2,6()2,5()2,4()2,6()2,4()3,8()2,4(CCCCCCCCCC)2,5()2,4()2,6()2,4(3CCCC)4()3()2()1()0()0()2,5()2,9()2,6()2,8()3,8()2,6()3,10()2,4()5,15(CCCCCCCCC 0)2,5()2,6()2,6(

24、)2,6()2,5()2,4()2,6()2,4()3,8()2,4(CCCCCCCCCC)2,5()2,4()2,6()2,4(CCCC不通过上述四条线段中任何一条的路径数不通过上述四条线段中任何一条的路径数路径数问题路径数问题:*321 1、求、求n n对夫妻排成一行，夫妻相邻的排列数。对夫妻排成一行，夫妻相邻的排列数。解：解：nnn2!)(3.10,n对夫妻问题。对夫妻问题。2 2、求、求n n对夫妻排成一行，夫妻不相邻的排列数。对夫妻排成一行，夫妻不相邻的排列数。解：设解：设A Ai i是第是第i i对夫妻排在一起的排列集。对夫妻排在一起的排列集。正好有正好有m m对夫妻排在一起的方案

25、数对夫妻排在一起的方案数33解：设解：设A Ai i是第是第i i对夫妻排在一起的排列集。对夫妻排在一起的排列集。2)!12(nAi22)!22(nAAjihihiihnAAA2)!2(.21nn2)!12()1()2,(2)!22()2(2nCn),(2)!2()(hnChnhhnnn2!)(3.10,n对夫妻问题。对夫妻问题。34nnnnnCnnCnnCn2!),()1(.2)!22)(2,(2)!12)(1,()!2()0(2)()1(.)2()1()0()0(nn3.10,n对夫妻问题。对夫妻问题。)(),()1(.)2(),2()1(),1()()(nmnCmmmCmmmCmmmn正

26、好有正好有m m对夫妻排在一起的方案数对夫妻排在一起的方案数353,n3,n对夫妻围一圆桌而坐，夫妻相邻的排列数。对夫妻围一圆桌而坐，夫妻相邻的排列数。nn2)!1(3.10,n对夫妻问题。对夫妻问题。4 4、n n对夫妻围一圆桌而坐，夫妻不相邻的方案数？对夫妻围一圆桌而坐，夫妻不相邻的方案数？解：设解：设A Ai i是第是第i i对夫妻排在一起的排列集。对夫妻排在一起的排列集。正好有正好有m m对夫妻排在一起的方案数对夫妻排在一起的方案数362)!22(nAinn2)!22()1(nnnnnCnnCn2)!1()1(.2)!32)(2,(2)!22)(1,()!12()0(222)!32(n

27、AAjihihiihnAAA2)!12(.21)2,(2)!32()2(2nCn),(2)!12()(hnChnhhnnn2)!1()(3.10,n对夫妻问题。对夫妻问题。37习习 题题 3.20 3.20 在由在由a,a,a,b,b,b,c,c,ca,a,a,b,b,b,c,c,c组成组成的排列中的排列中,求满足下列条件的排列数。求满足下列条件的排列数。(1)(1)不存在相邻三元素相同。不存在相邻三元素相同。(2)(2)相邻两元素不相同相邻两元素不相同设设A A是有两个是有两个a a相邻的排列数。相邻的排列数。B B是有两个是有两个b b相邻的排列数。相邻的排列数。C C是有两个是有两个c

28、c相邻的排列数。相邻的排列数。解解(2)(2)：38习习 题题设设A A是两个是两个a a相邻的排列数。相邻的排列数。B B是两个是两个b b相邻的排列数。相邻的排列数。C C是两个是两个c c相邻的排列数。相邻的排列数。解：解：CBACBACBCABACBAN39CBACBCABA!3!3!7!3!3!8!3!7!3!6!3!6!3!5习习 题题40CBA!6设设X X是是a a与与aaaa相邻的排列数。相邻的排列数。Y Y是是b b与与bbbb相邻的排列数。相邻的排列数。Z Z是是c c与与cccc相邻的排列数。相邻的排列数。ZYXZYXZYZXYXZYX !3!4!4!4!5!5!5习习 题题*