第三章容斥原理与鸽巢原理.ppt

第三章第三章 容斥原理与容斥原理与鸽鸽巢原理巢原理1.例：例：11，2020中中2 2或或3 3的倍数的个数。的倍数的个数。解：解：2 2的倍数是：的倍数是：2 2，4 4，6 6，8 8，1010，1212，1414，1616，1818，2020。10 10个个 3 3的倍数是：的倍数是：3 3，6 6，9 9，1212，1515，1818。6 6个个 但答案不是但答案不是10+6=1610+6=16个，因个，因为为6 6，1212，1818在两在两类类中重复中重复计计数，数，应应减去。减去。故答案是：故答案是：16-3=1316-3=133.1 3.1 De MorganDe Morgan定理定理2.3.1 3.1 De MorganDe Morgan定理定理DeMorganDeMorgan定理定理 论论域域U，补补集集,有有(a)(b)3.DeMogan定理的推广：定理的推广：设A1,A2,An是是U的子集，的子集，则证明：只明：只证(1).N=2时定理已定理已证。设定理定理对n是正确的，即假定：是正确的，即假定：3.1 3.1 De MorganDe Morgan定理定理4.即定理即定理对n+1也是正确的。也是正确的。3.1 3.1 De MorganDe Morgan定理定理则5.即具有性即具有性质A或或B的元的元素的个数等于具有性素的个数等于具有性质A和和B的元素个数。的元素个数。定理：定理：3.2 3.2 容斥原理容斥原理UBA6.定理：定理：3.2 3.2 容斥原理容斥原理7.ABC3.2 3.2 容斥原理容斥原理8.例：例：一个学校只有三一个学校只有三门课程：数学、物理、程：数学、物理、化学。已知修化学。已知修这三三门课的学生分的学生分别有有170、130、120人；同人；同时修数学、物理两修数学、物理两门课的学生的学生45人；人；同同时修数学、化学的修数学、化学的20人；同人；同时修物理化学的修物理化学的22人。同人。同时修三修三门的的3人。人。问这学校共有多少学校共有多少学生？学生？3.2 3.2 容斥原理容斥原理9.令：令：M为修数学的学生集合；修数学的学生集合；P 为修物理的学生集合；修物理的学生集合；C 为修化学的学生集合；修化学的学生集合；3.2 3.2 容斥原理容斥原理10.即学校学生数即学校学生数为336人。人。3.2 3.2 容斥原理容斥原理11.同理可推出：同理可推出：利用数学利用数学归纳法可得一般的定理：法可得一般的定理：3.2 3.2 容斥原理容斥原理12.定理：定理：设A1,A2,An是有限集合，是有限集合，则3.2 3.2 容斥原理容斥原理13.证：用数学：用数学归纳法法证明。明。已知已知 n=2时有有设 n-1时成立，即有：成立，即有：3.2 3.2 容斥原理容斥原理14.3.2 3.2 容斥原理容斥原理15.3.2 3.2 容斥原理容斥原理16.3.2 3.2 容斥原理容斥原理17.3.2 3.2 容斥原理容斥原理18.3.2 3.2 容斥原理容斥原理19.3.2 3.2 容斥原理容斥原理20.其中其中N是集合是集合U的元素个数，即不属于的元素个数，即不属于A的元的元素个数等于集合的全体减去属于素个数等于集合的全体减去属于A的元素的个数。的元素的个数。一般有：一般有：3.2 3.2 容斥原理容斥原理又又21.3.2 3.2 容斥原理容斥原理22.例例1 1 求求a,b,c,d,e,f六个字母的全排列中不允六个字母的全排列中不允许出出现ace和和df图象的排列数。象的排列数。解：解：设A为ace作作为一个元素出一个元素出现的排列集，的排列集，B为 df作作为一个元素出一个元素出现的排列集，的排列集，为同同时出出现ace、df的排列数。的排列数。3.3.3 3 容斥原理容斥原理举例例23.根据容斥原理，不出根据容斥原理，不出现ace和和df的排列数的排列数为：=6!-(5!+4!)+3!=582 3.3.3 3 容斥原理容斥原理举例例24.例例2 2 求从求从1到到500的整数中能被的整数中能被3或或5除尽的数除尽的数的个数。的个数。解：解：令令A为从从1到到500的整数中被的整数中被3除尽的数除尽的数的集合，的集合，B为被被5除尽的数的集合除尽的数的集合3.3.3 3 容斥原理容斥原理举例例25.被被3或或5除尽的数的个数除尽的数的个数为例例3 3 求由求由a,b,c,d四个字母构成的位符号串中，四个字母构成的位符号串中，a,b,c至少出至少出现一次的符号串数目。一次的符号串数目。3.3.3 3 容斥原理容斥原理举例例26.解：令解：令A、B、C分分别为n位符号串中不出位符号串中不出现a，b，c符号的集合。符号的集合。由于由于n位符号串中每一位都可取位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允四种符号中的一个，故不允许出出现a的的n位位符号串的个数符号串的个数应是是3n，即，即3.3.3 3 容斥原理容斥原理举例例27.a，b，c至少出至少出现一次的一次的n位符号串集合即位符号串集合即为3.3.3 3 容斥原理容斥原理举例例28.例例4 4 求不超求不超过120的素数个数。的素数个数。因因 112=121，故不超，故不超过120的合数必然是的合数必然是2、3、5、7的倍数，而且不超的倍数，而且不超过120的合数的因子不可能都超的合数的因子不可能都超过11。设Ai为不超不超过120的数的数i 的倍数集的倍数集,i=2,3,5,7。3.3.3 3 容斥原理容斥原理举例例29.3.3.3 3 容斥原理容斥原理举例例30.3.3.3 3 容斥原理容斥原理举例例31.3.3.3 3 容斥原理容斥原理举例例32.3.3.3 3 容斥原理容斥原理举例例33.3.3.3 3 容斥原理容斥原理举例例34.注意：注意：27并非就是不超并非就是不超过120的素数个数，因的素数个数，因为这里排除了里排除了2，3，5，7四个数，又包含了四个数，又包含了1这个非素数。个非素数。2，3，5，7本身是素数。故所求的本身是素数。故所求的不超不超过120的素数个数的素数个数为：27+4-1=303.3.3 3 容斥原理容斥原理举例例35.例例5 5 用用26个英文字母作不允个英文字母作不允许重复的全排列，重复的全排列，要求排除要求排除dog，god，gum，depth，thing字字样的的出出现，求，求满足足这些条件的排列数。些条件的排列数。解：所有排列中，令：解：所有排列中，令：3.3.3 3 容斥原理容斥原理举例例36.3.3.3 3 容斥原理容斥原理举例例A1为出出现dog的排列的全体的排列的全体;A2为出出现god的排列的全体的排列的全体;A3为出出现gum的排列的全体的排列的全体;A4为出出现depth的排列的全体的排列的全体.A5为出出现thing的排列的全体的排列的全体.37.出出现dogdog字字样的排列，相当于把的排列，相当于把dogdog作作为一一个个单元参加排列，故元参加排列，故类似有：似有：由于由于god,dog不可能在一个排列中同不可能在一个排列中同 时出出现，故：，故：类似：似：3.3.3 3 容斥原理容斥原理举例例38.由于由于gum,dog可以在可以在dogum字字样中同中同时出出现，故，故有：有：类似有似有god和和depth可以在可以在godepth字字样中同中同时出出现，故，故 god和和thing可以在可以在thingod字字样中同中同时出出现，从，从而而 3.3.3 3 容斥原理容斥原理举例例39.3.3.3 3 容斥原理容斥原理举例例40.由于由于god、depth、thing不可以同不可以同时出出现，故有：，故有：其余多于其余多于3个集合的交集都个集合的交集都为空集。空集。3.3.3 3 容斥原理容斥原理举例例41.故故满足要求的排列数足要求的排列数为：3.3.3 3 容斥原理容斥原理举例例42.例例6 6 求完全由求完全由n个布个布尔变量确定的布量确定的布尔函数函数的个数。的个数。解：解：设f(x1,x2,xn)中不出中不出现xi的布的布尔函数函数为Ai (i=1,2,n)由于由于n个布个布尔变量量 的不同的的不同的真真值表数目与表数目与 位位2进制数数目相同，故制数数目相同，故为 个。根据容斥原理，个。根据容斥原理，满足条件的函数数目足条件的函数数目为：3.3.3 3 容斥原理容斥原理举例例43.3.3.3 3 容斥原理容斥原理举例例若若n=2，则44.x1、x2均出均出现的的10个布个布尔函数函数为：x1x2，x1x2，x1x2，x1x2，x1x2，x1x2，x1x2，x1x2，(x1x2)(x1x2)，(x1x2)(x1x2)3.3.3 3 容斥原理容斥原理举例例45.例例7 7：错排排问题 n个元素依次个元素依次给以以标号号1，2，n。N个个元素的全排列中，求每个元素都不在自己原来元素的全排列中，求每个元素都不在自己原来位置上的排列数。位置上的排列数。设Ai为数数i在第在第i位上的全体排列，位上的全体排列，i=1，2，n。因数字。因数字i不能不能动，因而有：，因而有：3.3.3 3 容斥原理容斥原理举例例46.3.3.3 3 容斥原理容斥原理举例例47.每个元素都不在原来位置的排列数每个元素都不在原来位置的排列数为3.3.3 3 容斥原理容斥原理举例例48.例例8.8.数数1,2,9的全排列中的全排列中,求偶数在原来位置求偶数在原来位置上上,其余都不在原来位置的其余都不在原来位置的错排数目。排数目。解：解：实际上是上是1,3,5,7,9五个数的五个数的错排排问题，总数数为：3.3.3 3 容斥原理容斥原理举例例49.例例9.9.在在8个字母个字母A,B,C,D,E,F,G,H的全排列中的全排列中,求求使使A,C,E,G四个字母不在原来上的四个字母不在原来上的错排数目。排数目。解解:8个字母的全排列中，令个字母的全排列中，令分分别表表A,C,E,G在原来位置上的排列，在原来位置上的排列，则错排数：排数：3.3.3 3 容斥原理容斥原理举例例50.3.3.3 3 容斥原理容斥原理举例例51.例例10.10.求求8个字母个字母A,B,C,D,E,F,G,H的全排列中只的全排列中只有有4个不在原来位置的排列数。个不在原来位置的排列数。解：解：8个字母中只有个字母中只有4个不在原来位置上个不在原来位置上,其其余余4个字母保持不个字母保持不动,相当于相当于4个元素的个元素的错排排,其其数目数目为：3.3.3 3 容斥原理容斥原理举例例52.故故8个字母的全排列中有个字母的全排列中有4个不在原来位置上个不在原来位置上的排列数的排列数应为：C(8,4)9=6303.3.3 3 容斥原理容斥原理举例例53.1.有限制排列有限制排列3.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列 例例4个个x，3个个y，2个个z的全排列中，求不出的全排列中，求不出现xxxx，yyy，zz图象的排列。象的排列。解解设出出现xxxx的排列的集合的排列的集合记为A1，|A1|=60;设出出现yyy的排列的集合的排列的集合记为A2，|A2|=105；6!4!2!7!1!3!2!54.3.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列 设出出现zz的排列的集合的排列的集合记为A3，|A3|=280；|A1A2|=12；|A1A3|=20；|A2A3|=30；|A1A2A3|=3!=6；全排列的个数全排列的个数为：=1260；所以：所以：|A1A2A3|=1260(60+105+280)+(12+20+30)6 =871 4!3!8!4!2!5!3!6!4!9!2!3!4!55.2.棋子多棋子多项式式 n个不同元素的一个全排列可看做个不同元素的一个全排列可看做n个相同个相同的棋子在的棋子在nn的棋的棋盘上的一个布局。布局上的一个布局。布局满足同足同一行（列）中有且一行（列）中有且仅有一个棋子。有一个棋子。xxxxx 如如图所示的布局所示的布局对应于排列于排列41352。3.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列56.可以把棋可以把棋盘的形状推广到任意形状：的形状推广到任意形状：布子布子规定称定称为无无对攻攻规则，棋子相当于象，棋子相当于象棋中的棋中的车。令令r k(C)表示表示k个棋子布到棋个棋子布到棋盘C上的方案上的方案数。如：数。如：3.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列57.r1()=1，r1()=2，r1()=2，r2()=0，r2()=1。为了形象化起了形象化起见,()中的中的图像便是棋像便是棋盘的形状。的形状。3.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列58.定定义 设C为一棋一棋盘，称，称R(C)=rk(C)xk为C的棋的棋盘多多项式。式。规定定 r0(C)=1，包括，包括C=时。设Ci是棋是棋盘C的某一指定格子所在的行与列的某一指定格子所在的行与列都去掉后所得的棋都去掉后所得的棋盘；Ce是是仅去掉去掉该格子后的格子后的棋棋盘。在上面定在上面定义下，下，显然有然有 rk(C)=rk1(Ci)rk(Ce)，k=03.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列59.即即对任一指定的格子，要么布子，所得的任一指定的格子，要么布子，所得的方案数方案数为 rk1(Ci)；要么不布子，方案数要么不布子，方案数为 rk(Ce)。设C有有n个格子，个格子，则 r1(C)n r1(C)r0(Ci)+r1(Ce)，r1(Ce)n1 r0(Ci)1 故故规定定 r0(C)1是合理的是合理的3.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列60.即即对任一指定的格子，要么布子，所得的任一指定的格子，要么布子，所得的方案数方案数为 rk1(Ci)；要么不布子，方案数要么不布子，方案数为 rk(Ce)。从而从而R(C)=rk(C)xk rk1(Ci)+rk(Ce)xk =x rk(Ci)xk+rk(Ce)xk xR(Ci)+R(C e)k=0k=0k=0k=03.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列61.例如：例如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=x R()+R()=x(1+x)+1+x =1+2x+x23.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列62.如果如果C由相互分离的由相互分离的C1，C2组成，即成，即C的的任一格子所在的行和列中都没有任一格子所在的行和列中都没有C2的格子。的格子。则有：有：rk(C)=ri(C1)rki(C2)i=0k故故R(C)=(ri(C1)rki(C2)xk =(ri(C1)xi)(rj(C2)xj)j=0nnkni=0i=0k=0 R(C)=R(C1)R(C2)3.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列63.利用利用(3)和和(4)，可以把一个比，可以把一个比较复复杂的棋的棋盘逐步分解成相逐步分解成相对比比较简单的棋的棋盘，从而得，从而得到其棋到其棋盘多多项式。式。例例R()=xR()+R()=x(1+x)2 +(1+2x)2 =1+5x+6x2+x3*R()=xR()+R()=1+6x+10 x2+4x33.3.4 4 棋棋盘多多项式和有限制排列式和有限制排列64.例例设对于排列于排列P=P1 P2 P3 P4，规定定P1，P、，、，P2、，、，P42。1 2 3 4P1P2P3P412 4 314 3223431 214 这样的排列的排列对应于有于有禁区的布子。如右禁区的布子。如右图有影有影线的格子表示禁区。的格子表示禁区。3.3.5 5 有禁区的排列有禁区的排列65.定理定理设 ri 为 i个棋子布入禁区的方案数，个棋子布入禁区的方案数，i=1,2,3,n。有禁区的布子方案数。有禁区的布子方案数(即禁即禁区内不布子的方案数区内不布子的方案数)为 r0 n!r1(n1)!r2(n2)!(1)nrn(1)k rk(nk)!k=0n证令令P1P2Pn是是n个棋子布入个棋子布入nn棋棋盘的排列的排列,即即Pi是第是第i个棋子在第个棋子在第i行的位置行的位置,Ai 是棋子是棋子Pi3.3.5 5 有禁区的排列有禁区的排列66.落入禁区落入禁区,其他棋子任意布的方案集，其他棋子任意布的方案集，i=1,2,3,n。一个棋子落入禁区。一个棋子落入禁区,其余其余n-1个棋子个棋子进行无条件的排列行无条件的排列,故至少有一个棋子落入禁区故至少有一个棋子落入禁区的方案数的方案数为r1(n-1)!,两个棋子落入禁区两个棋子落入禁区,其余其余n-2个棋子个棋子进行无条件的排列行无条件的排列,故至少有两个棋子故至少有两个棋子落入禁区的方案数落入禁区的方案数为r2(n-2)!,依次依次类推推,n个棋个棋子无一落入禁区的排列数子无一落入禁区的排列数为:A1A2An=n!+(1)k rk(nk)!k=0 n3.3.5 5 有禁区的排列有禁区的排列67.上例方案数上例方案数为 4!6(41)!11(42)!7(43)!1(4)!4例例1,2,3,4四位工人，四位工人，A,B,C,D 四四项任任务。条件如下条件如下:1不干不干B;2不干不干B、C;不干不干C、D;4不干不干D。问有多少种可行方案？有多少种可行方案？3.3.5 5 有禁区的排列有禁区的排列68.解由解由题意，可得如下棋意，可得如下棋盘：其中有影其中有影线的格子表示的格子表示禁区。禁区。A B C D1 2 3 4 R()=1+6x+10 x2+4x3 方案数方案数=4!6(41)!+10(42)!4(43)!+0(44)!=43.3.5 5 有禁区的排列有禁区的排列69.例例三三论错排排问题 错排排问题对应的是的是nn的棋的棋盘的主的主对角角线上的格子是禁区的布子上的格子是禁区的布子问题。C=错排的方案数排的方案数:3.3.5 5 有禁区的排列有禁区的排列70.3.3.6 6广广义的容斥原理的容斥原理例：例：若将若将.2中的例子改中的例子改为“单修一修一门数学的学数学的学生有多少？生有多少？”“只修一只修一门课的学生有多少的学生有多少”“只修只修两两门课的学生有多少？的学生有多少？”则相相应的答案表示如下：的答案表示如下：MPC；MPC+MPC+MPCMPC+MPC+MPC71.3.3.6 6广广义的容斥原理的容斥原理u只修一只修一门数学：数学：u只修一只修一门物理：物理：u只修一只修一门化学：化学：72.3.3.6 6广广义的容斥原理的容斥原理所以，只修一所以，只修一门课程：程：73.3.3.6 6广广义的容斥原理的容斥原理u修数学和物理两修数学和物理两门课：u类似地：似地：74.3.3.6 6广广义的容斥原理的容斥原理一般地：一般地：75.所以，可得：所以，可得：3.3.6 6广广义的容斥原理的容斥原理76.3.3.6 6广广义的容斥原理的容斥原理还可以推得：可以推得：77.3.3.6 6广广义的容斥原理的容斥原理所以有：所以有：78.3.3.6 6广广义的容斥原理的容斥原理定理：定理：在集合在集合S中中,设A1,A2,An是是n种性种性质的的子集子集,(m)表示表示刚好只有其中好只有其中m个性个性质的元素的元素个数个数,(m)表示至少有表示至少有m个性个性质的元素个数的元素个数,则79.3.3.6 6广广义的容斥原理的容斥原理以以m=2,n=4为例：例：80.3.3.6 6广广义的容斥原理的容斥原理以以m=3,n=4为例：例：81.例：例：某校有某校有12个教个教师,已知教数学的有位已知教数学的有位,教物理教物理的有位的有位,教化学的位教化学的位;数、理位数、理位,数、化位数、化位,理、化位理、化位;数理化位。数理化位。问教其他教其他课的有几位？的有几位？只教一只教一门的有几位？只好教两的有几位？只好教两门的有几位？的有几位？解令教数学的教解令教数学的教师属于属于A1，教物理的属于，教物理的属于A2，教化学的属于教化学的属于A3。则(0)12，(1)|A1|+|A2|+|A3|8+6+519;(2)|A1A2|+|A1A3|+|A2A3|12；(3)|A1A2A3|3；3.3.7 7广广义的容斥原理的的容斥原理的应用用82.故教其他故教其他课的老的老师数数为：(0)(0)(1)+(2)(3)恰好一恰好一门的教的教师数：数：(1)(1)2(2)+3(3)=4恰好教两恰好教两门的老的老师数数为：(2)(2)3(3)=33.3.7 7广广义的容斥原理的的容斥原理的应用用83.3.3.8 8 第二第二类StirlingStirling数的展开式数的展开式第二第二类Stirling数，数，S(n,m)是将是将n个有个有标志的球放志的球放进m个无区个无区别的盒子而无一空盒的盒子而无一空盒的方案数，也是将的方案数，也是将n个数拆分成正好个数拆分成正好m个数个数的和的方案数。的和的方案数。考考虑n个有个有标志的球放志的球放进m个有区个有区别的盒的盒子，无一空盒的方案数，令：子，无一空盒的方案数，令：Ai表示第表示第i盒盒为空盒的子集，空盒的子集，i=1,2,m.n个有个有标志的球，志的球，m个有区个有区别的盒，无一的盒，无一空盒的事件全体空盒的事件全体为S.84.3.3.8 8 第二第二类StirlingStirling数的展开式数的展开式85.3.3.8 8 第二第二类StirlingStirling数的展开式数的展开式n个有个有标志的球放志的球放进m个有区个有区别的盒子，的盒子，无一空盒的方案数：无一空盒的方案数：86.3.3.8 8 第二第二类StirlingStirling数的展开式数的展开式第二第二类Stirling数，数，S(n,m)是将是将n个有个有标志志的球放的球放进m个无区个无区别的盒子而无一空盒的方的盒子而无一空盒的方案数，所以：案数，所以：推推论1：推推论2：由于：由于S(m,m)=187.问题:欧拉函数欧拉函数(n)是求小于是求小于n且与且与n互素互素的数的个数。的数的个数。解：若解：若n分解分解为素数的乘素数的乘积 设1到到n的的n个数中个数中为Pi 倍数的数的集合倍数的数的集合为:Ai (i=1,2,n)则有有3.3.9 9 欧拉函数欧拉函数(n)(n)88.3.3.9 9 欧拉函数欧拉函数(n)(n)89.3.3.9 9 欧拉函数欧拉函数(n)(n)90.即比即比60小且与小且与60无公因子的数有无公因子的数有16个：个：7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，此外尚有一个，此外尚有一个1。3.3.9 9 欧拉函数欧拉函数(n)(n)91.3.3.1010n n对夫妻夫妻问题例例n 对夫妻夫妻围坐坐问题 设 n 对夫妻夫妻围圈而坐，男女相圈而坐，男女相间，每个男人，每个男人都不和他的妻子相都不和他的妻子相邻，有多少种可能的方案？，有多少种可能的方案？解：（解：（1）n个人个人围桌而坐的方案数桌而坐的方案数应为(n1)!n对夫妻夫妻围桌而坐的方案数：桌而坐的方案数：2n(n-1)!令：令：Ai表示第表示第i对夫妻相夫妻相邻而坐的集合，而坐的集合，i=1,2,n,夫妻不相夫妻不相邻的方案数的方案数为：92.3.3.1010n n对夫妻夫妻问题（2）2n个人个人围桌而坐的方案数桌而坐的方案数应为(2n1)!|Ai|相当于将第相当于将第i对夫妻作夫妻作为一个一个对象象围桌而坐后桌而坐后换位，故：位，故：93.3.3.1010n n对夫妻夫妻问题故夫妻不相故夫妻不相邻而坐的方案数而坐的方案数为：94.11.11M Mbius反演定理反演定理 基本想法：基本想法：an 易算易算,bn难算算,an可用可用 bn表示表示,利用反演利用反演,将将bn用用an表示表示 1.二二项式反演式反演引理引理:95.11.11M Mbius反演定理反演定理 基本想法：基本想法：an 易算易算,bn难算算,an可用可用 bn表示表示,利用反演利用反演,将将bn用用an表示表示 1.二二项式反演式反演引理引理:96.11.11M Mbius反演定理反演定理 基本想法：基本想法：an 易算易算,bn难算算,an可用可用 bn表示表示,利用反演利用反演,将将bn用用an表示表示 Mbius反演定理：反演定理：设f(n)和和g(n)是定是定义在正整在正整数集合上的两个函数，若数集合上的两个函数，若则 反之亦然。反之亦然。其中：其中：若若d=1=1若若d=r个不同素数之个不同素数之积其它（素数其它（素数积中含有相同素数）中含有相同素数）97.11.11M Mbius反演定理反演定理 辅助定理：助定理：对于任意正整数于任意正整数n恒有：恒有：证明：明：n=1时，定理成立。，定理成立。若若其中，其中，pi是互不相同的素数。是互不相同的素数。d|n可表示可表示为：98.11.11M Mbius反演定理反演定理则d是从是从 个个 中中选 个个 ，从从 个个 中中选 个个 ，从从 个个 中中选 个个 ，而得到的，而得到的结果。果。而重复取某个而重复取某个 时，令：，令：99.11.11M Mbius反演定理反演定理证明明(Mbius反演定理反演定理)：由由f(n)的公式得：的公式得：令令由于由于100.11.11M Mbius反演定理反演定理所以，所以，反反过来，来，101.例例圆排列排列问题 设 a1a2an 是一个是一个圆排列排列，即，即 a2a3ana1,ana1 an1，看作是相同的。，看作是相同的。为了加以区了加以区别，必，必要要时把原先的排列称把原先的排列称为线排列排列。一个。一个圆排列在排列在 n 个位置短开形成的个位置短开形成的 n 个个线排列在元素可重复的情排列在元素可重复的情况下，未必都不相同。况下，未必都不相同。例如，例如，dn时，由不重复的，由不重复的a1a2 ad重复重复 n d次构成的次构成的圆排列。排列。.11.11M Mbius反演定理反演定理102.(a1a2 ad )(a1a2 ad )n d 组 只能形成只能形成 d 个不同的个不同的线排列。排列。若一个若一个圆排列可由一个排列可由一个长度度为 k 的的线排列重复排列重复若干次形成，若干次形成，则这样的的 k 中最小者成中最小者成为该圆排排列的周期列的周期。一个。一个圆排列中元素的个数（重复出排列中元素的个数（重复出现的按其重复次数的按其重复次数计）称）称为它的它的长度度。.11.11M Mbius反演定理反演定理103.设集合集合1,2,m中元素形成的中元素形成的长度度与周期都是与周期都是 d 的的圆排列的个数排列的个数为M(d)。设 n 是一是一给定的正整数。定的正整数。若若 d n，每个，每个长度与周期都是度与周期都是 d的的圆排排列可在列可在 d 个位置上断开，重复个位置上断开，重复 n/d 次形成次形成d个个长度度为 n 的可重排列。因此有的可重排列。因此有 d M(d)=mn 由由Mbus反演定理反演定理 n M(n)=(d)m故故M(n)=(d)mdndndnndnd.11.11M Mbius反演定理反演定理104.设长度度为 n 的的圆排列的个数排列的个数为T(n)，则T(n)M(d)dn例例m=1,2 ，n=7 则 M(7)=(272)=18 T(7)=M(d)=M(1)+M(7)=20 d717.11.11M Mbius反演定理反演定理105.12 12 鸽巢原理巢原理 鸽巢原理是巢原理是组合数学中最合数学中最简单也是最基本也是最基本的原理，也叫抽的原理，也叫抽屉原理。即原理。即 “若有若有n个个鸽子巢，子巢，n+1个个鸽子，子，则至少有一至少有一个巢内有至少有两个个巢内有至少有两个鸽子。子。”例例367人中至少有人的生日相同。人中至少有人的生日相同。例例10双手套中任取双手套中任取11只，其中至少有两只只，其中至少有两只 是完整配是完整配对的。的。例例参加一会参加一会议的人中至少有人的人中至少有人认识的的别的参加者的人数相等。的参加者的人数相等。106.例例从从1到到2n的正整数中任取的正整数中任取n+1个，个，则这n+1个数中，至少有一个数中，至少有一对数，其中一个是另数，其中一个是另一个的倍数。一个的倍数。证设n+1个数是个数是 a1,a2,an+1。每个数去掉。每个数去掉一切一切2的因子，直至剩下一个奇数的因子，直至剩下一个奇数为止。止。组成序成序列列 r1,r2,rn+1。这n+1个数仍在个数仍在1,2n中，中，且都是奇数。而且都是奇数。而1,2n中只有中只有n个奇数个奇数。故必有故必有 ri=rj=r,则 ai=2i r,aj=2j r若若ij，则 ai 是是 aj 的倍数。的倍数。.12 12 鸽巢原理巢原理107.例例设 a1,a2,am是正整数序列，是正整数序列，则至至 少存在少存在k和和 t,1kt m，使得和，使得和 ak+ak+1+at 是是m的倍数。的倍数。证设Sk=ai,Sh rh mod m 0rhm-1h=1,2,m.若存在若存在t,St0 mod m 则命命题成立否成立否则，1rhm-1但但h=1,2,m由由鸽巢原理，故存在巢原理，故存在 rk=rh,即即Sk Sh，不妨，不妨设 h k则 ShSk=ak+1+ak+2+ah 0 mod m i=1k.13 13 鸽巢原理巢原理举例例108.例例 设 a1,a2,a3为任意个整数，任意个整数，b1b2b3为a1,a2,a3的任一排列，的任一排列，则 a1b1,a2b2 ,a3b3中至少有一个是偶数中至少有一个是偶数证由由鸽巢原理，巢原理，a1,a2,a3必有两个同奇必有两个同奇偶偶设这个数被除的余数个数被除的余数为 xxy，于，于是是b1,b2,b3中被除的余数有个中被除的余数有个x，一个，一个y这样a1b1,a2b2 ,a3b3被除的余被除的余数必有一个数必有一个为.13 13 鸽巢原理巢原理举例例109.例例 设a1,a2,a100是由是由 1和和组成的序成的序列列,已知从其任一数开始的已知从其任一数开始的顺序序10个数的和个数的和不超不超过16即即 ai+ai+1+ai+9 16，1 i 91 则至少存在至少存在 h 和和 k，k h，使得，使得 ah+ah+1+ak=39 证令令Sj=ai，j=1,2,100显然然 S1S2hSkSh=39 即即 ah+ah+1+ak=39.13 13 鸽巢原理巢原理举例例111.鸽巢原理二巢原理二设至少至少kn+1只只鸽子分配在子分配在n个个鸽巢里巢里,则至少存在一个至少存在一个鸽巢中有至少巢中有至少k+1只只鸽子。子。上一小上一小节的的鸽巢原理一是巢原理一是这一原理的特一原理的特殊情况，即殊情况，即k=1时的情况。的情况。.14 14 鸽巢原理的推广巢原理的推广112.推推论m只只鸽子子进n个巢，至少有一个巢里有个巢，至少有一个巢里有不少于不少于 只只鸽子子推推论n(m1)+1只只鸽子子进n个巢，至少有一个巢，至少有一个巢内至少有个巢内至少有m只只鸽子子推推论若若m1,m2,mn是正整数，且是正整数，且 r1,则 m1,mn至少有一个数不小于至少有一个数不小于r。m1+mn n.14 14 鸽巢原理的推广巢原理的推广113.定理若序列定理若序列S=a1,a2,an2+1中的各数是中的各数是不等的不等的则 S中至少可中至少可选出一出一组由由n+1个元素个元素组成的或成的或为单调增或增或为单调减的子序列。减的子序列。证由由S中的每个中的每个 ai 向后向后选取最取最长单调增子增子序列，序列，设其其长度度为li(i=1,2,n2+1)，从而得序，从而得序列列L=l1,l2,lk,若存在若存在 lkn+1,则结论成成立立.14 14 鸽巢原理的推广巢原理的推广114.否否则所有的所有的 li 1,n,其中必有其中必有 个相等个相等设li1=li2=lin=lin+1 不妨不妨设 i1i2 ai2 ain+1，即有一，即有一长度度为n+1的的递减子序列减子序列否否则不妨不妨设ai1 li2，矛盾，矛盾.14 14 鸽巢原理的推广巢原理的推广115.例例将将 1,67 划分划分为个子集，必有一个子个子集，必有一个子集中有一数是同子集中的另两数之差集中有一数是同子集中的另两数之差证用反用反证法法设此命此命题不真即存在划分不真即存在划分P1P2P3P4 1,67,Pi中不存在一个数是中不存在一个数是Pi中两数之差，中两数之差，i=1,2,3,4，因，因 ,故有故有一子集，其中至少有一子集，其中至少有17个数，个数，设这17个数从小个数从小到大到大为a1,a17 不妨不妨设 A=a1,a17 。令令bi1=aia1，i=2，17。.14 14 鸽巢原理的推广巢原理的推广116.设Bb1,b16，bi 1,67。由反。由反证法假法假设BP1=。因而。因而 B(P2 P3 P4)。因因为 ，不妨，不妨设b1,b6 P2，令令Ci1=bib1，i=2，6 设C C1,C5，C 1,67 由反由反证法假法假设C(P1P2)=，故有，故有 C(P3P4)因因为 ，不妨，不妨设C1,C2,C3 P3.14 14 鸽巢原理的推广巢原理的推广117.14 14 鸽巢原理的推广巢原理的推广令令di1=CiC1，i=2,3设D d1,d2 ,D 1,67。由反由反证法假法假设 D(P1P2P3)=，因而，因而 D P4由反由反证法假法假设 d2d1 P1P2P3 且且d2d1 P4，故故 d2d1 1,67，但，但显然然 d2d1 1,67，矛盾。，矛盾。118.1515RamseyRamsey问题RamseyRamsey问题 Ramsey问题可以看成是可以看成是鸽巢原理的推广下巢原理的推广下面面举例例说明明Ramsey问题例例6 个人中至少存在人相互个人中至少存在人相互认识或者相互不或者相互不认识证这个个问题与与K6的的边着色存在同色三角形着色存在同色三角形等价假定用等价假定用红蓝着色着色119.15 Ramsey 15 Ramsey 问题 设K6的的顶点集点集为v1,v2,v6，dr(v)表表示与示与顶点点 v 关关联的的红色色边的条数，的条数，db(v)表示与表示与 v 关关联的的蓝色色边的条数在的条数在K6 中，有中，有dr(v)db(v)，由，由鸽巢原理可知，至少巢原理可知，至少有条有条边同色同色现将将证明明过程用判断程用判断树表示如下：表示如下：120.15 Ramsey 15 Ramsey 问题dr(v1)3?db(v1)3设(v1v2)(v1v3)(v1v4)为红边设(v1v2)(v1v3)(v1v4)为蓝边v2v3v4是是红?v2v3v4是是蓝?设(v2v3)是是蓝边设(v2v3)是是红边v1v2v3是是蓝v1v2v3是是红YNNNYY121.15 Ramsey 15 Ramsey 问题若干推若干推论(a)(a)K6的的边用用红蓝任意着色，任意着色，则至少有两个至少有两个同色的三角形同色的三角形。证由前定理知，有同色三角形，不妨由前定理知，有同色三角形，不妨设v1v2v3是是红色三角形可由如下判断色三角形可由如下判断树证明明122.15 Ramsey 15 Ramsey 问题v1v4v5是是蓝设(v4v5)为蓝边v4v5v6是是红?设(v1v4)(v1v5)(v1v6)为蓝边db(v1)3dr(v1)3?设(v1v4)为红边(v4v2)(v4v3)为蓝边?设(v4v2)为红边db(v4)3?v1v2v4是是红dr(v4)3设(v4v5)为蓝边(v4v5)(v4v6)为红边v2v3v5是是红?设(v2v5)为蓝边v2v4v5是是蓝v4v5v6是是红v1v5v6是是蓝?设(v5v6)为红边yyyyyynnnnn123.15 Ramsey 15 Ramsey 问题(b)(b)K9 的的边红蓝两色任意着色，两色任意着色，则必有必有红K4或或蓝色三角形色三角形(蓝K4或或红色三角形色三角形)证设个个顶点点为 v1,v2,v9对个个顶点的点的完全完全图的的边的的红、蓝着色着色图中，必然存在中，必然存在vi，使得使得 dr(vi)3 否否则，红边数数 d