组合数学第六章

第六章容斥原理及应用,刘贵全gqliu,6.1容斥原理,例1，20中2或3的倍数的个数解2的倍数是：2，4，6，8，10，12，14，16，18，20。10个3的倍数是：3，6，9，12，15，18。6个但答案不是10+6=16个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=13,容斥原理研究有限集合的交或并的计数。DeMorgan定理论域U，补集,(a),(b),6.1容斥原理,6.1容斥原理,DeMogan定理的推广：设A1,A2,An是U的子集，则(1)(2),设S为物品的有穷集，P1和P2为两种性质，S中每个物品可以具有或不具有这些性质，A1和A2分别是具有性质P1和P2的物品组成的子集。则既不具有性质P1也不具有性质P2的物品的子集的大小为：其正确性可以这样证明：每个既不具有性质P1也不具有性质P2的物品对等式右边贡献的净值为1；其它物品对等式右边贡献的净值为0.,6.1容斥原理,6.1容斥原理,S,A2,A1,A1A2,同样有,6.1容斥原理,6.1容斥原理,6.1容斥原理,6.1容斥原理,例一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？,解令：M为修数学的学生集合；P为修物理的学生集合；C为修化学的学生集合；,6.1容斥原理,|MPC|=|M|+|P|+|C|-|MP|-|MC|-|PC|+|MPC|=170+130+120-45-20-22+3=336即学校学生数为336人。,设P1,P2,Pm为m种性质，S中每个物品可以具有或不具有这些性质，设Ai=x:xS且x具有性质Pi，i=1,2,m定理6.1.1S中不具有P1,P2,Pm中任何一种性质的物品的个数为其中第一个是对1,2,m的所有1-组合i求和；第二个是对1,2,m的所有2-组合i,j求和；第三个是对1,2,m的所有3-组合i,j,k求和；.，如此类推。,6.1容斥原理,证每个不具有P1,P2,Pm中任何一种性质的物品对等式右边贡献的净值为1-0+0-+(-1)m0=1每个具有P1,P2,Pm中任何n种(1nm)性质的物品对等式右边贡献的净值为C(n,0)-C(n,1)+C(n,2)-+(-1)mC(n,n)=(1-1)n=0,6.1容斥原理,推论6.1.2S中具有P1,P2,Pm中至少一种性质的物品的个数为|A1A2Am|=|Ai|-|AiAj|+|AiAjAk|+-(-1)m|AiAjAm|若容斥原理中集合Ai1Ai2Aik的大小只依赖于k的大小，不依赖于集合中有哪些元素，即存在常数0,1,m使得,6.1容斥原理,0=|S|=|S|，1=|A1|=|A2|=|Am|，2=|A1A2|=|A1A3|=|Am-1Am|m=|A1A2Am|,则容斥原理简化为=0-C(m,1)1+C(m,2)2-+(-1)kC(m,k)k+(-1)mm,6.1容斥原理,例求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图像的排列数。解：设A为ace作为一个元素出现的排列集，B为df作为一个元素出现的排列集，AB为同时出现ace、df的排列数。|A|=4!,|B|=5!,|AB|=3!根据容斥原理，不出现ace和df的排列数为：=6!-(5!+4!)+3!=582,6.1容斥原理,例求从1到500的整数中能被3或5除尽的数的个数。解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合则,6.1容斥原理,被3或5除尽的数的个数为|AUB|=|A|+|B|-|AB|=166+10033=233,例求由a、b、c、d四个字母构成的n位符号串中，a、b、c皆至少出现一次的符号串数目。解令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是3n，即|A|=|B|=|C|=3n|AB|=|BC|=|CA|=2n|ABC|=1,6.1容斥原理,a，b，c至少出现一次的n位符号串集合即为,=4n-(|A|+|B|+|C|)+(|AB|+|BC|+|CA|)-|ABC|=4n-33n+32n-1,6.1容斥原理,例用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。,6.1容斥原理,解：所有排列中，令：A1为出现dog的排列的全体；A2为出现god的排列的全体；A3为出现gum的排列的全体；A4为出现depth的排列的全体；A5为出现thing的排列的全体；,6.1容斥原理,出现dog字样的排列，相当于把dog作为一个单元参加排列，故|A1|=24!类似有：|A2|=|A3|=24!，|A4|=|A5|=22!由于god,dog不可能在一个排列中同时出现，故：|A1A2|=0类似地：|A2A3|=0，|A1A4|=0,6.1容斥原理,由于gum,dog可以在dogum字样中同时出现，故有：|A1A3|=22!类似有god和depth可以在godepth字样中同时出现，故|A2A4|=20!god和thing可以在thingod字样中同时出现，从而|A2A5|=20!,6.1容斥原理,|A1A5|=0，|A4A5|=19!，|A3A4|=|A3A5|=20!，|A3A4A5|=17!，其余3个或多于3个集合的交集都为空集。故满足要求的排列数为：26!-324!-222!+22!+420!+19!-17!=26!-324!-22!+420!+19!-17!,6.1容斥原理,求多重集T=n1a1,n2a2,nkak的r-组合，若非所有ni皆等于1或皆r时如何求？例求多重集T=3a,4b,5c10-组合数。解：设T*=a,b,c,S为T*的全体10-组合的集合，A1为T*的含有多于3个a的10-组合的集合，A2为T*的含有多于4个b的10-组合的集合，A3为T*的含有多于5个c的10-组合的集合。,6.2具有重复的组合,=|S|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)-|A1A2A3|容易求出，|S|=C(10+3-1,10)=66而A1与T*的6-组合数相等(从A1的任一组合中去掉4个a即得6-组合)。故|A1|=C(6+3-1,6)=28,，最后求得=66-(28+21+15)+(3+1+0)-0=6,6.2具有重复的组合,即为所求，由容斥原理，,例求方程x1+x2+x3+x4=18的满足1x15,-2x24，0x35，3x49的整数解的个数。解作变量代换y1=x1-1,y2=x2+2,y3=x3,y4=x4-3,则问题变成求方程y1+y2+y3+y4=16的满足0y14,0y26，0y35，0y46的整数解的个数。,6.2具有重复的组合,设S为方程y1+y2+y3+y4=16的所有非负整数解的集合，A1、A2、A3、A4分别为满足y15,y27,y36,y47的非负整数解的集合。则所求答案为：,6.2具有重复的组合,n个元素依次给以标号1，2，n。n个元素的全排列中，求每个元素都不在自己原来位置上的排列数。设Ai为数i在第i位上的全排列的集合，i=1,2,n，有：|Ai|=(n-1)!，i=1,2,n，同理|AiAj|=(n-2)!，i、j=1,2,n，ij,6.3错位排列,每个元素都不在原来位置的排列数为,=n!C(n,1)(n-1)!,6.3错位排列,+C(n,2)(n-2)!-C(n.n)1!,1,2,n的错排数记为Dn定理6.3.1Forn1，,Dn,e-1=1-1/1!+1/2!-1/3!+1/4!-=Dn/n!+(-1)(n+1)/(n+1)!+(-1)(n+2)/(n+2)!+e-1与Dn/n!的差别小于1/(n+1)!，对n7，e-1与Dn/n!在小数点后三位以内都是相等的。Dn是最接近n!/e的整数。例10位球迷在球队进球时欢呼着将帽子抛向空中，一阵风将帽子吹乱，每位球迷只好随机地捡回一顶帽子。则每位球迷都没有捡到自己帽子的概率是D10/10!e-1,6.3错位排列,Dn满足递归关系：Dn=(n-1)(Dn-2+Dn-1),(n=3,4,5,)D1=0,D2=1证明：考虑n3，1,2,n的错排分成(n-1)组，分别对应2,3,n放在第1个位置的错排。当i(i=2,3,n)放在第1个位置时的错排数：a)第i个位置放1，错排数为Dn-2；b)第i个位置不放1，错排数为Dn-1；,6.3错位排列,递归关系可重写为：Dn-nDn-1=-Dn-1-(n-1)Dn-2,n3=(-1)2Dn-2-(n-2)Dn-3=(-1)n-2D2-2D1=(-1)nDn=nDn-1+(-1)n,n=2,3,4,对照两个关于阶乘数的递归公式：n!=(n-1)(n-2)!+(n-1)!)，n=3,4,5n!=n(n-1)!n=2,3,4,6.3错位排列,例n位男士和n位女士参加舞会，有多少种方式搭配舞伴？如果在第一支舞跳完后，要求所有人跳第二支舞时必须换舞伴，跳第二支舞时又有多少种方式搭配舞伴?答案：n!，Dn,6.3错位排列,例在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来位置上的错排数目。解：8个字母的全排列中，令A1,A2,A3,A4分别表A,C,E,G在原来位置上的排列，则错排数为：,=8!C(4,1)7!+C(4,2)6!C(4,3)5!+C(4,4)4!=24024,6.3错位排列,例求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列数。,解：8个字母中只有4个不在原来位置上，其余4个字母保持不动，相当于4个元素的错排，其数目为,6.3错位排列,故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)9=630,6.3错位排列,6.4带有禁止位置的排列,n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行(列)中有且仅有一个棋子。,x,x,x,x,x,如图所示的布局对应于排列41352。,1棋子多项式,6.4带有禁止位置的排列,可以把棋盘的形状推广到任意形状：,布子规定称为无对攻规则，棋子相当于象棋中的车。令rk(C)表示k个棋子布到棋盘C上的方案数。如：,6.4带有禁止位置的排列,r1()=1，,r1()=2，,r1()=2，,r2()=0，,r2()=1。,为了形象化起见，（）中的图象便是棋盘的形状。,定义设C为一棋盘，称R(C)=rk(C)xk为C的棋盘多项式。规定r0(C)=1，包括C=时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有rk(C)=rk1(Ci)rk(Ce)，,6.4带有禁止位置的排列,6.4带有禁止位置的排列,即对任一指定的格子，要么布子，所得的方案数为rk1(Ci)；要么不布子，方案数为rk(Ce)。,设C有n个格子，则r1(C)nr1(C)r0(Ci)+r1(Ce)，r1(Ce)n1r0(Ci)1故规定r0(C)1是合理的,6.4带有禁止位置的排列,从上可得R(C)=rk(C)xkrk1(Ci)+rk(Ce)xk=xrk(Ci)xk+rk(Ce)xkxR(Ci)+R(Ce)(1),k=0,k=0,k=0,k=0,例如：,R()=1+x；,R()=xR()+R()=x+(1+x)=1+2x；,R()=xR()+R()=x(1+x)+1+x=1+2x+x2,6.4带有禁止位置的排列,6.4带有禁止位置的排列,如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：rk(C)=ri(C1)rki(C2),i=0,k,故R(C)=(ri(C1)rki(C2)xk=(ri(C1)xi)(rj(C2)xj),j=0,n,n,k,n,i=0,i=0,k=0,R(C)=R(C1)R(C2)(2),6.4带有禁止位置的排列,利用(1)和(2)，可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。,例R()=xR()+R()=x(1+x)2+(1+2x)2=1+5x+6x2+x3,*,R()=xR()+R()=1+6x+10 x2+4x3,6.4带有禁止位置的排列,2有禁区的排列,例设对于排列P=P1P2P3P4，规定P13，P1、4，P2、4，P42。,1234,P1,P2,P3,P4,1,2,43,143,2,23,4,3,12,14,这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。,定理设ri为i个棋子布入禁区的方案数，i=1,2,3,n。有禁区的布子方案数（即禁区内不布子的方案数）为,r0n!r1(n1)!r2(n2)!(1)nrn(1)krk(nk)!,k=0,n,证设Ai为第i个棋子布入禁区，其他棋子任意布的方案集，i=1,2,3,n。,6.4带有禁止位置的排列,6.4带有禁止位置的排列,则所有棋子都不布入禁区的方案数为A1A2Ann！(1)kAi,I(n,k),n,iI,k=0,而Ai正是k个棋子布入禁区，其他n-k个棋子任意布的方案数。由假设可知等于rk(nk)！(注意：布入禁区的棋子也要遵守无对攻规则）.所以A1A2An=n!+(1)krk(nk)!,I(n,k),iI,k=0,n,上例方案数为4!6(41)!11(42)!7(43)!1(44)!4,例1，2，3，4四位工人，A，B，C，D四项任务。条件如下：1不干B；2不干B、C；3不干C、D；4不干D。问有多少种可行方案？,6.4带有禁止位置的排列,6.4带有禁止位置的排列,解由题意，可得如下棋盘：,其中有影线的格子表示禁区。,ABCD,1234,R()=1+6x+10 x2+4x3,方案数=4!6(41)!+10(42)!4(43)!+0(44)!=4,6.4带有禁止位置的排列,例再论错排问题错排问题对应的是nn的棋盘的主对角线上的格子是禁区的布子问题。,C=,R(C)=(1+x)n=()xk令rk=(),n,k=0,n,k,n,k,故R(C)中的xn:n!+(1)k()(nk)!=n!(1)k=Pn,k=1,n,n,k=0,k!,1,k,n,8个男生每天排成一队去散步，除第一个人以外，每个人看到前面一个人的后脑勺。第二天他们不愿意还是看着昨天那个人的后脑勺，问有多少种方式重新排队？设Qn为1,2,n的排列中不出现12,23,(n-1)n中任何一个的排列数。,6.5另外的禁排位置问题,定理6.5.1Forn1Qn=n!-C(n-1,1)(n-1)!+C(n-1,2)(n-2)!-C(n-1,3)(n-3)!+(-1)n-1C(n-1,n-1),6.5另外的禁排位置问题,证设Aj(j=1,2,n-1)为1,2,n的排列中出现了j(j+1)的排列的子集。则,|Aj|=(n-1)!|AiAj|=(n-2)!|Ai1Ai2Aik|=(n-k)!而Qn=|A1A2An-1|可以证明Qn=Dn+Dn-1，(n2),6.6反演,基本想法：an易算，bn难算，an可用bn表示，利用反演，将bn用an表示,二项式反演,引理,6.6反演,证,6.6反演,定理,证,推论,证在定理中bk处用(1)kbk代入，即可,例n!=()Dnk，Dn=bn，令nk=l，则n!=()DlDn=(1)n-k()k!=n!(1)n-k=n,nk,nk,nk,1(nk)!,k=0,k=0,k=0,n,n,n,(1)kk!,6.6反演,6.6反演,Mbus反演,定义设nZ+1，若n=1;(n)=0，若n=p11p22pkk存在i1(1)k，若n=p1p2pk如(30)=(235)=(1)3(12)=0；,定理设nZ+则(d)=,1，若n=1；,0，若n1；,d|n,证若n=1，(d)=(1)=1,成立若n1，设n=p11p22pkk，n=p1p2pk(d)=(d)=(pi)+(1)=1+()(1)j=(11)k=0,d|n,d|n,d|n,j=1,k,iI,I(k,j),kj,j=1,k,6.6反演,6.6反演,推论(n)=n,证n=n=n1+(1)j(pi)1=n(1)=(n),1pi,j=1,i=1,k,k,I(k,j),iI,6.6反演,定理(Mbus反演定理)设f(n)和g(n)是定义在正整数集合上的两个函数f(n)=g(d)=g()(M1)g(n)=(d)f()=()f(d