组合数学第一章

1、组合数学组合数学第一章第一章主讲教师主讲教师 数学学院魏毅强教授数学学院魏毅强教授联系电话联系电话Email : Yiqiang Wei 2第一章第一章排列组合排列组合1.4 Stirling近似公式近似公式Yiqiang Wei 3第一章第一章排列组合排列组合1.3 Stirling近似公式近似公式1.4 模型转换模型转换1.5全排列的生成算法全排列的生成算法1.6 组合的生成组合的生成1.7 可重组合可重组合1.8 若干等式及其组合意义若干等式及其组合意义1.9应用举例应用举例1.2 排列与组合排列与组合Yiqiang Wei 41.1 1.1 加法法则与乘法法则

2、加法法则与乘法法则 加法法则加法法则 设事件设事件A有有m种产生方式，事件种产生方式，事件B有有n种产生方式，则事件种产生方式，则事件A或或B之一有之一有m+n种产生方式。种产生方式。集合论语言：集合论语言：若若 |A| = m , |B| = n , A B = , 则则 |A B| = m + n 。例例1 书架上有数学类书书架上有数学类书5本，计算机类书本，计算机类书3，任取其，任取其中一本，有多少种取法。中一本，有多少种取法。共有共有5+3=8种取法种取法Yiqiang Wei 51.1 1.1 加法法则与乘法法则加法法则与乘法法则 乘法法则乘法法则 设事件设事件A有有m种产生式，事件

3、种产生式，事件B有有n种产生方式，则事件种产生方式，则事件A与与B有有 m n种产生方式。种产生方式。集合论语言：集合论语言：若若 |A| = m , |B| = n , A B = (a,b) | a A,b B, 则则 |A B| = m n 。例例2 从从A到到B有三条道路，从有三条道路，从B到到C有两条道路，则有两条道路，则从从A经经B到到C有几有几条道路条道路?有有 3 2=6 条条Yiqiang Wei 6例例3 机动车牌照字由机动车牌照字由7个字符组成，第一个字符是个字符组成，第一个字符是汉字，表示省份或军区等，第二个字符是英文字母汉字，表示省份或军区等，第二个字符是英文字母，表

4、示市、区或行业等，其余，表示市、区或行业等，其余5位可选自英文字母位可选自英文字母或数字（有时用第三个字符表示行业，如出租用或数字（有时用第三个字符表示行业，如出租用T)，问一个市的机动车拥有量最多是多少？，问一个市的机动车拥有量最多是多少？机动车拥有量最多是：机动车拥有量最多是：(26+10)5 辆。辆。出租车拥有量最多是：出租车拥有量最多是：(26+10)4 辆。辆。1.1 1.1 加法法则与乘法法则加法法则与乘法法则Yiqiang Wei 71.11.1 加法法则与乘法法则加法法则与乘法法则v例例4 某种样式的运动服的着色由底色和装饰条某种样式的运动服的着色由底色和装饰条纹的颜色配成。底

5、色可选红、蓝、橙、黄，条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有纹色可选黑、白，则共有4 2 = 8种着色方案。种着色方案。v若此例改成底色和条纹都用红、蓝、橙、黄四若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是种颜色的话，则，方案数就不是4 4 = 16， 而而只有只有 4 3 = 12 种。种。v在乘法法则中要注意事件在乘法法则中要注意事件 A 和和 事件事件 B 的相互的相互独立性。独立性。Yiqiang Wei 81.1 1.1 加法法则与乘法法则加法法则与乘法法则例5 1)求小于求小于10000的含的含1的正整数的个数的正整数的个数 2)求

6、小于求小于10000的含的含0的正整数的个数的正整数的个数小于小于10000的正整数可看做的正整数可看做4位数位数, 共有共有104 1=9999个（个（0000除外）除外）不含不含1的的4位数有：位数有：9416560个个含含1的的4位数有：位数有：99996560=3439个个 另另: 全部全部4位数有位数有10 4个个,不含不含1的四位数有的四位数有94 个个, 含含1的的4位数为两个数的差位数为两个数的差: 104 9 4= 3439个个Yiqiang Wei 92)“含含0”和和“含含1”不可直接套用。不可直接套用。0019(含含1但但不含不含0)。 在组合的习题中有许多类似的在组合

7、的习题中有许多类似的隐含隐含的规定，的规定，要特别留神。要特别留神。 不含不含0的的1位数有位数有9个，个，2位数有位数有92 个，个，3位数有位数有93 个，个，4位数有位数有94 个个 不含不含0小于小于10000的正整数有的正整数有 9+92+93+94 =(951)/(91)=7380个个含含0小于小于10000的正整数有的正整数有 99997380=2619个个1.1 1.1 加法法则与乘法法则加法法则与乘法法则Yiqiang Wei 101.1 1.1 加法法则与乘法法则加法法则与乘法法则例例6 求除尽求除尽 n=73.112.134 的数的个数的数的个数 除尽除尽 n=73.11

8、2.134 的数可表示为的数可表示为 x=7a.11b.13c其中其中40, 20, 30cba故整除的个数为故整除的个数为60534Yiqiang Wei 111.2 1.2 一一对应原理一一对应原理如我们说如我们说A A集合有集合有n n个元素个元素 |A|=|A|=n n，无非是建立了将无非是建立了将A A中元与中元与1,1,n n 元一一对应的关系。元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换在组合计数时往往借助于一一对应实现模型转换. .比如要对比如要对A A集合计数，但直接计数有困难，于是可设集合计数，但直接计数有困难，于是可设法构造一易于计数的法构造一易于计数的B

9、 B，使得使得A A与与B B一一对应。一一对应。 一一对应原理一一对应原理 如果事件如果事件A与事件与事件B间存在一一对间存在一一对应（双射），则事件应（双射），则事件A与与B一样大，即一样大，即|A|=|B| 。Yiqiang Wei 12例例7 7 在在6565名选手之间进行淘汰赛名选手之间进行淘汰赛( (即一场的比赛即一场的比赛结果，失败者退出比赛结果，失败者退出比赛),),最后产生一名冠军，最后产生一名冠军，问要举行几场比赛？问要举行几场比赛？ 另一种思路是淘汰的选手与比赛另一种思路是淘汰的选手与比赛( (按场计按场计) )集集一一对应。一一对应。淘汰淘汰6464名选手，需要名选手，

10、需要6464场比赛场比赛。1.2 1.2 一一对应原理一一对应原理 一种常见的思路是按轮计场（一种常见的思路是按轮计场（费事费事）：）： 32+16+8+4+2+1+1=6432+16+8+4+2+1+1=64注意，每轮都有一人轮空。注意，每轮都有一人轮空。Yiqiang Wei 13例例8 8 设凸设凸n n边形的任意三条对角线不共点，求对边形的任意三条对角线不共点，求对角线在多边形内交点的个数。角线在多边形内交点的个数。可以先计算对角线的个数，然后计算交点，但是存可以先计算对角线的个数，然后计算交点，但是存在在多边形内无交点的情形，比较复杂。在在多边形内无交点的情形，比较复杂。可以考虑对应

11、关系：可以考虑对应关系： 多边形内交点多边形内交点 to to 多边形四个顶点。多边形四个顶点。可以证明这是一一对应（映射，单且满）。可以证明这是一一对应（映射，单且满）。1.2 1.2 一一对应原理一一对应原理交点的个数：交点的个数：Cn4Yiqiang Wei 141.1.3 3 排列与组合排列与组合定义 从从n个不同的元素中，取个不同的元素中，取r个不重复的元素，个不重复的元素，按次序排列，称为从按次序排列，称为从n个中取个中取r个的个的无重排列无重排列。排列的全体组成的集合用排列的全体组成的集合用 P(n,r)表示。表示。所有不同排列的个数称为排列数，也记为所有不同排列的个数称为排列数

12、，也记为P(n,r)。或或Prn，或或Arn。当当r=n时称为时称为全排列全排列。所有不同全排列的个数记为。所有不同全排列的个数记为Pn或或An。Yiqiang Wei 151.1.3 3 排列与组合排列与组合从从n个中取个中取r个的排列的典型例子是个的排列的典型例子是( (取球模型取球模型):):从从n个不同的球中个不同的球中, ,取出取出r个个, ,放入放入r个不同的盒子里个不同的盒子里, ,每盒每盒1 1个。第个。第1 1个盒子有个盒子有n种不同选择，第种不同选择，第2 2个有个有n-1种选择，种选择，第，第r个有个有n-r+1种选择。故由乘法种选择。故由乘法原理有原理有 P(n,r)=

13、n(n-1)(n-r+1) =n!/(n-r)!Yiqiang Wei 16规定规定1.1.3 3 排列与组合排列与组合1, 1! 00nP从从n中取出中取出r个排列的模型，可看作是从个排列的模型，可看作是从n个有区个有区别的球中取出别的球中取出r个，放入个，放入r个有标记的盒子中，且个有标记的盒子中，且无一空盒。无一空盒。特别，当特别，当r=n时有时有! nPPnnn显然显然)!(!rnnPPrnPrnnrrnYiqiang Wei 17例例9 9 由由5 5种颜色的星状物，种颜色的星状物，2020种不同的花排列成种不同的花排列成如下图案：两边是星状物，中间是如下图案：两边是星状物，中间是3

14、 3朵花，问共朵花，问共有多少种这样的图案？有多少种这样的图案？ 两边是星状物，从五种颜色的星状物中取两个的两边是星状物，从五种颜色的星状物中取两个的排列的排列数是排列的排列数是 P(5,2)=20根据乘法法，则得图案数为根据乘法法，则得图案数为2020种不同的花取种不同的花取3 3种排列的排列数是种排列的排列数是P(20,3)=20 19 18=684020 6840=1368001.1.3 3 排列与组合排列与组合Yiqiang Wei 18例例1010 A单位有单位有7 7名代表，名代表，B单位有单位有3 3位代表，排成一位代表，排成一列合影，如果要求列合影，如果要求B单位的单位的3 3

15、人排在一起，问有多人排在一起，问有多少种不同的排列方案。若少种不同的排列方案。若A单位的单位的2 2人排在队伍两人排在队伍两端，端，B单位的单位的3人不能相邻，问有多少种不同的排人不能相邻，问有多少种不同的排列方案列方案？B单位单位3 3人按一个元素参加排列，人按一个元素参加排列，P P(8,8)(8,8)P P(3,3)(3,3)A单位的人排法固定后单位的人排法固定后A*A*A*A*A*A*A，B单单位位第一人有第一人有6 6种选择，第二人有种选择，第二人有5 5种，第三人有种，第三人有4 4种，因此答案为种，因此答案为 P P(7,7)(7,7)6 65 54 41.1.3 3 排列与组合

16、排列与组合Yiqiang Wei 19于是我们只需要计算于是我们只需要计算Si即即可可。例例1111 求由求由1,3,5,71,3,5,7组成的不重复出现的整数的总和组成的不重复出现的整数的总和解：解：这样的整数可以是这样的整数可以是1 1位数位数,2,2位数位数,3,3位数位数,4,4位数位数, , S=S1+S2+S3+S4,S1=1+3+5+7=16,1.1.3 3 排列与组合排列与组合若设若设 Si，i=1,2,3,4=1,2,3,4，是，是i位数的总和，则位数的总和，则Yiqiang Wei 20 S2=3(1+3+5+7)10+3(1+3+5+7)= 480+48=528S4=6(

17、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=106656S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7) =9600+960+96=10656S=16+528+10656+106656=117856两位数有：两位数有：13,15,17,31,33,35,37,51,53,55,57,71,73,75,77，所以，所以同理同理1.1.3 3 排列与组合排列与组合Yiqiang Wei 211.1.3 3 排列与组合排列与组合例例1212 假设一高速路口有假设一高速路口有4

18、 4个出口，现有个出口，现有9 9辆车子从这辆车子从这6 6个口下高速，问有多少种不同的下法？个口下高速，问有多少种不同的下法？解法一解法一 假设出口编号为：假设出口编号为：K K1 1，K K2 2，K K3 3，K K4 4； 9 9辆车的编号为辆车的编号为1,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,91 1号车选择出口有号车选择出口有4 4种；种；2 2号车选择就有号车选择就有5 5种，因为当种，因为当2 2号车与号车与1 1号车选同一出口时，两车有前后顺序的号车选同一出口时，两车有前后顺序的问题；同理问题；同理3 3号车有号车有6 6种选择；依此类推，种选择；依此

19、类推，9 9号车号车应有应有1212种选择。故不同的下法共有种选择。故不同的下法共有 4 4* *5 5* *6 6* * *12=12!/3!12=12!/3!Yiqiang Wei 221.1.3 3 排列与组合排列与组合解法二解法二 如果只有一个出口，则显然如果只有一个出口，则显然9 9辆车的不同下辆车的不同下法为法为 9 9！；如果有两个出口，则可以加入一个分！；如果有两个出口，则可以加入一个分隔符隔符F F与车辆号一起进行排列，在与车辆号一起进行排列，在F F的左右排列可的左右排列可看作是分别从两个出口的一种下法，故此时的下看作是分别从两个出口的一种下法，故此时的下法为法为 1010

20、！。！。本题有本题有4 4个出口，应加入三个分隔符，所以不同的下个出口，应加入三个分隔符，所以不同的下法有法有 12!/3!.12!/3!.注意到，分隔标记注意到，分隔标记F F是无区别的是无区别的Yiqiang Wei 231.1.3 3 排列与组合排列与组合解法三解法三 在在9 9辆车的标号与辆车的标号与3 3个分隔符共同组成的个分隔符共同组成的1212个标记中，首先选出个标记中，首先选出3 3个作为分隔符，不同选法个作为分隔符，不同选法有有C(12,3)C(12,3)，然后余下的，然后余下的9 9个作为车辆标号进行排个作为车辆标号进行排列，应有列，应有9!9!种不同方案，故总的下法有种不

21、同方案，故总的下法有 C(12,3)C(12,3)* *9!=12!/3!9!=12!/3!注意注意 本解法用到了组合的概念，它也可以作为基本解法用到了组合的概念，它也可以作为基本的组合模型本的组合模型Yiqiang Wei 241.1.3 3 排列与组合排列与组合定义定义 从从n个不同元素中取个不同元素中取r个不重复的元素组成一个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从个子集，而不考虑其元素的顺序，称为从n个中个中取取r个的个的无重组合无重组合。rnC组合的全体组成的集合用组合的全体组成的集合用 C(n,rC(n,r) ) 表示，表示，所有不同组合的个数记为所有不同组合的个数记

22、为 C(n,rC(n,r) )或或 C Cn nr r若球不同，盒子相同，则是从若球不同，盒子相同，则是从n n个不同元素中取个不同元素中取r r个不重复的组合的模型。个不重复的组合的模型。Yiqiang Wei 25若球不同，盒子相同，则是从若球不同，盒子相同，则是从n n个中取个中取r r个的组合个的组合的模型。若放入盒子后再将盒子标号区别，则的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有又回到排列模型。每一个组合可有r!r!个标号方个标号方案。案。故有故有 C(n,r)C(n,r)r r!=!=P(n,rP(n,r),),即即 C(n,rC(n,r)=)=P(n,

23、r)/rP(n,r)/r!= != n!r!(n-r)!1.1.3 3 排列与组合排列与组合Yiqiang Wei 261.1.3 3 排列与组合排列与组合例例1313 有有5 5本不同的俄文书，本不同的俄文书，7 7本不同的英文书，本不同的英文书，1010本不同的中文书。如果从中任本不同的中文书。如果从中任1)1)取取2 2本不同文字的书；本不同文字的书；2)2)取取2 2本相同文字的书；本相同文字的书；3)3)任取两本书任取两本书问各有多少种不同的取法？问各有多少种不同的取法？解解 1) 5 1) 57+57+510+710+710=155;10=155; 2) 2) C(5,2)+C(7

24、,2)+C(10,2)C(5,2)+C(7,2)+C(10,2) =10+21+45=76; =10+21+45=76; 3) 155+76=231=( ) 3) 155+76=231=( )5+7+10 2Yiqiang Wei 271.1.3 3 排列与组合排列与组合例例14 14 从从1,3001,300中取中取3 3个不同的数，使这个不同的数，使这3 3个数的和个数的和能被能被3 3整除，有多少种方案？整除，有多少种方案？解解 将将1,300分成分成3类：类： A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)

25、=3,6,9,300. 要满足条件，有四种解法：要满足条件，有四种解法： 1) 3个数同属于个数同属于A; 2) 3个数同属于个数同属于B 3) 3个数同属于个数同属于C; 4) A,B,C各取一数各取一数.故共有故共有3C(100,3)+1003 =485100+1000000=1485100Yiqiang Wei 281.1.3 3 排列与组合排列与组合例例8 8 某车站有某车站有6 6个入口处，每个入口处每次只能个入口处，每个入口处每次只能进一人，一组进一人，一组9 9个人进站的方案有多少？个人进站的方案有多少？解解 进站方案可表示成：进站方案可表示成：00011001010100其中其

26、中“0”表示人，表示人，“1”表示门框，其中表示门框，其中“0”是是不同元，不同元，“1”是相同元。给是相同元。给“1”n个门只用个门只用n-1个门框。任意进站方案可表示成上面个门框。任意进站方案可表示成上面14个元素的个元素的一个排列。一个排列。Yiqiang Wei 291.1.4 4 StirlingStirling近似公式近似公式v组合计数的渐进值问题是组合论的一个研究方向。组合计数的渐进值问题是组合论的一个研究方向。vStirlingStirling公式给出一个求公式给出一个求n!n!的近似公式，它对从的近似公式，它对从事计算和理论分析都是有意义的。事计算和理论分析都是有意义的。20

27、sinxdxInn1) Wallis公式公式, 2, 1, 0nYiqiang Wei 301.1.4 4 StirlingStirling近似公式近似公式2, 121102IInInnInn则有递推关系则有递推关系令令n! = 135(n-2)n，n是奇数。是奇数。246(n-2)n，n是偶数。是偶数。则则10!)!1(! !)!1(! !InnInnInn n是奇数是奇数n n是偶数是偶数Yiqiang Wei 311.1.4 4 StirlingStirling近似公式近似公式20 x当当时，由于时，由于 12212nnnIII ， (2k)! (2k-1)! (2k-2)!(2k+1)

28、! (2k)! 2 (2k-1)!1 1. 2 (2k)!(2k-1)! 1 2k+12k+1 2k2kYiqiang Wei 321.1.4 4 StirlingStirling近似公式近似公式v所以所以 (2k)!(2k-1)!2lim = , 1 2k+1 2klim = ,(2k)!(2k)! (2k)! 1 2k+12 2klim =2 (k!) (2k)! 1 2k+12 2k2k 2Yiqiang Wei 331.1.4 4 StirlingStirling近似公式近似公式v2)2)stirling公式公式y y=lnx 0 1 2 3 n-1 n xYiqiang Wei 34

29、1.1.4 4 StirlingStirling近似公式近似公式v令An= lnxdx=xlnx| dx=nlnnn+1 vtn=ln1+ln2+ln(n1)+lnn=ln(n!)lnnvtn的几何意义是由x轴,x=n,以及连接(1,0), (2,ln2),(n1,ln(n1),(n,lnn)诸点而成的折线围成的面积。n n n1 1 11 12 212Yiqiang Wei 351.1.4 4 StirlingStirling近似公式近似公式vTn=+ln2+ln(n1)+lnn1 18 2Tn是由三部分面积之和构成的。一是曲线是由三部分面积之和构成的。一是曲线y=lnx在在x=k点的切线和

30、点的切线和x轴，以及轴，以及x=k,x=k包围的梯形，当包围的梯形，当k分别为分别为2,3,n-1时的面积之和；一是由时的面积之和；一是由y=lnx在在x=1点的切点的切线，线，x=3/2线，以及线，以及x轴围城的梯形；另一轴围城的梯形；另一是由是由y=lnn,x=n,x=n及及x轴包围的矩形轴包围的矩形面积。因而有面积。因而有 tnAnTn121212Yiqiang Wei 361.1.4 4 StirlingStirling近似公式近似公式v所以所以n! 2n ()v令bn=An tn.序列b1,b2,是单调增，而且有上界，故有极限，令 limbn=b1v由(1-3-4),(1-3-5)

31、得 bn=nlnnn+1ln(n!)+lnn = lnnn+1ln(n!)+ln n vln(n!)=1bn+ lnn ln n lnevn!=e n ()0AntnTntn=18n12nn n1-bnnenYiqiang Wei 371.1.4 4 StirlingStirling近似公式近似公式v令令n=e ,limn=.v将将(1-3-8)代入代入(1-3-3),整理得整理得 = 2 .n1-bnnenYiqiang Wei 381.5 1.5 全排列的生成算法全排列的生成算法全排列的生成算法全排列的生成算法就是对于给定的字符集就是对于给定的字符集，用有，用有效的方法将所有可能的全排列无

32、重复无遗漏地效的方法将所有可能的全排列无重复无遗漏地枚举出来。枚举出来。 这里介绍全排列算法四种：这里介绍全排列算法四种：( (A)A)字典序法字典序法( (B)B)递增进位制数法递增进位制数法( (C)C)递减进位制数法递减进位制数法( (D)D)邻位对换法邻位对换法Yiqiang Wei 391.5 1.5 全排列的生成算法全排列的生成算法 对给定的字符集中的字符规定了一个先后关对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。右逐个比较对应的字符的先后。1.5.11.5.1字典序法字典序法

33、例字符集字符集1,2,3,1,2,3,较小的数字较先较小的数字较先, ,这样按字这样按字典序生成的全排列是典序生成的全排列是: :123,132,213,231,312,321123,132,213,231,312,321。 一个全排列可看做一个字符串，字符串可一个全排列可看做一个字符串，字符串可有有前缀前缀、后缀后缀。Yiqiang Wei 401.5 1.5 全排列的生成算法全排列的生成算法1 1）生成给定全排列的下一个排列生成给定全排列的下一个排列所谓所谓一个的下一个一个的下一个就是这一个与下一个之间没有就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能其他的。这就要求这一

34、个与下一个有尽可能长长的的共同前缀共同前缀，也即变化限制在尽可能，也即变化限制在尽可能短短的的后缀后缀上。上。 例例 839647521 839647521是是1-91-9的排列。的排列。1 19 9的排列最前的排列最前面的是面的是123456789123456789，最后面的是，最后面的是987654321987654321，从，从右向左扫描若都是增的，就到右向左扫描若都是增的，就到了了987654321987654321，也，也就没有下一个了。否则找出第一次出现下降的就没有下一个了。否则找出第一次出现下降的位置位置。Yiqiang Wei 41求求839648396475217521的下一

35、个排列的下一个排列7 5 2 1 747 42 2 41 1在后缀7521中找出比4大的数7 5找出其中比4大的最小数 5 5 4 、5 对换 8396 7 215 4后缀变为7421 将此后缀翻转 12 4 7接上前缀83965得到839651247 即839647521的下一个。例为后缀大于4的用橙色表示小于4的用绿色表示找出比右边数字小的第一个数41.5 1.5 全排列的生成算法全排列的生成算法Yiqiang Wei 421.5.11.5.1字典序法字典序法求求83968396475217521的下一个排列的下一个排列7 5 2 1 747 42 2 41 1 在后缀7521中找出比4大

36、的数7 5找出其中比4大的最小数 5 5 4 、5 对换 8396 7 215 4后缀变为7421 将此后缀翻转 12 4 7接上前缀83965得到839651247 即839647521的下一个。例为后缀大于4的用橙色表示小于4的用绿色表示 找出比右边数字小的第一个数4Yiqiang Wei 431.5.11.5.1字典序法字典序法在在1,1,nn的全排列中的全排列中, ,n n-1 n n-1 321 321是最后一个排列是最后一个排列, ,其中介数其中介数是是( (n-1,n-1,n-2n-2,.,.,3,2,1),3,2,1)其序号为其序号为n-1kk!k=1另一方面可直接看出其序号为

37、n!-1 n-1 n-1于是n!-1= kk! 即 n!=kk! +1 k=1 k=1Yiqiang Wei 441.5.11.5.1字典序法字典序法一般而言，设一般而言，设P P是是1,1,nn的一个全排列。的一个全排列。P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pnj=maxi|PiPj对换Pj，Pk，将Pj+1Pk-1PjPk+1Pn翻转，P= P1P2Pj-1PkPnPk+1PjPk-1Pj+1即P的下一个Yiqiang Wei 451.5.11.5.1字典序法字典序法2)2)计算给定排列的序号计算给定排列的序号839647521的序号即先于此排列的排列的个数。

38、将先于此排列的排列按前缀分类按前缀分类。前缀先于8的排列的个数：78!第一位是8,先于83得的排列的个数：27!前2位是83,先于839得的排列的个数：66!先于此排列的的排列的个数：78!+27!+66!前3位是839,先于8396得的排列的个数：45!+45!前4位是8396,先于83964得的排列的个数：24!+24!前5位是83964,先于839647得的排列的个数：33!+33!前6位是839647,先于8396475得的排列的个数：22!+22!前7位是8396475,先于83964752得的排列的个数：11!+11!297191 前8位固定，则最后一位也随之固定 将8!,7!,1

39、!前面的系数抽出，放在一起得到 72642321此数的特点： 7：8的右边比8小的数的个数 2：3的右边比3小的数的个数6：9的右边比9小的数的个数4：6的右边比6小的数的个数2：4的右边比4小的数的个数3：7的右边比7小的数的个数2：5的右边比5小的数的个数1：2的右边比2小的数的个数72642321是计算排列839647521的序号的中间环节，我们称之为中介数中介数。这是一个很有用的概念。Yiqiang Wei 461.5.11.5.1字典序法字典序法一般而言一般而言, ,对于对于1,91,9的全排列中介数首位的取值为的全排列中介数首位的取值为0 08 8，第，第2 2位的取值为位的取值为

40、0 07 7，以此类推，第，以此类推，第8 8位的取值为位的取值为0 0、1 1。从而序号。从而序号可表示为：可表示为： n-1n-1 k ki i(n-i(n-i)!)! i=1 i=1k ki i：P Pi i的右边比的右边比P Pi i小的数的个数小的数的个数i=1,2,i=1,2,n-1,n-1Yiqiang Wei 471.5.11.5.1字典序法字典序法由中介数推出排列的算法由中介数推出排列的算法例 由72642321推算出839647521方法1：P1 P2 P3 P4 P5 P6 P7 P8 P9_ _ _ _ _ _ _ _ _P1=887+1=82+1=3P2=336+1=

41、7，但3已在P3左边出现，7+1=8，但8已在P3左边出现，8+1=9 P3=994+1=5，但3已经在P4左边出现，5+1=6 P4=662+1=3，但3已经在P5左边出现，3+1=4 P4=443+1=4，但3,4已经在P6左边出现，4+1+1=6，但6已经在P6左边出现， 6+1=7 P6=772+1=3，但3已经在P7左边出现，3+1=4，但4已经在P7左边出现， 4+1=5 P7=551+1=2 P8=2 P9=1 2 1这个过程比较麻烦(这酝酿着改进的可能)，该算法从左到右依次推出P1,P2,P9。下述算法依次定出1,2,3,9的位置。Yiqiang Wei 481.5.11.5.

42、1字典序法字典序法方法方法2-12-1：72642321中未出现0，1在最右边中介数右端加一个0扩成9位，先定1，每定一位，其左边未定位下加一点，从（位位下点数=0）的位中选最左最左的。7 2 6 4 2 3 2 1 0定 1 的位置1223344 55 66 77 8899由72642321推算出839647521Yiqiang Wei 491.5.11.5.1字典序法字典序法方法方法2-22-2：已定出上标，找左起第一个0，下标_由72642321推算出839647521 72642321-11111111=61531210_ _ _ _ _ _ _ _ 12 61531210 -1111

43、1110=504201003 50420100 -10000000=404201004 40420100 -10110000=303101005 30310100 -10110100=202000006 20200000 -10100000=101000007 10100000 -10100000=000000008 000000009以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数进位链（中介数的后继）递增进位制数Yiqiang Wei 501.5.21.5.2递增进位制数法递增进位制数法1)1)由排列求中介数由排列求中介数 在字典序法中，中介数的各位是由排列数的位

44、决定的.中介数位的下标与排列的位的下标一致。 在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2n)一致。Yiqiang Wei 511.5.21.5.2递增进位制数法递增进位制数法可看出可看出n-1n-1位的进位链。位的进位链。右端位逢右端位逢2 2进进1 1，右起第，右起第2 2位逢位逢3 3进进1 1，右起第右起第i i位逢位逢i+1i+1进进1 1，i=1,2,i=1,2,n-1.,n-1.这样的中介数我们称为这样的中介数我们称为递增进位制数递增进位制数。上面是由中介数求排列。上面是由中介数求排列。Yiqiang Wei 521.5.21.5

45、.2递增进位制数法递增进位制数法由序号（十进制数）求中介数（递增进位制数）如下：由序号（十进制数）求中介数（递增进位制数）如下： m=mm=m1 1, 0, 0 m n!-1 m n!-1 m m1 1=2m=2m2 2+k+kn-1n-1, 0 k, 0 kn-1 n-1 11 m m2 2=3m=3m3 3+k+kn-2n-2, 0 k, 0 kn-2 n-2 22 . m mn-2n-2=(n-1)m=(n-1)mn-1n-1+k+k2 2, 0 k, 0 k2 2 n-2n-2 m mn-1n-1=k=k1 1, 0 k, 0 k1 1 n-1n-1 p p1 1p p2 2p pn

46、n(k(k1 1k k2 2k kn-1n-1) m mYiqiang Wei 531.5.21.5.2递增进位制数法递增进位制数法在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。递增进位制数加以改进。为方便起见，令ai+1=kn-I，i=1,2,n-1(k1k2kn-1)=(anan-1a2)ai：i的右边比i小的数字的个数Yiqiang Wei 541.5.21.5.2递增进位制数法递增进位制数法在这样的定义下，有在这样的定义下，有8 83 396964 475752121(67342221)(67342

47、221)( (67342221)+1=(67342300)67342221)+1=(67342300) 8496175238496175236 68+8+7)7)7+7+3)3)6+6+4)4)5+5+2)2)4+4+2)2)3+3+2)2)2+12+1=279905=279905Yiqiang Wei 551.5.21.5.2递增进位制数法递增进位制数法由(anan-1a2)求p1p2pn。从大到小求出n,n-1,2,1的位置_ . _ n _ _ _ an个空格n的右边有an个空格。n-1的右边有an-1个空格。2的右边有a2个空格。最后一个空格就是1的位置。_ _/ VYiqiang W

48、ei 561.5.21.5.2递增进位制数法递增进位制数法_ _ _ _ _ _ _ _ _ 6 7 3 4 2 2 2 1 a9 a8 a7 a6 a5 a4 a3 a2_ _/ V 6个空格9_ _/ V 7个空格8 _ _/ V 3个空格765431 _ _/ V 4个空格 _ _/ V 2个空格 1个空格 序号 nm=ak(k-1)! k=221.5.31.5.3递减进位制数法递减进位制数法在递增进位制数法中，中介数的最低位是逢在递增进位制数法中，中介数的最低位是逢2 2进进1 1，进位频繁，这是一，进位频繁，这是一个缺点。个缺点。把递增进位制数翻转,就得到递减进位制数。(anan-1

49、a2)(a2a3an-1an) 839647521 (12224376) n nm=akn!/k!=n!ak/k! k=2 k=2(12224376)=13+2)4+2)5+2)6+4)7+3)8+7)9+6=340989 求下一个排列十分容易1.5.41.5.4邻位对换法邻位对换法递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向排列某

50、相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。左，而邻位对换法的换位是双向的。1.5.41.5.4邻位对换法邻位对换法这个算法可描述如下：这个算法可描述如下：对对1 1n-1n-1的每一个偶排列，的每一个偶排列，n n从右到左插入从右到左插入n n个空档个空档( (包括两端包括两端) )，生成，生成1 1n n的的n n 个排列。个排列。对对1 1n-1n-1的每一个奇排列，的每一个奇排列，n n从左到右插入从左到右插入n n个空档，生成个空档，生成1 1n n的的n n个排个排列。列。对对2,2,nn的每个数字都是如此。的每个数字都是如此。1.5.4

51、1.5.4邻位对换法邻位对换法 例例 839647521 836947521解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 ( ) b2 b3 b4 b5 b6 b7 b8 b91 0 1 2 1 3 7 22上箭头向左，2右边有1个数字比2小，b

52、2=13上箭头向右，3左边有0个数字比3小，b3=04上箭头向右，4左边有1个数字比4小，b4=15上箭头向右，5左边有2个数字比5小，b5=26上箭头向右，6左边有1个数字比6小，b6=17上箭头向左，7右边有3个数字比7小，b7=38上箭头向左，8右边有7个数字比8小，b8=79上箭头向右，9左边有2个数字比9小，b9=2 839647521的中介数为101213721.5.41.5.4邻位对换法邻位对换法a ak k(p)(p)：p p中中1 1k k排列的序号，排列的序号，a ak k(p(p) )的奇偶性与的奇偶性与1 1k k排列的奇偶性排列的奇偶性相同。相同。a9(p)=9a8(

53、p)+b9(p) =9(8a7(p)+b8(p)+b9(p)an(p)，bn(p)简写成an，bn1.5.41.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奇51.5.41.5.4邻位对换法邻位对换法序号序号=1=13 3+0+0) )4 4+1+1) )5 5+2+2) )6 6+1+1) )7 7+3+3) )8 8+7+7) )9 9+ +2 2=203393=203393(10121372)(10121372

54、)Yiqiang Wei 641.5.41.5.4邻位对换法邻位对换法8 83 39 96 64 47 75 52 21 1字字典典序序法法递递增增进进位位制制法法递递减减进进位位制制法法邻邻位位对对换换法法下下一一个个8 83 39 96 65 51 12 24 47 78 84 49 96 61 17 75 52 23 38 89 93 36 64 47 75 52 21 18 83 36 69 94 47 75 52 21 1中中介介数数7 72 26 64 42 23 32 21 1 6 67 73 34 42 22 22 21 1 1 12 22 22 24 43 37 76 6 1

55、 10 01 12 21 13 37 72 2序序 号号 297191279905340989203393Yiqiang Wei 651.6组合的生成组合的生成v设从1,n中取r元的组合全体为C(n,r).vC1C2CrC(n,r).不妨设C1C2CrviCi(nr+i), i=1,2,rv令j=maxi|Cinr+i.v则C1C2Cr的下一个组合为C1C2Cj-1(Cj+1)(Cj+2)(Cj+rj+1)v这等于给C(n,r)的元素建立了字典序。v12r的序号为0，n-r+1 n-r+2n的序号为( )1 _ _ n rYiqiang Wei 66v例 在C(10,4)中 4679的序号是v

56、首位小于4的组合的个数；首位是4，第2位小于6的组合的个数；前2位是46，第3位小于7的组合的个数；前3位是467，第4位小于9的组合的个数之和。v反之，也可以由序号求组合。Yiqiang Wei 671.6组合的生成组合的生成vA(m,l)：1,m的l-组合(或l-子集)。 第1个组合：1,2,l-1,l. 最后1个组合：1,2,l-1,mvA(n,k)=A(n-1,k)，A(n-1,k-1)nvA：将有序集A(或线性表)的顺序逆转的有序集。vAn：将A中每个元素(是集合)都与n求并的有序集_ _ _Yiqiang Wei 681.6组合的生成组合的生成v例 用两种方法计算1,n的无重不相邻

57、组合C(n,r)的计数问题v解法1 v 00100100100100 v其中不可含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-1Yiqiang Wei 691.6组合的生成组合的生成v以0结尾： r个10与n-2r个0的排列 r+n-2r = n-rv这样的排列有 ( )个v()+() = ( ) f(a1a2ar) = b1b2brn-r r n-r n-r n-r+1r-1 r rYiqiang Wei 701.6组合的生成组合的生成

58、v解法v任给a1a2arC(n,r),a1 a2 arv令f：a1a2arb1b2brvbi = ai-i+1, i= 1,2,r.v1b1 b2 br n-r+1,b1b2brC(n-r+1,r)vC(n,r) = C( n-r+1,r)Yiqiang Wei 711.7可重组合可重组合vC(n,r)的计数问题相当于r相同的球放入n个互异的盒子，每盒球的数目不同的方案的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。v易知所求计数为 = C(n+r-1,r)v即C(n,r)=( )=C(n-1,r)+C(n,r-1) 不含“” 至少含一个“” (n-1+r)! r!(

59、n-1)!n+r-1 r r个相同的球 / 001001100 / /n-1个相同的盒壁Yiqiang Wei 721.7可重组合可重组合v另证设a1a2arC(n,r)1a1a2 arn,v令C(n,r)上的f，使得bi=ai+i-1,i=1,2,r.v则b1b2br满足1b1b2brn+r-1 b1b2brC(n+r-1,r)vf： a1a2arb1b2brv显然f是单射，f ：b1b2bra1a2ar-1Yiqiang Wei 731.7可重组合可重组合vai=bi-i+1, i=1,2,r.va1a2arC(n,r)vf是单射C(n,r)C(n+r-1,r)vf 是单射 C(n,r)C

60、(n+r-1,r)v C(n,r)=C(n+r-1,r)v第二个证明可说一种“拉伸压缩”技巧。不可谓不巧妙。但仍不如第一证明来的明快，由此可见组合证明的功效。-1Yiqiang Wei 741.8若干等式及其组合意义若干等式及其组合意义v组合意义或组合证明，含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。Yiqiang Wei 751.8若干等式及其组合意义若干等式及其组合意义v1. C(n,r)=C(n,n-r) (1.7.1)v从1,n去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。v故C(n,r)=C(n,n-r)Yiqiang W