组合数学讲义3

1,Combinatorics(第三讲),2,2,CountingofElementsinaSet,加法原理的另一表达形式：若一个事件可通过n种方式来完成，其中第i种方式有ki种方法，则完成该事件的方法总数为k1+k2+ki+kn。加法原理/和则总结:A、B为两个有限不交集，则有：AB=A+B.同时还成立下列公式:AB=AAB,AB=A+BAB,AB=A+B2ABABminA,B,3,3,乘法原理（积则）,若某个事件可以分n步来完成，第一步有k1种方法可选，第二步有k2种方法可选，第n步有kn种方法可选，则完成此事件的方法总数为k1k2kn。Brualdi的乘法原理表述：令S是元素的序偶(a,b)的集合，其中第一个元素a来自大小为p的一个集合，而对于a的每个选择，元素b存在着q种选择。于是，S的大小为pq，即S=pq。Brualdi的加法原理表述：设集合S划分为部分S1、S2、Sm，则S的元素的个数可以通过找出它的每一个部分的元素个数来确定，即有S=S1+S2+Sm(S有穷),4,排列组合基础,5,5,全排列,r个物体的全排列方法数P(r,r)=r!（第一个位置有r种选择，第二个位置有r-1种选择（第一个位置被选中的不能再选），第三个位置有r-2种选择（第一、二位被选中的不能再选），第k+1个位置有r-k种选择（前面被选中的k个不能再选），最后一个位置只能有1种选择，（前面r-1位置已将r-1个都选走了不能再选，故只有1种选择），于是按乘法原理，r个物体的全排列方法数P(r,r)=r*(r-1)*(r-2)*3*2*1=r!,6,6,全排列,r个物体的全排列方法数P(r,r)=r!（换一种视角）用数学归纳法。k=1(一个物体)时只有一种排法，P(1,1)=1!。设kn-1时有P(k,k)=k!，再看k=n时：n个物体的全排列，可视为：取定一个物体（如第3个或其它任意一个，但取定），再把该物体插入到其余n-1个物体的排列中去；此n-1个物体的排列方法数按归纳法假设有P(n-1,n-1)=(n-1)!，而取定的这个物体插入一个n-1排列有n种方法（第一位之前，一、二位之间，二、三位之间，第n-1位之后）于是按乘法原理，n个物体的全排列方法数P(n,n)满足：P(n,n)=P(n-1,n-1)*n=n!,7,7,排列、组合等式,n个物体中取r个进行排列的方法数P(n,r)=n!/(n-r)!第一个位置有n种选择，第二个位置有n-1种选择，第三个位置有n-2种选择，第r个位置有n-(r-1)种选择，故按乘法原理，P(n,r)=n*(n-1)*(n-2)*(n-r+1)，由于(n-r)!/(n-r)!=1，于是n*(n-1)*(n-2)*(n-r+1)=n*(n-1)*(n-2)*(n-r+1)*(n-r)!/(n-r)!)=n!/(n-r)!用C(n,r)记从n个物体中取r个的方法数，则有P(n,r)=C(n,r)*P(r,r)（从n个物体中取r个进行排列，可看成：先从n个物体中取出r个，再对取出的r个进行全排列）于是有C(n,r)=P(n,r)/P(r,r)=(n!/(n-r)!)/r!=n!/(n-r)!r!。,8,8,C(n,r)=C(n-1,r)+C(n-1,r-1),已知C(n,r)=n!/(n-r)!r!求证组合等式C(n,r)=C(n-1,r)+C(n-1,r-1)。当然可以套用C(n,r)=的表达式：C(n-1,r)=(n-1)!/(n-1-r)!r!，C(n-1,r-1)=(n-1)!/(n-1-r+1)!(r-1)!=(n-1)!/(n-r)!(r-1)!通过对两表达式进行通分来证明C(n,r)=C(n-1,r)+C(n-1,r-1)。但此式亦可从组合角度进行解释。如何解释？（看问题的角度在解组合数学问题时是非常重要的）,9,9,C(n,r)=C(n-1,r)+C(n-1,r-1),从n个物体中取r个，取法总数按定义为C(n,r)。把所有的取法按其中是否有a1分为两类：1、含有a1的取法；2、不含有a1的取法。1、含有a1的取法：a1已取定，只需从剩下n-1个中取r-1个，加上a1就成为n个物体中取r个的一种取法。所以此类情况的取法总数是C(n-1,r-1)。2、不含有a1的取法：可以取的只能是剩下的n-1个物体，在这n-1个物体中取r个，取法总数是C(n-1,r)。从n个物体中取r个，只有以上两类取法，所以有：C(n,r)=C(n-1,r)+C(n-1,r-1),10,10,组合计数举例,n边凸多边形，每两个顶点可连一条线，于是有C(n,2)条直线，去除n条边外，其余C(n,2)-n条线构成凸多边形的对角线，设所有对角线的交点均不重合，问这些对角线被分割为多少条线段？分析：因无重合的交点，故每个交点恰对应于4个顶点；反之，任取4个顶点，可作出一个交点（由凸多边形的性质保证），且如4个顶点不全相同，作出的交点也不同（交点不重合）。故一个4顶点集与一个交点1-1对应。n边凸多边形共有C(n,4)个4顶点集，故交点亦有C(n,4)个。,11,11,组合计数举例,一条对角线上如有k个交点，则该条线被割为k+1段，设有p条对角线（p=C(n,2)-n），并设第1、2、。p条线上各有k1，k2，。kp个交点，则线段总数为i=1p(ki+1），又因为每个交点在两条线上均被计数一次，故有i=1pki=交点数的2倍=2*C(n,4)，于是线段总数为i=1p(ki+1）=2*C(n,4)+p=2*C(n,4)+C(n,2)-n解法2：每增加一个交点，将使相交的两条线各增加一条线段。原先有C(n,2)-n条对角线，而一个交点使线段数增2，因交点共有C(n,4)个，故线段数为C(n,2)-n+2C(n,4)。,12,12,组合计数举例,仓库有若干把锁，由3人轮守，每人带有其中部分锁的钥匙。规定任意2人必须能开仓库，而任一人至少有一把锁不能开。问至少需要多少把锁、每人需备几把锁的钥匙？设三人分别为甲、乙、丙。甲、乙2人所缺的钥匙必不同，（否则，甲、乙在一起时门仍不能开）。同理，甲与丙、乙与丙所缺钥匙也必不同。故至少有3把锁。设3把锁为A、B、C，可按下法分配钥匙：甲：A、B；乙：B、C、丙：A、C这样，组合甲、乙、甲、丙、乙、丙都能打开。此问题可再复杂化一点。,13,13,组合计数举例,金库门有若干把锁，由11人轮守，每人带有其中部分锁的钥匙。规定任意6人必须能开金库，而任意5人则有一把锁不能开。问金库门至少需要多少种锁、每人至少带多少种钥匙。分析：任意两个5人组A与5人组B，打不开的锁一定不同（否则就至少有一个6人组不能打开门）。由于共有C(11,5)(=462)个5人组，故至少必须有462把锁。当X与不含X的5人组相聚时（此时恰有6人），必须能打开门，即X必须具有该组所缺的钥匙，而不含X的5人组共有C(10,5)(=252)个，据上述，不同的5人组所缺的钥匙不同，故X必须至少带有252把钥匙。（每把锁配6把钥匙）作业：试编一个程序，给每个人分配不同的252把钥匙。,14,14,组合应用校验码,考虑长度为n的二进序列，每个序列可以代表一个信息，这样一共可以有2n个序列对应于2n个信息。由于代码在传输时有可能出错，这样信息就会发生混淆。为能够检测出传输所导致的错误，首先引进了奇偶校验码前n-1位表达信息，而最后一位用来进行校验：根据前n-1位中1（或0）的奇偶性，最后一位加1或加0。Eg:偶校验：最后一位加1或加0使得序列中1的个数为偶数。如果接收到的序列有奇数个1，说明其在传输过程中有误。传输过程中有奇数个错误可查出，但偶数个错误查不出。,15,15,组合应用r纠错码,原因是用于校验的信息不够充分。可以增加信息冗余量，以提高发现传输错误的能力，但有效信息必然将减少。需要做权衡，只在必要时使用有较多冗余信息的纠错码。1968年图灵奖得主RichardW.Hamming提出了r纠错码。码的概念：长度为n的二进制序列（显然有2n个）。码字的概念：长度为n的二进制序列中选出p个作为有效码，其余的均为错误码。Eg：对于三位的二进制序列，只选000和111作为有效码（码字），其余皆为错误码。为什么要这样取？这样取能带来什么样的好处？,16,16,组合应用r纠错码,R.W.Hamming提出码间距离的概念。两个码的距离：对两个码（n位二进制序列）逐位比对，若有k个位不同，则两码的距离为k。Eg：000与111的距离为3，000与100、010、001的距离为1，与110、011、101的距离为2，而码字111与前3个的距离为2，与后3个的距离为1。r纠错码：一组码字的集合，其中任意两个码字的距离2r+1.Eg：码字000与111的距离为3=2*1+1，所以它们是1纠错码。,17,17,组合应用r纠错码,一个公度d(x,y)要成为距离须满足3个条件：1.a有d(a,a)=0;2.a,b有d(a,b)=d(b,a);3.a,b,c有d(a,b)+d(b,c)d(a,c)。r纠错码的使用：任取一个码（n位二进制序列）与p个码字逐一比对，只要该码与码字a的距离r，则认为该码是a。如100、010、001与000的距离为1，所以它们都被认为是000；110、011、101与111的距离为1，所以它们都被认为是111。由于距离的第3条性质（a,b,c有d(a,b)+d(b,c)d(a,c)），任一个错误码不可能同时被认作两个不同的码字。这样，任何错误不超过r位的码都可以被纠正过来。,18,18,组合应用r纠错码,被认为是码字a的错误码究竟有多少个？1、有1位错误（与a距离为1）的码，共有C(n,1)个；2、有2位错误（与a距离为2）的码，共有C(n,2)个；。r、有r位错误（与a距离为r）的码，共有C(n,r)个。于是，属于码字a的错误码共有C(n,1)+C(n,2)+C(n,r)个；加上a自身，共有C(n,0)+C(n,1)+C(n,2)+C(n,r)个属于码字a因此，码字总数不可能超过2n/k=0rC(n,k)即2n/(C(n,0)+C(n,1)+C(n,2)+C(n,r)个（码字最大数）。,19,19,组合应用r纠错码,最少可以选出多少个码字？令E=所有的n位二进制序列在E中任取一个序列a1作为码字，并令A1=所有与a1距离小于等于2r的n位二进制序列因此，A1=k=02rC(n,k)。注意A1中有些不一定看做a1。之后在E-A1中再取一个序列a2也作为码字,则d(a1,a2)2r+1。再令A2=所有与a2距离小于等于2r的n位二进制序列，则A2=k=02rC(n,k)，但注意A1与A2的交集不一定为空。无论如何，有A1A22k=02rC(n,k)。在E-(A1A2)中再任取一个序列a3也作为码字，则有d(a1,a3)2r+1，d(a2,a3)2r+1。,20,20,组合应用r纠错码,最后，当A1A2Ap=E时，则挑选码字的工作结束。按上述分析，挑选出的任意两个码字的距离d(ai,aj)2r+1，（当ij时）所以这一组码字是r纠错码。由于2n=E=A1A2App*k=02rC(n,k)故有p2n/k=02rC(n,k)，即码字至少有2n/k=02rC(n,k)个,21,21,组合应用二元群码,二元群码定义：任意两个码字做运算，其结果仍然是码字。Eg：1101110101=01110，1010101110=11011，1101101110=10101，再加上00000，构成一个码字集合。定理：码字集合连同二元运算构成一个群。（00000为运算的幺元，每个码字运算逆元是其自身）定理：码字表达的任一列要么全为0，要么0、1各占一半。证：设两序列b1b2，则有ab1ab2。否则，若ab1=ab2，则有aab1=aab2，于是b1=b2,矛盾。,22,22,组合应用二元群码,若第i列中0、1个数不等，不失一般性设n1n0。设n1个码字（第i位为1的码字）是a1,a2,an1(互不相同)，于是a1a1,a1a2,a1an1也都是互不相同的码字，且这些码字的第i列均为0，即i列为0的码字至少有n1个,矛盾。于是知所有码字中“1”的个数不超过n*码字数/2。（若n0n1，则选一个第i列为1的码字与这n0个码字运算）r纠错二元群码中最多能有多少个码字？,23,23,组合应用二元群码,r纠错二元群码中最多能有多少个码字？（设A(r)为码字数）首先，全0序列必在群码中（因为任一码字有aa=）；且对任一码字a，需满足d(a,)2r+1，所以a至少有2r+1个1。由于除了以外还有A(r)-1个码字，于是这些码字至少有(2r+1)(A(r)-1)个1。又由于共有n列，且每列1的个数不超过一半即A(r)/2，故有(2r+1)(A(r)-1)所有码字中1的个数n*A(r)/2，此式化简得A(r)2*(2r+1)/(4r+2-n),24,24,乘法原理应用举例,问：在1300中任取3个数，其和能够被3整除的情况有多少种？分析：把300个数分为3组：1，4，7，。，298，2，5，8，。，299，3，6，9，。，300，3个数的取数可分为3类：第1类：3个数均取自同一个组；第2类：3个组中各取1个数；第3类：某组中取2个加它组1个。第1类：同一组中任取3个，则其和必然能被3整除，此类方法数为3*C(100,3);第2类：3个组中各取1个，其和亦能被3整除，此类方法数有1003;第3类：某组中取2个加它组1个，则其和必然不能被3整除，舍弃。于是总的方法数为3*C(100,3)+1003。,25,25,乘法原理应用举例,设有t种物体，第1种有q1个，第2种有q2个，。第t种有qt个，总共有q1+q2+。+qt=n个物体；则从中取1个、2个、。、n个物体的取法总数为：(q1+1)(q2+1)。(qt+1)-1（换一种角度看）Eg：t=4，每种取法可以对应于一个有序4元组(a1,a2,a3,a4)，满足条件0aiqi(i=1,2,3,4),不同取法对应于不同4元组。如（0,0,1,0）是取1个的取法中的一种（第3种物体取了1个）；（2,1,0,2）是取5个的取法中的一种（第1种物体取了2个，第2种物体取了1个，第3种物体未取，第4种物体取了2个）；由此推广到一般，取法的总数就相当于满足条件0aiqi的有序t元组的个数，其中要去掉（0,0,0,0）即一个也不取的情况。,26,26,乘法原理应用举例,任给一个正整数n（非素数），问它有多少个正整数因子？分析：任一个非素数的正整数n，都可以写成其素因子乘积形式Eg：1400=2*2*2*5*5*7=23*52*71故1400的正整数因子，均可表达为2i*5j*7k的形式(其中i3，j2，k1，i,j,k0，i,j,k均为0时相当于因子1)。故按乘法原理，1400的正整数因子有(3+1)(2+1)(1+1)=24个。因此，一般而言，若一个非素数的正整数n=P1i1*P2i2*.*Ptit(其中P1,P2,.Pt均为素数，i1,i2,it为非负整数),则n恰有(i1+1)(i2+1)(it+1)个正整数因子。,27,27,乘法原理应用举例,不同的n元真值函数共有多少个？分析：任一个n元真值函数，其自变量共有2n个n元组。如n=3，则作为自变量的3元组(x,y,z)共有23=8种情况：(0,0,0)，(0,0,1)，(0,1,0)，(0,1,1)，(1,0,0)，(1,0,1)，(1,1,0)，(1,1,1)。任一个3元真值函数，均要为此8个3元组指定0或1。考察此种指定的方法数：(0,0,0)可指定0或1，(0,0,1)可指定0或1，。(1,1,1)可指定0或1。8个3元组，每个3元组均有两种选择，故不同的3元真值函数有28个，不同的n元真值函数有22n个。,28,2变量的真值函数有16(222)个,pqqp,pq(pq),pq(pq)f0(p,q)F,f3(p,q)p,f5(p,q)q,f10(p,q)q,f12(p,q)p,f15(p,q)T,29,29,乘法原理应用举例,设有n种重物，重量依次为1、2、4、8。，2n-1，已知：从n种重物中任取p个重物都构成一种不同的重量(p=1,2,.n)，问总共可以取出多少种不同的重量？当然用组合计数可以很容易得到C(n,1)+C(n,2)+C(n,3)+。+C(n,n)=2n-1（因为(1+x)n=C(n,0)+C(n,1)x+C(n,2)x2+C(n,3)x3+。+C(n,n)xn(二项式定理)，令x=1即得）但也可以作如下考虑：对每一种取法逐一考察n种重物，每种重物可以有取与不取两种选择，从而构成一个以0、1为分量的n元组；如n=3，(0,1,1)表示取第2、3个重物，第1个不取。这样的n元组共有22。2（n个2连乘）=2n，再去掉一个也不取所对应的(0,0,0)，得总数为2n-1。,30,30,乘法原理应用举例,重量为1、2、4、8。，2n-1的情况可以推广。设重物w1Si-1=k=1i-1wk，即第i个重物的重量，比前i-1个重物之和还要重。这样就有：任意两种取重物的方法，所得的重量之和必不相同。因为：若A组最重的重物wk重于B组中最重的重物，则B组中其它重物之和，由前提小于wk的重量。故A、B组的重量不同。若A、B组最重的重物均相同，则由重到轻考察，不失一般性，设wk是第一个A组有B组没有的重物，于是B组中其余重量轻于wk的重物之和，由前提小于wk的重量。故A、B组的重量不同。故总共可以得到2n-1种重量（按每个重物取与不取考虑）。,31,31,乘法原理应用举例,称重问题：有n个不同的砝码，问最多能称多少种重量？其次，要满足什么条件，才能达到这个最大值？分析：任一个砝码可以：1、放在砝码盘中；2、放在重物盘中；3、不放在任一盘中。按乘法原理，这n个砝码共有3n-1种放法。但这3n-1种放法并不是都可以称重：当砝码盘中所有砝码的重量之和轻于重物盘中所有砝码的重量之和时，该格局不能称重。如果出现上述情况，则把重物盘中的砝码与砝码盘中的砝码互换，则此时的格局就是可称重的格局。于是可称重格局与不可称重格局1-1对应。如可称重的重量互不相同，则总共有(3n-1)/2个不同重量(格局)。满足什么条件才能达到(3n-1)/2这个最大值呢？,32,32,乘法原理应用举例,要满足什么条件？只要砝码满足w12*Si-1=2*k=1i-1wk，则最大值(3n-1)/2可以达到。(保证了两个不同的可称重格局所称重量必不同)考察任两个不同的可称重格局A、B，从最重的开始逐一检查两格局砝码盘中的砝码，不失一般性，设wi是第一个遇到的A砝码盘中有而B砝码盘中没有的那个最重的砝码（必然有这样的砝码，否则两格局就完全相同了）；于是知格局B砝码盘中尚未比过的那些砝码重量均小于wi，而这些砝码最多能称重Si-1=k=1i-1wk，（一般达不到，因为w1,w2,wi-1不一定都在砝码盘中而不在重物盘中，如都在砝码盘中时可称到此最大值）而格局A中仅wi的重量就大于2*Si-1，即使w1,w2,wi-1均放在重物盘中，wi能称的重量也大于Si-1，故格局A的称重大于格局B的称重。于是有：如满足条件，任两个不同的可称重格局所称重量一定不同。,33,钥匙问题编程举例,金库门有若干把锁，由5人轮守，每人带有其中部分锁的钥匙。规定任意3人必须能开金库，而任意2人则有一把锁不能开。金库门至少需要C(5,2)(=10)把锁、每人带C(4,2)(=6)把钥匙。编一个程序给每个人分配不同的6把钥匙。共5*6=30把钥匙。开门的组合（5人任取3人）共有C(5,3)(=10)种方式。用一长为10*5的二维数组A记录每个组合（如：第4种组合的参加者为1、3、4，则在A4,1、A4,3、A4,4中作标记。标记完毕后，5列中的每列（对应1人）恰好有C(4,2)个标记。（含某人的3人组合，去掉该人为2人，故此类组合有C(4,2)种）C(5,3)(=10)种组合，每个组合对应一把锁，在此组合中的人（三人已作标记）配该锁的钥匙。（注意：C(5,2)=C(5,3)）,34,34,圆排列,每个圆排列（设按逆时针序）如断开，则可得一个全排列。首先，不同的圆排列断开后所得全排列必不相同（否则连起来后就得到相同的圆排列，矛盾）。其次，每个圆排列（有n个数）可以在n个点处断开，而此n种断开方法所得的全排列是互不相同的（即一个圆排列对应于n个全排列）。且有：任一普通全排列必含于某个圆排列中（连起来即得）。设不同的圆排列有k个，于是有k*n=n!，故k=(n-1)!,35,35,圆排列,方法2选一个特定物体作为第一个，在圆排列（逆时针序）中的其余n-1个物体的排列就对应于它们的一个普通全排列；反之，任给一个n-1个物体（不含特定物体）的普通全排列，把特定物体加在该普通全排列的最前面并将其连接，就得到一个圆排列，且不同的普通全排列按此法得到的圆排列是不同的，即圆排列与n-1个物体(不含特定物体)的普通全排列1-1对应，故不同圆排列的个数为(n-1)!,36,36,多重排列,设有q1个A1,q2个A2,qk个Ak，每类中的物体视为相同，且有q1+q2+qk=n。将这n个物体排成一列，则不同的排法共有n!/(q1!q2!qk!)n个物体排成一列，共有n个位置。先定q1个A1类物体的位置。n个位置中的q1个放A1类物体，相当于将这q1个位置涂上A1色，位置可以是n个中任何q1个，方法数为C(n,q1)=n!/(n-q1)!q1!;接着在余下n-q1个位置中选择q2个放A2类物体（涂上A2色）方法数为C(n-q1,q2)=(n-q1)!/(n-q1-q2)!q2!，再在余下n-q1-q2个位置中选择q3个放A3类物体（涂上A3色），,37,37,多重排列,方法数为C(n-q1-q2,q3)=(n-q1-q2)!/(n-q1-q2-q3)!q3!按乘法原理，不同的排法共有(n!/(n-q1)!q1!)*(n-q1)!/(n-q1-q2)!q2!)*(n-q1-q2)!/(n-q1-q2-q3)!q3!)*(n-q1-q2-q3)!/(n-q1-q2-q3-q4)!q4!)*(n-q1-qk-1)!/(n-q1-qk-1-qk)!qk!)=n!/(q1!q2!qk!)方法2：先把每个物体注上标记，使之互不相同，则排法共有n!种。每一个不可辨排法对应于q1!q2!qk!种可辨排法，而任一可辨排法去掉标记后恰对应于一个不可辨排法，故不可辨排法的方法数为两者之商：n!/(q1!q2!qk!),38,38,多重排列应用,证明：(p!)!能够被(p!(p-1)!)整除。设有p!个物体，分为(p-1)!类，每类有p个。对照多重排列（q1+q2+qk=n，不同的排法共有n!/(q1!q2!qk!)）k=(p-1)!，q1=q2=q(p-1)!=p，q1+q2+q(p-1)!=p!，即n=p!。此情况下的不同排法共有(p!)!/(p!p!p!)（p!共有(p-1)!个）即为(p!)!/(p!(p-1)!)该方法数当然是一正整数，故(p!)!能够被(p!(p-1)!)整除。,39,39,可重排列,可重排列定理：n个元素可重复地选r个进行排列，方法数为nrr个位置中的每个位置都可有n种选择，再用乘法原理。（注意与多重排列的区别：多重排列中每类物体的个数是有限的）Eg：11010中，有多少个数含有1，多少个数不含有1？先看不含有1的数：每个数位只有9种选择（1不能选），用可重排列定理，不含有1的数有910-1（去掉0）再看含有1的数：去掉不含有1的数，剩下都是含有1的数。因总共有1010个数，故含有1的数有1010-910+1个。,40,40,可重排列定理应用,n位二进制数中有多少个含偶数个0？（比四进制数简单）分类：无0，2个0，4个0，6个0，。无0：即全1，只有一个（C(n,0)）；2个0：n位中取2位放0，其余位置均放1，有C(n,2)个；4个0：n位中取4位放0，其余位置均放1，有C(n,4)个；。由已证定理：C(n,0)+C(n,2)+C(n,4)+。=C(n,1)+C(n,3)+C(n,5)+。n个中取偶数个的方法数与n个中取奇数个的方法数相同。2n中各占一半，即为2n-1。,41,41,可重排列定理应用,n位二进制数中有多少个含偶数个0？（换一个视角）任一n-1位二进制数都可以对应一个含偶数个0的n位二进制数：若该n-1位二进制数有偶数个0则在其前面加1，若该n-1位二进制数有奇数个0则在其前面加0，如此，每个n-1位二进制数都可对应一个含偶数个0的n位二进制数；且不同的n-1位二进制数所对应的n位二进制数亦不同，即n-1位二进制数与含偶数个0的n位二进制数有一个1-1对应，故两者的个数一样多。而前者的个数恰为2n-1。,42,42,可重排列定理应用,n位二进制数中有多少个含偶数个0？（再换一个视角）任一含偶数个0的n位二进制数都与一个含奇数个0的n位二进制数1-1对应：后n-1位相同、首位不同的恰有2个数，其中一个是含偶数个0的n位二进制数，一个是含奇数个0的n位二进制数，两两配对，于是有：含偶数个0的n位二进制数与含奇数个0的n位二进制数一样多；故两者的个数均为2n/2=2n-1。,43,43,可重排列定理应用,推广：含偶数个0与1的n位四进制数恰好为总数的一半。后n-1位完全相同的有4个数：首位分别是0、1、2、3。将首位是0和2的两个数配对，首位是1和3的两个数配对，于是每对中有一个是含偶数个0、1的，另一个是含奇数个0、1的。将所有n位四进制数按此方法进行配对（首位为0配首位为2，首位为1配首位为3），共形成4n/2对，由于每对中一个是含偶数个0、1的，另一个是含奇数个0、1的；两类数一样多，均为4n/2个。,44,44,可重排列定理应用,再求：含偶数个0、偶数个1的n位四进制数。含偶数个0、偶数个1的n位四进制数必然是含偶数个0与1的n位四进制数。其中仅含有2与3的n位四进制数是共有2n个。而按上题，含偶数个0与1的n位四进制数有4n/2个，这4n/2个中去掉仅含有2与3的，真正含有0或1的有4n/2-2n个。这4n/2-2n个数可分为两类：偶数个0、偶数个1（下称偶偶数）以及奇数个0、奇数个1（下称奇奇数）。再进行配对：,45,45,可重排列定理应用,对每一个奇奇数，从右边往左逐位看，第一次碰到0或1时，原先为0则改为1，原先为1则改为0。于是，一个奇奇数就对应于一个偶偶数。且不难证明，按此方法，不同的奇奇数一定对应于不同的偶偶数。这样，奇奇数与偶偶数就建立了1-1对应，故两者的数目一样多，即均有(4n/2-2n)/2个。偶偶数再加上仅含有2与3的2n个数，含偶数个0、偶数个1的n位四进制数的个数为(4n/2-2n)/2+2n=4n-1+2n-1（对比递推方程求解法）印度程序员VS中国程序员,46,46,无限制可重组合,Th:n种物体，不加限制、可重复地取出r个，取法数为C(n+r-1,r)。不失一般性，用数字1,2,。n来代表这n种物体。任一种取法，取出后可将各数字排成非降序列(a1,a2,.,ar)，即有aiai+1（i=1,2,。r-1），1a1,arn。令(b1,b2,.,br)=(a1+0,a2+1,.,ar+r-1),即bi=ai+i-1,于是有：bi+1-bi=(ai+1+i)-(ai+i-1)=ai+1-ai+11。故有b1b2br即b1,b2,.,br是互不相同的数。于是知：(b1,b2,.,br)也是一种取数法。是在什么范围里取数呢？arn，brn+r-1,另外有1a1=b1,47,47,无限制可重组合,1b1b2brn+r-1,即(b1,b2,.,br)是在1，2，。，n+r-1中选r个不同的数。任给一个非降序列(a1,a2,.,ar)，按bi=ai+i-1（i=1,2,。r），可作出一个严格递增序列(b1,b2,.,br)；反之，任给一个(b1,b2,.,br)（满足条件1b1b2brn+r-1），按ai=bi-i+1（i=1,2,。r），可作出一个非降序列(a1,a2,.,ar)。于是，(a1,a2,.,ar)的取法与(b1,b2,.,br)的取法可以1-1对应，即两者的取法一样多。而(b1,b2,.,br)的取法数为C(n+r-1,r)，故(a1,a2,.,ar)的取法数也为C(n+r-1,r)。,48,48,无限制可重组合,n种物体，不加限制、可重复地取出r个，取法数为C(n+r-1,r)。用加间隔法求解。准备n-1条相同的竖线和r个相同的球。若第一种物体取了k1个，则在左数第一条竖线左边放k1个球；。若第i种物体取了ki个，则在左数第i-1条与第i条竖线之间放ki个球；(若第i种物体未取则第i-1条与第i条竖线之间不放球)。若第n种物体取了kn个,则在左数第n-1条竖线右边放kn个球。如OOOOOO有4条线、6个球，即n=5、r=6，上述格局表示第1种物体取3个，第3种物体取2个，第4种物体取1个，第2、第5种物体不取。,49,49,无限制可重组合,于是，每一种取法可以得到一个由n-1条竖线和r个球所组成的格局，不同的取法对应于不同的格局；反之，有一个格局就可以得到一种取法，不同的格局对应于不同的取法；两者1-1对应。有多少种格局？分析：r个球加n-1条竖线共有n+r-1个位置。在n+r-1个位置中，若n-1条竖线的位置不同，则对应于不同的格局。如r=5，n=3，n+r-1=7，2条竖线的位置为2、4就不同于2、5。位置为2、4：OOOOO；位置为2、5：OOOOOn-1条竖线的位置有多少种选择？在n+r-1个位置中取n-1个故格局数=n-1条竖线的可选位置数C(n+r-1,n-1)=C(n+r-1,r)。,50,50,无限制可重组合,注意:只要每一种物体超过r个，就认为是不加限制的可重复组合，可以应用该定理；若某种物体少于r个（即有一定的限制），则不能应用该定理，而要用其它的方法计算。还要注意的是：格局数与可能发生的事件数是两个不同的概念,格局数是无序的，而可能发生的事件数是有序的。如格局1,2,3可对应事件1-2-3,1-3-2,2-1-3,2-3-1,3-1-2,3-2-1。排列问题中位置是有区别的，而组合问题中没有可区分的位置，因此，一般要把组合问题尽可能变形到可区分的位置问题上去。,51,51,不同物体的分配,设nr，要将r个不同的物体放入n个不同的盒子中，规定每个盒子最多放一个，共有多少种不同的放法？这样考虑：第1个物体有n种选择，第2个物体有n-1种选择，。，第r个物体有n-r+1种选择。于是方法数为：n*(n-1)*(n-2)*.*(n-r+1)=P(n,r)若rn，从r个物体中取出n个，放入盒子中（每盒一个），类似地：放第1个盒子时有r种选择，第2个盒子时有r-1种选择，。，放第n个盒子时有r-n+1种选择。于是方法数为：r*(r-1)*(r-2)*.*(r-n+1)=P(r,n),52,52,不同物体的分配,若每个盒子可放无穷多个，则n、r的大小就无关了：第1个物体有n种选择，第2个物体有n种选择，。，第r个物体有n种选择；因此共有nr种放法。若放入盒子中的次序亦有关系，则这样考虑：将r个物体顺序排好，然后加n-1条竖线间隔，于是就得到1种格局（放法），若n-1条竖线看成是可分辨的，则相当于r+n-1个物体的全排列（方法数为(r+n-1)!），但现在n-1条竖线是不可分辨的，故一个不可分辨的格局对应于(n-1)!个可分辨的格局，于是格局数为(r+n-1)!/(n-1)!即P(n+r-1,n-1)=P(n+r-1,r),53,53,不同物体的分配,解法2：将r个物体放入n个不同的盒子中（次序亦有关系），可这样考虑：r个物体有r!种排法，每一种排法加n-1条竖线间隔就得到1种格局，按前述加间隔的方法数为C(n+r-1,r)，故总的方法数为C(n+r-1,r)*r!=P(n+r-1,r)解法3：第1个物体有n种选择，第2个物体有n+1种选择，（这是因为，第1个物体的放入使得该其所在的盒子增加了一个间隔，即第2个物体可选择放在第1个物体的之前或之后，每增一个物体，间隔就增加一个），。第r个物体有n+r-1种选择，故总的方法数为n*(n+1)*.(n+r-1)=P(n+r-1,r),54,54,不同物体的分配（举例）,有5根旗杆，7面旗子，问有多少种挂旗子的方法。这里n=5，r=7，（7个物体放到5个盒子且顺序有关）分析：第1面旗子有5种选择，第2面旗子有6种选择，（第2面旗子挂在第1面旗子所在的旗杆上时有两种选择在第1面旗子之上或在第1面旗子之下）。第7面旗子有11种选择，故总的方法数为5*6*7*8*9*10*11=P(11,7)=P(n+r-1,r),55,55,多重排列的应用,设第1种物体有q1个,第2种物体有q2个,第k种物体有qk个，每类中的物体视为相同，且有q1+q2+qk=n。要将这n个物体放入n个盒子（每盒一个），有多少种放法？如果能看出每一种放法就相当于将这n个物体排成一列，故由多重排列的结论知不同的排法共有n!/(q1!q2!qk!)类似于多重排列的分析，第1种q1个物体放法选择为C(n,q1)，第2种q2个物体放法选择为C(n-q1,q2)，。最后一种qk个放时，只有n-q1-q2-。-qk-1=qk个位置，只有一种选择，故方法数为C(n,q1)*C(n-q1,q2)*。展开即得n!/(q1!q2!qk!),56,56,多重排列的应用,设第1种物体有q1个,第1种物体有q2个,第k种物体有qk个，每类中的物体视为相同，且有q1+q2+qk=r。即物体是r个而盒子有n个，而rn，将这r个物体放入n个盒子（每盒最多一个），有多少种放法？逐个考虑每种物体放法，第1种q1个物体有C(n,q1)种选择，第2种q2个物体有C(n-q1,q2)种选择，。最后一种qk个放时，有C(n-q1-q2-。-qk-1,qk)种选择。（注意此时有n-q1-q2-。-qk-1qk），方法数为以上各项的乘积：n!/(q1!q2!qk!(n-r)!),57,57,多重排列的应用,设第1种物体有q