第一章 排列组合.ppt

第一章排列组合,主讲教师数学学院魏毅强教授联系电mail:weiyiqiang,2,第一章排列组合,1.1加法法则与乘法法则,1.3Stirling近似公式,1.4模型转换,1.5全排列的生成算法,1.6组合的生成,1.7可重组合,1.8若干等式及其组合意义,1.9应用举例,1.2排列与组合,1.1加法原理与乘法原理,1.2一一对应原理,4,1.1加法法则与乘法法则,加法法则设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。,集合论语言：若|A|=m,|B|=n,AB=,则|AB|=m+n。,例1.1.1书架上有数学类书5本，计算机类书3，任取其中一本，有多少种取法。,共有5+3=8种取法,5,1.1加法法则与乘法法则,乘法法则设事件A有m种产生式，事件B有n种产生方式，则事件A与B有mn种产生方式。,集合论语言：若|A|=m,|B|=n,AB=(a,b)|aA,bB,则|AB|=mn。,例1.1.2从A到B有三条道路，从B到C有两条道路，则从A经B到C有几条道路?,有32=6条,6,例1.1.3机动车牌照字由7个字符组成，第一个字符是汉字，表示省份或军区等，第二个字符是英文字母，表示市、区或行业等，其余5位可选自英文字母或数字（有时用第三个字符表示行业，如出租用T)，问一个市的机动车拥有量最多是多少？,机动车拥有量最多是：(26+10)5辆。,出租车拥有量最多是：(26+10)4辆。,1.1加法法则与乘法法则,7,1.1加法法则与乘法法则,例1.1.4某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是44=16，而只有43=12种。在乘法法则中要注意事件A和事件B的相互独立性。,8,1.1加法法则与乘法法则,例1.1.51)求小于10000的含1的正整数的个数2)求小于10000的含0的正整数的个数,小于10000的正整数可看做4位数,共有1041=9999个（0000除外）不含1的4位数有：9416560个含1的4位数有：99996560=3439个,另:全部4位数有104个,不含1的四位数有94个,含1的4位数为两个数的差:10494=3439个,9,2)“含0”和“含1”不可直接套用。0019(含1但不含0)。在组合的习题中有许多类似的隐含的规定，要特别留神。,不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个,不含0小于10000的正整数有9+92+93+94=(951)/(91)=7380个,含0小于10000的正整数有99997380=2619个,1.1加法法则与乘法法则,10,1.1加法法则与乘法法则,例1.1.6求除尽n=73.112.134的数的个数,除尽n=73.112.134的数可表示为,x=7a.11b.13c,其中,故整除的个数为,1.2一一对应原理,1.2一一对应原理,12,1.2一一对应原理,如我们说A集合有n个元素|A|=n，无非是建立了将A中元与1,n元一一对应的关系。,在组合计数时往往借助于一一对应实现模型转换.,比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。,一一对应原理如果事件A与事件B间存在一一对应（双射），则事件A与B一样大，即|A|=|B|。,13,例1.2.1在65名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？,另一种思路是淘汰的选手与比赛(按场计)集一一对应。淘汰64名选手，需要64场比赛。,1.2一一对应原理,一种常见的思路是按轮计场（费事）：32+16+8+4+2+1+1=64注意，每轮都有一人轮空。,14,例1.2.2设凸n边形的任意三条对角线不共点，求对角线在多边形内交点的个数。,可以先计算对角线的个数，然后计算交点，但是存在在多边形内无交点的情形，比较复杂。,可以考虑对应关系：多边形内交点to多边形四个顶点。,可以证明这是一一对应（映射，单且满）。,1.2一一对应原理,交点的个数：Cn4,1.3排列与组合,1.2一一对应原理,16,1.3排列与组合,定义从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。,排列的全体组成的集合用P(n,r)表示。所有不同排列的个数称为排列数，也记为P(n,r)。或Prn，或Arn。当r=n时称为全排列。所有不同全排列的个数记为Pn或An。,17,1.3排列与组合,从n个中取r个的排列的典型例子是(取球模型):从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种不同选择，第2个有n-1种选择，第r个有n-r+1种选择。故由乘法原理有P(n,r)=n(n-1)(n-r+1)=n!/(n-r)!,18,规定,1.3排列与组合,从n中取出r个排列的模型，可看作是从n个有区别的球中取出r个，放入r个有标记的盒子中，且无一空盒。,特别，当r=n时有,显然,19,例1.3.1由5种颜色的星状物，20种不同的花排列成如下图案：两边是星状物，中间是3朵花，问共有多少种这样的图案？,两边是星状物，从五种颜色的星状物中取两个的排列的排列数是P(5,2)=20,根据乘法法，则得图案数为,20种不同的花取3种排列的排列数是,P(20,3)=201918=6840,206840=136800,1.3排列与组合,20,例1.3.2A单位有7名代表，B单位有3位代表，排成一列合影，如果要求B单位的3人排在一起，问有多少种不同的排列方案。若A单位的2人排在队伍两端，B单位的3人不能相邻，问有多少种不同的排列方案？,B单位3人按一个元素参加排列，P(8,8)P(3,3),A单位的人排法固定后A*A*A*A*A*A*A，B单位第一人有6种选择，第二人有5种，第三人有4种，因此答案为P(7,7)654,1.3排列与组合,21,于是我们只需要计算Si即可。,例1.3.3求由1,3,5,7组成的不重复出现的整数的总和,解：这样的整数可以是1位数,2位数,3位数,4位数,S=S1+S2+S3+S4,S1=1+3+5+7=16,1.3排列与组合,若设Si，i=1,2,3,4，是i位数的总和，则,22,S2=3(1+3+5+7)10+3(1+3+5+7)=480+48=528,S4=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=96000+9600+960+96=106656,S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=9600+960+96=10656,S=16+528+10656+106656=117856,两位数有：13,15,17,31,33,35,37,51,53,55,57,71,73,75,77，所以,同理,1.3排列与组合,23,1.3排列与组合,例1.3.4假设一高速路口有4个出口，现有9辆车子从这4个口下高速，问有多少种不同的下法？,解法一假设出口编号为：K1，K2，K3，K4；9辆车的编号为1,2,3,4,5,6,7,8,9,1号车选择出口有4种；2号车选择就有5种，因为当2号车与1号车选同一出口时，两车有前后顺序的问题；同理3号车有6种选择；依此类推，9号车应有12种选择。故不同的下法共有4*5*6*12=12!/3!,24,1.3排列与组合,解法二如果只有一个出口，则显然9辆车的不同下法为9！；如果有两个出口，则可以加入一个分隔符F与车辆号一起进行排列，在F的左右排列可看作是分别从两个出口的一种下法，故此时的下法为10！。,本题有4个出口，应加入三个分隔符，所以不同的下法有12!/3!.,注意到，分隔标记F是无区别的,25,1.3排列与组合,解法三在9辆车的标号与3个分隔符共同组成的12个标记中，首先选出3个作为分隔符，不同选法有C(12,3)，然后余下的9个作为车辆标号进行排列，应有9!种不同方案，故总的下法有C(12,3)*9!=12!/3!,注意本解法用到了组合的概念，它也可以作为基本的组合模型,26,1.3排列与组合,定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。,组合的全体组成的集合用C(n,r)表示，,所有不同组合的个数记为C(n,r)或Cnr,若球不同，盒子相同，则是从n个不同元素中取r个不重复的组合的模型。,27,若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)r!=P(n,r),即C(n,r)=P(n,r)/r!=,n!r!(n-r)!,1.3排列与组合,28,1.3排列与组合,例1.3.5有5本不同的俄文书，7本不同的英文书，10本不同的中文书。如果从中任取2本1)不同文字的书；2)相同文字的书；3)书问各有多少种不同的取法？,解1)C(5,1)C(7,1)+C(5,1)C(7,1)+C(7,1)C(10,1)=57+510+710=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=(),5+7+102,29,1.3排列与组合,例1.3.6从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？,解将1,300分成3类：A=i|i1(mod3)=1,4,7,298,B=i|i2(mod3)=2,5,8,299,C=i|i3(mod3)=3,6,9,300.要满足条件，有四种解法：1)3个数同属于A;2)3个数同属于B3)3个数同属于C;4)A,B,C各取一数.,故共有3C(100,3)+1003=485100+1000000=1485100,1.4Sterling近似公式,1.2一一对应原理,31,1.4Sterling近似公式,组合计数的渐进值问题是组合论的一个研究方向。Stirling公式给出一个求n!的近似公式，它对从事计算和理论分析都是有意义的。,1)Wallis公式,则有递推关系,32,1.4Stirling近似公式,其中,33,1.4Stirling近似公式,34,1.4Stirling近似公式,所以,35,1.4Stirling近似公式,2)stirling公式,36,1.4Stirling近似公式,tn的几何意义是由x轴,x=n,以及连接(1,0),(2,ln2),(n1,ln(n1),(n,lnn)诸点而成的折线围成的面积。,令,令,37,1.4Stirling近似公式,Tn是由三部分面积之和构成的。一是曲线y=lnx在x=k点的切线和x轴，以及x=k1/2,x=k+1/2包围的梯形，当k=2,3,n-1时的面积之和；一是由y=lnx在x=1点的切线，x=3/2线，以及x轴围城的梯形；另一是由y=lnn,x=n1/2,x=n及x轴包围的矩形面积。,令,因而有,38,1.4Stirling近似公式,令bn=Antn，则序列bn是单调增的，而且有上界，故有极限，令limbn=b,由An,tn的表达式得,39,1.4Stirling近似公式,代入并整理得,令,40,1.4Stirling近似公式,组合计数的渐进值问题是组合论的一个研究方向。Stirling公式给出一个求n!的近似公式，它对从事计算和理论分析都是有意义的。,1)Wallis公式,1.5全排列的生成算法,1.2一一对应原理,42,1.5全排列的生成算法,全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。,这里介绍全排列算法四种：,(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法,43,1.5全排列的生成算法,1.5.1字典序法,字典序：设字符集A=a1,a2,，an有序：a1a2an则字符串集=p1p2pm|piA，mN按下列方式定义的序称为字典序：p1p2pmq1q2ql当且仅当p1=q1，p2=q2，pm=qm或存在km-1,使得p1=q1，pk=qk，pk+1qk+1,44,1.5全排列的生成算法,按字典序规定两个全排列的先后是从左到右逐个比较对应的字符的先后。,字典序法：一个全排列可看做一个字符串，按字典序给出全排列的序称为字典序法,例如，字符集1,2,3,较小的数字较先,这样按字典序生成的全排列顺序是:123,132,213,231,312,321。,两个字符串，相同前缀越长的越靠近。,45,1.5全排列的生成算法,如何生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。,例如839647521是1-9的排列。19的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。,46,在839647521中从右向左第一个小于右边数字的是元素4，此时有后缀7521；,将后缀翻转得1247，接上前缀83965得到839651247,1.5全排列的生成算法,后缀中大于4的最小数是5，交换4,5的位置；此时，排列的前缀是83965，后缀是7421；,即839647521的下一个排列为839651247。,47,1.5全排列的生成算法,首先，在排列中从右向左找出第一个小于右边元素的元素，记为a。右边部分构成后缀。,由字典序法产生下一个排列的步骤,其次，在后缀找出大于a的最小元素，记为b,第三，对换元素a与b,最后，对新的后缀进行翻转，得到所求。,48,1.5全排列的生成算法,例1.5.1在字典序下求731598642的下一个排列,首先，在排列中从右向左找出第一个小于右边元素的元素，是5；,其次，在后缀找出大于5的最小元素，是6；,第三，对换元素5与6,最后，对新的后缀进行翻转，得到所求为731624589,49,令j=maxi|PiPj对换Pj，Pk，并将Pj+1Pk-1PjPk+1Pn翻转，,1.5全排列的生成算法,一般而言，设P是1,n的一个全排列P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pn,P=P1P2Pj-1PkPnPk+1PjPk-1Pj+1,即P的下一个排列,由字典序法产生下一个排列的算法,50,计算给定排列的序号,1.5全排列的生成算法,例如，在1,n的全排列中,按字典序法123.(n-1)n是第一个排列，序号为0;n(n-1)321是最后一个排列，序号为n!-1.,为了求得排列的序号，下面首先给出数的阶乘表示法。,在给定的序法下，将先于此排列的排列个数称为该排列的序号。,51,1.5全排列的生成算法,注意到,所以,可以证明：对任意的m(0mn!-1)可唯一的表示为,其中,52,1.5全排列的生成算法,所以在阶乘表示法下，任意的数m(0mn!-1)可表示为,其中,例如，5=22!+11!=21,15=23!+12!+11!=211,100=44!+03!+22!+01!=4020,53,1.5全排列的生成算法,下面通过实例来给出排列序号的计算方法,例1.5.2求排列839647521的序号。,将先于此排列的排列按前缀分类,前缀先于8的排列的个数：78!,第1位是8,先于83得的排列的个数：27!,前2位是83,先于839得的排列的个数：66!,前3位是839,先于8396得的排列的个数：45!,前4位是8396,先于83964得的排列的个数：24!,前2位是83,先于839得的排列的个数：66!,前3位是839,先于8396得的排列的个数：45!,前4位是8396,先于83964得的排列的个数：24!,54,所以先于此排列的排列的个数为：,前5位是83964,先于839647得的排列的个数：33!,前6位是839647,先于8396475得的排列的个数：22!,前7位是8396475,先于83964752得的排列的个数：11!,前8位固定，则最后一位也随之固定,78!+27!+66!+45!+24!+33!+22!+11!=297191,故排列839647521的序号为297191。,1.5全排列的生成算法,55,将8!,7!,1!前面的系数抽出，放一起得72642321，此数的特点：,6：9的右边比9小的数的个数,7：8的右边比8小的数的个数,2：3的右边比3小的数的个数,4：6的右边比6小的数的个数,2：4的右边比4小的数的个数,3：7的右边比7小的数的个数,排列839647521,2：5的右边比5小的数的个数,1：2的右边比2小的数的个数,1.5全排列的生成算法,56,72642321是计算排列839647521序号的中间环节，我们称之为中介数。这是一个很有用的概念。,例如，在1,3的全排列中,按字典序法123是第1个排列，序号为0，中介数是00;132是第2个排列，序号为1，中介数是01;213是第3个排列，序号为2，中介数是10;231是第4个排列，序号为3，中介数是11;312是第5个排列，序号为4，中介数是20;321是第6个排列，序号为5，中介数是21.,1.5全排列的生成算法,57,给定排列的序号计算,1.5全排列的生成算法,一般地，设P是1,n的一个全排列P=P1P2Pn，则排列的序号为,其中,为排列的中介数,ak：Pn-k的右边比Pn-k小的数的个数,58,1.5全排列的生成算法,排列的中介数为：62024321,例1.5.3在字典序下求排列731598642的序号,排列的序号为：,68!+27!+06!+25!+44!+33!+22!+11!=252359,注：给定排列后，通过中介数计算，不难得到排列序号计算。,59,给定序号推出排列的方法,1.5全排列的生成算法,例如，由序号72642321推出排列839647521,方法1：,P1P2P3P4P5P6P7P8P9_,7+1=8，P1=8,2+1=3，P2=3,6+1=7，但3已在P3左边出现，7+1=8，但8已在P3左边出现，8+1=9P3=9,4+1=5，但3已经在P4左边出现，5+1=6P4=6,60,2+1=3，但3已经在P5左边出现，3+1=4P5=4,3+1=4，但3,4已经在P6左边出现，4+1+1=6，但6已经在P6左边出现，6+1=7P6=7,2+1=3，但3已经在P7左边出现，3+1=4，但4已经在P7左边出现，4+1=5P7=5,1+1=2P8=2,P1P2P3P4P5P6P7P8P9_,8,3,6,9,P9=1,1.5全排列的生成算法,61,方法2：,中介数右端加一个0扩成9位，先定1，从小到大逐个定位，每定一位，其左边未定位下加一点，从（位位下点数=0）的位中选最左的。,726423210,P1P2P3P4P5P6P7P8P9_,1,2,3,4,5,6,7,8,9,1.5全排列的生成算法,62,1.5全排列的生成算法,方法2：,中介数右端加一个0扩成9位，先定1，从小到大逐个定位，每定一位，其左边未定位下中介数减1，从中介数为0的位中选最左的。,726423210,P1P2P3P4P5P6P7P8P9_,1,61531210,2,5042010,3,4,33110,2200,5,6,110,7,00,8,9,442010,63,1.5全排列的生成算法,1.5.2递增进位制数法,在字典序法中，中介数的各位是由排列数的位决定的，即中介数an-1an-2a1中ak表示排列的第n-k位Pn-k的右边比Pn-k小的数的个数。介数位的下标与排列的位的下标一致。,在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数an-1an-2a1中ak表示元素k+1在排列中它的右边比k+1小的数的个数。中介数中各位的下标与排列中的元素(2n)一致。,64,在数的阶乘表示法下，任意的数m(0mn!-1)可表示为,其中,1.5全排列的生成算法,可看出n-1位的进位链，右端第1位逢2进1，右起第2位逢3进1，,右起第k位逢k+1进1，k=1,2,n-1.这样的进位制我们称为递增进位制数。,例如，510=21，910=111，1410=510+910=21+111=210,65,由排列求中介数(及序号)的方法,1.5全排列的生成算法,从大到小逐个计算每个元素在排列中它的右边比它小的元素的个数（逆序数），即中介数an-1an-2a1中ak表示元素k+1的逆序数。,一般地，设P是1,n的一个全排列P=P1P2Pn，则在递增进位制数法中排列的中介数an-1an-2a1由下列方法得到,以中介数作为数的阶乘表示法下的位系数，计算排列的序号,66,1.5全排列的生成算法,例1.5.4在递增进位制下求排列839647521的中介数。,解,对此排列的元素由大到小逐个计算逆序数,元素9的逆序数：6,元素8的逆序数：7,元素6的逆序数：4,元素5的逆序数：2,元素3的逆序数：2,元素7的逆序数：3,元素2的逆序数：1,元素4的逆序数：2,故此排列的中介数为：67342221序号为68!+77!+36!+45!+24!+23!+22!+11!=279905,注：排列839647521在字典序下的中介数：72642321。序号为297191,67,解在1,3的全排列中,按递增进位制法123是第1个排列，中介数是00，序号为0;213是第2个排列，中介数是01，序号为1;132是第3个排列，中介数是10，序号为2;231是第4个排列，中介数是11，序号为3;312是第5个排列，中介数是20，序号为4;321是第6个排列，中介数是21，序号为5.,1.5全排列的生成算法,例1.5.5在递增进位制下求1,2,3的所有全排列的中介数。,注：排列在不同序下的顺序是不同的。,68,由序号(及中介数)求排列的方法,1.5全排列的生成算法,由序号（十进制）求中介数（递增进位制）如下：m=m1,0mn!-1m1=2m2+a1,0a11m2=3m3+a2,0a22.mn-2=(n-1)mn-1+an-2,0an-2n-2mn-1=an-1,0an-1n-1则序号为m的排列p1p2pn的中介数为an-1an-2a1m10=(an-1an-2a1),69,1.5全排列的生成算法,297191=2148595+1,a1=1；2476=6412+4,a5=3；148595=349531+2,a2=2；412=758+6,a6=6；49531=412382+3,a3=3；58=87+2,a7=2；12382=52476+3,a4=3；a8=7。,例1.5.6在递增进位制下，求序号为297191的排列的中介数。,解由于m=297191，且,则序号为297191的排列p1p2pn的中介数为72633321。,70,设在1,n上的某排列的中介数为an-1an-2a1，则对元素从大到小逐个确定其位置，元素k的位置是从右向左的第ak-1+1个空位，最后留下的空是元素1的位置。,1.5全排列的生成算法,在字典序法中由中介数求排列比较麻烦，而在递增进位制数下则比较简单。,P1P2PiPjPlPsPn_k_|ak-1|,71,例1.5.7在递增进位制下，求序号为297191的排列。,1.5全排列的生成算法,解由于例1.5.6知排列的中介数为72633321，则,元素9在从右向左的第7+1个空位,P1P2P3P4P5P6P7P8P9_,元素8在从右向左的第2+1个空位,元素7在从右向左的第6+1个空位,元素6在从右向左的第3+1个空位,元素5在从右向左的第3+1个空位,元素4在从右向左的第3+1个空位,元素3在从右向左的第2+1个空位,元素2在从右向左的第1+1个空位,注意：数空位,所求排列为794563821,72,例1.5.8在递增进位制下，求排列794563821的下一个。,1.5全排列的生成算法,解通过计数每个元素的逆序数可知排列的中介数为72633321,通过递增进位制计算可知下一个排列的中介数为72633321+1=72624000,而中介数为72624000的排列为795126834,故所求排列为795126834,73,例1.5.9在递增进位制下，求排列794563821后的第10个排列。,1.5全排列的生成算法,解通过计数每个元素的逆序数得排列的中介数为72633321,然后通过递增进位制计算所求排列的中介数为72633321+120=72634111,注意到1010=120,故所求排列为795263841,74,1.5.3递减进位制数法,1.5全排列的生成算法,在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。,把递增进位制数翻转,就得到递减进位制数。,转变为,75,1.5全排列的生成算法,从大到小逐个确定元素k的位置为从右向左的第ak-1+1个空位，最后留下的空是元素1的位置。,在递减进位制数下由排列获得中介数，以及由中介数确定排列的方法与在递增进位制数下是一致的。,P1P2PiPjPlPsPn_k_|ak-1|,从小到大逐个计算每个元素在排列中它的右边比它小的元素的个数（逆序数），即中介数a1a2an-1中ak表示元素k+1的逆序数。,76,在递减进位制下求下一个排列十分容易,例1.5.10在递减进位制下求排列839647521的中介数，并求它的下一个排列。,1.5全排列的生成算法,解通过计数每个元素的逆序数得排列的中介数为12224376,下一个排列的中介数为12224376+1=12224377,所以下一个排列十分容易为893647521,77,解在1,3的全排列中,按递减进位制法123是第1个排列，中介数是00，序号为0;132是第2个排列，中介数是01，序号为1;312是第3个排列，中介数是02，序号为2;213是第4个排列，中介数是10，序号为3;231是第5个排列，中介数是11，序号为4;321是第6个排列，中介数是12，序号为5.,1.5全排列的生成算法,例1.5.11在递减进位制下求1,2,3的所有全排列的中介数。,注：排列在不同序下的顺序是不同的。,78,1.5.4邻位对换法,1.5全排列的生成算法,递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。,79,这个算法可描述如下：对1n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1n的n个排列。对1n-1的每一个奇排列，n从左到右插入n个空档，生成1n的n个排列。对2,n的每个数字都是如此。,1.5全排列的生成算法,80,解在邻位对换法下123是第1个排列，中介数是00，序号为0;132是第2个排列，中介数是01，序号为1;312是第3个排列，中介数是02，序号为2;321是第4个排列，中介数是10，序号为3;231是第5个排列，中介数是11，序号为4;213是第6个排列，中介数是12，序号为5.,1.5全排列的生成算法,例1.5.12在邻位对换法下给出1,2,3的所有全排列。,注：排列在不同序下的顺序是不同的。,81,例,839647521836947521,解,2的右边有1个数字(奇数)比2小,2上加一个点。,3的右边有2个数字(偶数)比3小,3上不加点。,4的右边有2个数字(偶数)比4小,4上不加点。,5的右边有2个数字(偶数)比5小,5上不加点。,6的右边有2个数字(偶数)比6小,6上不加点。,7的右边有3个数字(奇数)比7小,7上加一个点。,8的右边有7个数字(奇数)比8小,8上加一个点。,18上共有3个(奇数)点，9上箭头向右。,P=839647521()b2b3b4b5b6b7b8b9,1,0,1,2,1,3,7,2,2上箭头向左，2右边有1个数字比2小，b2=1,3上箭头向右，3左边有0个数字比3小，b3=0,4上箭头向右，4左边有1个数字比4小，b4=1,5上箭头向右，5左边有2个数字比5小，b5=2,6上箭头向右，6左边有1个数字比6小，b6=1,7上箭头向左，7右边有3个数字比7小，b7=3,8上箭头向左，8右边有7个数字比8小，b8=7,9上箭头向右，9左边有2个数字比9小，b9=2,839647521的中介数为10121372,1.5全排列的生成算法,82,1.5.4邻位对换法,ak(p)：p中1k排列的序号，ak(p)的奇偶性与1k排列的奇偶性相同。,a9(p)=9a8(p)+b9(p)=9(8a7(p)+b8(p)+b9(p),an(p)，bn(p)简写成an，bn,83,1.5.4邻位对换法,已知(10121372)求排列。,9的位置由b9和a8的奇偶性决定。a8的奇偶性同b8的奇偶性。a7的奇偶性同b7+b6的奇偶性。b2=0,1。,b8奇9，b6+b7偶8，b6奇7，b4+b5奇6，b4奇5,84,1.5.4邻位对换法,序号=13+0)4+1)5+2)6+1)7+3)8+7)9+2=203393(10121372),85,1.5全排列的生成算法,86,1.5全排列的生成算法,87,1.6组合的生成,设从1,n中取r元的组合全体为C(n,r).C1C2CrC(n,r).不妨设C1C2CriCi(nr+i),i=1,2,r令j=maxi|Cinr+i.则C1C2Cr的下一个组合为C1C2Cj-1(Cj+1)(Cj+2)(Cj+rj+1)这等于给C(n,r)的元素建立了字典序。12r的序号为0，n-r+1n-r+2n的序号为()1,_nr,88,例在C(10,4)中4679的序号是首位小于4的组合的个数；首位是4，第2位小于6的组合的个数；前2位是46，第3位小于7的组合的个数；前3位是467，第4位小于9的组合的个数之和。反之，也可以由序号求组合。,89,1.6组合的生成,A(m,l)：1,m的l-组合(或l-子集)。第1个组合：1,2,l-1,l.最后1个组合：1,2,l-1,mA(n,k)=A(n-1,k)，A(n-1,k-1)nA：将有序集A(或线性表)的顺序逆转的有序集。An：将A中每个元素(是集合)都与n求并的有序集,_,_,_,90,1.6组合的生成,例用两种方法计算1,n的无重不相邻组合C(n,r)的计数问题解法100100100100100其中不可含11,/,共n位,r个1,/,以1结尾：r-1个10与n-1-2(r-1)个0的排列r-1+n-1-2(r-1)=n-r这样的排列有,(n-r)!=(r-1)!(n-2r+1)!,(),n-rr-1,91,1.6组合的生成,以0结尾：r个10与n-2r个0的排列r+n-2r=n-r这样的排列有()个()+()=()f(a1a2ar)=b1b2br,n-rr,n-rn-rn-r+1r-1rr,92,1.6组合的生成,解法任给a1a2arC(n,r),a1a2ar令f：a1a2arb1b2brbi=ai-i+1,i=1,2,r.1b1b2brn-r+1,b1b2brC(n-r+1,r)C(n,r)=C(n-r+1,r),93,1.7可重组合,C(n,r)的计数问题相当于r相同的球放入n个互异的盒子，每盒球的数目不同的方案的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。易知所求计数为=C(n+r-1,r)即C(n,r)=()=C(n-1,r)+C(n,r-1)不含“”至少含一个“”,(n-1+r)!r!(n-1)!,n+r-1r,r个相同的球/001001100/n-1个相同的盒壁,94,1.7可重组合,另证设a1a2arC(n,r)1a1a2arn,令C(n,r)上的f，使得bi=ai+i-1,i=1,2,r.则b1b2br满足1b1b2brn+r-1b1b2brC(n+r-1,r)f：a1a2arb1b2br显然f是单射，f：b1b2bra1a2ar,-1,95,1.7可重组合,ai=bi-i+1,i=1,2,r.a1a2arC(n,r)f是单射C(n,r)C(n+r-1,r)f是单射C(n,r)C(n+r-1,r)C(n,r)=C(n+r-1,r)第二个证明可说一种“拉伸压缩”技巧。不可谓不巧妙。但仍不如第一证明来的明快，由此可见组合证明的功效。,-1,96,1.8若干等式及其组合意义,组合意义或组合证明，含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。,97,1.8若干等式及其组合意义,1.C(n,r)=C(n,n-r)(1.7.1)从1,n去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。故C(n,r)=C(n,n-r),98,1.8若干等式及其组合意义,2.C(n,r)=C(n-1,r)+C(n-1,r-1)(1.7.2)从1,n取a1,a2,ar.设1a1a2arn,对取法分类：a1=1,有C(n-1,r-1)种方案a11,有C(n-1,r-1)种方案共有C(n-1,r)+C(n-1,r-1)中方案，故C(n,r)=C(n-1,r)+C(n-1,r-1),99,1.8若干等式及其组合意义,杨辉三角除了(0,0)点，都满足此递推式0rn,n0rC(n,r)=1,r=00,0nr,r0nn0且r0C(m+n,m)=C(m+n-1,m)+C(m+n-1,m-1)(0,0)(m,n)=(0,0)(m,n-1)(0,0)(m-1,n),(-1)(),|r|-1|n|-1,n+r,nrr!,100,1.8若干等式及其组合意义,3.()+()+()+()=()(1.7.3)1可从(7.2)推论，也可做一下组合证明从1,n+r+1取a1a2anan+1，设a1a2anan+1，可按a1的取值分类：a1=1,2,3,r,r+1.a1=1,a2an+1取自2,n+r+1有()种取法,nn+1n+2n+rn+r+1nnnnn,n+rn,a1=2,a2an+1取自3,n+r+1有()种取法,n+r-1n,a1=r,a2an+1取自r+1,n+r+1有()种取法,n+1n,a1=r+1,a2an+1取自r+2,n+r+1有()种取法,nn,也可看做按含1不含1，含2不含2,含r不含r的不断分类,101,1.8若干等式及其组合意义,2从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上)(),(),()故有.()+()+()+()=(),nn+1n+rnnn,nn+1n+2n+rn+r+1nnnnn,r(n+1,r).(0,0)nn+1,102,1.8若干等式及其组合意义,3可重组合.1,n+2的C(n+2,r)模型()不含1,含1个1,含2个1,含r个1C(),C(),C(),C()(),(),(),(),n+r+1r,n+1n+1n+1n+1rr-1r-20,n+rn+r-1n+r-2nrr-1r-20,103,1.8若干等式及其组合意义,4.()()=()()(1.7.4)选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委选常委,再选非常委政治局委员两种选法都无遗漏,无重复地给出可能的方案，应该相等。,nlnn-rlrrl-r,104,1.8若干等式及其组合意义,5.()+()+()=2,m0,(1.7.5)证1(x+y)=()xy,令x=y=1,得(1.7.5)组合证11,m的所有方案.每一子集都可取k1,m或不取.这样有2个方案.另可有0-子集(空集),1-子集,m-子集.组合证2从(0,0)走m步有2种走法,都落在直线x+y=m上,而到(m,0),(m-1,1),(m-2,2),(2,m-2),(1,m-1),(0,m)各点的走法各有(),(),(),(),(),()种,mmmm01m,mkm-k,mmkk=0,m,m,mmmmmm012m-2m-1m,105,1.8若干等式及其组合意义,6.()-()+()-()=0(1.7.6)证1在(x+y)=()xy中令x=1,y=-1即得.,nnnn012n,nn-kk,nk,nk=0,106,1.8若干等式及其组合意义,证2在1,n的所有组合中,含1的组合不含1的组合.有11对应关系。在任一含1组合及与之对应的不含1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数阁元的组合做成另一集。此二集的元数相等。()=(),nnii,i奇i偶,107,1.8若干等式及其组合意义,7.()=()()+()()+()()(1.7.7)即Vandermonde恒等式证1从m个互异红球和n个互异蓝球中取r个球,按r个球中红球的个数分类.组合证法:(0,0)到(m+n-r)点的路径.(0,0)(m-r+l,r-l)(m+n-r,r)()()()=()(),m+nmnmnmnr0r1r-1r0,mnr-ll,m+nmnrr-ll,P(m-r,r)(m+n-r,r)(m-r+l,r-l)l=0,1,2,rQ(m,0),rl=0,108,1.8若干等式及其组合意义,李善兰(18111882），清代数学家李善兰恒等式：()()()=()(),kln+k+l-jn+kn+ljjk+lkl,j0,证：利用Vandermonde恒等式及()()=()()=()()(接下页),nvnn-pnn-pvppn-vpv-p,109,1.8若干等式及其组合意义,有()()()=()()()()=()()()()=()()()()=()()()=()()()=()()()=()(),kln+k+l-jjjk+l,kln+kl-jjjk+vl-v,n+kkll-jk+vjjl-v,n+kklvk+vjvl,n+klk+vk+vvk,n+knlkn-vv,n+knlkn-vv,n+kn+lkl,j0j0vjv0j0v0j0v0v0v0,110,1.8若干等式及其组合意义,8.在7.中令r=mn,再将()换成()得()=()()+()()+()(),mmkm-k,m+nmnmnmnm0011mm,111,1.9应用举例,例某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若干钥匙。须人到场，所备钥匙才能开锁。问至少有多少把不同的钥匙？每人至少持几把钥匙？解每人至少缺把钥匙，且每人所缺钥匙不同。故至少共有()=35把不同的钥匙。,73,112,1.9应用举例,任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁。故每人至少持()20把不同的钥匙。为加深理解，举一个较简单的例子：人中人到场，所求如上。共有()=6把不同的钥匙。每人有()=3把钥匙。（见下页图）,113,1.9应用举例,钥匙A人BCD,114,1.9应用举例,例有4个相同质点,总能量为4E0,E0是常数。每个质点所具能量为kE0,k=0,1,2,3,4.A)若能级为kE0的质点可有k+1种状态，而且服从Bose-Einstein分布，即同能级的质点可以处于相同的状态，问系统有几种不同的状态？（或图像）B)若能级为kE0的质点可有2(k+1)种状态，而且服从Fermi-Dirac分布，即不允许同能级的两个质点有相同状态，问系统有几种不同状态？（或图像）,2,2,115,1.9应用举例,解,能级k01234A)k+11251017状B)2(k+1)24102034态,2,2,能量分布0,0,0,40,0,1,30,0,2,2A)111171121011C(5,2)B)C(2,3)34C(2,2)420C(2,2)C(10,2)能量分布0,1,1,21,1,1,1A)1C(2,2)5C(2,4)72B)2C(4,2)10C(4,4)246,116,1.9应用举例,例,3个相同的质点分布在2个相同的势阱里，这3个质点的总能量为3E0,每个质点的能级为kE0,k=0,1,2,3.能级为kE0的质点有2(k+1)种状态，服从Fermi-Dirac分布即同一势阱中的质点不可处于同一状态，问系统有几种状态？,2,117,1.9应用举例,0,0|30|0,30,1|20|1,21|0,21120222024108080=20=80=801,1|1111|0,0,3|0,1,2|C(4,2)4()11202410=24=4=20=80,43,202+805+24+4=468,解：,118,1.9应用举例,例,设n位长能纠r个错的码字的个数为M，则2/()M2/()n位长的0-1字符串共有2个。但不能每个串都设为码字，否则市区纠错能力。,n,nk,nk,n,2rk=0,rk=0,119,1.9应用举例,Hamming距离设a=a1a2an，b=b1b2bn是n位串。则a,b的Hamming距离为d(a,b)=|ai-bi|即对应位不同的位的个数。d(a,b)+d(b,c)d(a,c)d(a,b)=|ai-bi|,d(b,c)=|bi-ci|d(a,b)+d(b,c)=|ai-bi|+|bi-ci|(ai-