入门博弈组合数学

1、组合数学组合数学清华大学计算机 黄连生1999年7月前言 组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方.前言 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486前言 贾宪贾宪 北宋数学家（约北宋数学家（约11世纪）世纪） 著有黄帝著有黄帝九章细草、算法斅古集斅九章细草、算法斅古集斅 音音“笑（笑（“古古算法导引算法导引”）都已失传。杨辉著详解九章算）都已失传。杨辉著详解九章算法（法（1261年）中曾引贾宪的年）中曾引贾宪的“开方作法本源开方作法本源”图（即指数为正整数的二项式展开系数表，现图

2、（即指数为正整数的二项式展开系数表，现称称“杨辉三角形杨辉三角形”）和）和“增乘开方法增乘开方法”（求高（求高次幂的正根法）。前者比帕斯卡三角形早次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（年，后者比霍纳（William Geoge Horner，17861837）的方法（）的方法（1819年）早年）早770年。年。前言 1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。前言 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理

3、论体系。这与数学分析形成了对照。前言 本学期主要讲组合分析（计数和枚举）以及组合优化的一部分（线性规划的单纯形解法）。 组合分析是组合算法的基础。前言 组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。 但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。第一章排列组合1.1 加法法则与乘法法则1.1 加法法则与乘法法则 加法法则加法法则 设事件设事件A有有m种产生方式，种产生方式，事件事件B有有n种产生方式，则事件种产生方式，则事件A或或B之一之一有有m+n种产生方式。种产生方式。集合论语言：若 |A| = m , |B| = n , A

4、B = , 则 |AB| = m + n 。1.1 加法法则与乘法法则 例 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18 + 10 = 28 人。 例 北京每天直达上海的客车有 5 次，客机有 3 次， 则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。1.1 加法法则与乘法法则 乘法法则乘法法则 设事件设事件A有有m种产生式，种产生式，事件事件B有有n种产生方式，则事件种产生方式，则事件A与与B有有 m n种产生方式。种产生方式。集合论语言：若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。1

5、.1 加法法则与乘法法则例 某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有5 3 = 15 个。例 从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6 条道路。1.1 加法法则与乘法法则 例例 某种样式的运动服的着色由底色和装某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有橙、黄，条纹色可选黑、白，则共有42 = 8种着色方案。种着色方案。 若此例改成底色和条纹都用红、蓝、橙、若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数

6、就不是黄四种颜色的话，则，方案数就不是4 4 = 16， 而只有而只有 4 3 = 12 种。种。 在乘法法则中要注意事件在乘法法则中要注意事件 A 和和 事件事件 B 的的相互独立性。相互独立性。1.1 加法法则与乘法法则例例 1) 1)求小于求小于1000010000的含的含1 1的正整数的个数的正整数的个数 2) 2)求小于求小于1000010000的含的含0 0的正整数的个数的正整数的个数1)小于10000的不含1的正整数可看做4位数,但0000除外. 故有999916560个. 含1的有：99996560=3439个另: 全部4位数有10 个,不含1的四位数有9 个, 含1的4位数为

7、两个的差: 10 9 = 3439个4 44 42)“含0”和“含1”不可直接套用。0019含1但不含0。 在组合的习题中有许多类似的隐含的规定，要特别留神。 不含不含0的的1位数有位数有9个，个，2位数有位数有9 个，个，3位数有位数有9 个，个，4位数有位数有9 个个 不含不含0小于小于10000的正整数有的正整数有 9+9 +9 +9 =(9 1)/(91)=7380个个含含0小于小于10000的正整数有的正整数有 99997380=2619个个23423451.2排列与组合定义定义 从从n n个不同的元素中，取个不同的元素中，取r r个不重个不重复的元素，按次序排列，称为从复的元素，按

8、次序排列，称为从n n个中取个中取r r个的无重排列。排列的全体组成的集合个的无重排列。排列的全体组成的集合用用P(n,r)P(n,r)表示。排列的个数用表示。排列的个数用P(n,r)P(n,r)表表示。当示。当r=nr=n时称为全排列。一般不说可重时称为全排列。一般不说可重即无重。可重排列的相应记号为即无重。可重排列的相应记号为 - - P(n,r),P(n,r) P(n,r),P(n,r)。1.2排列与组合定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)表示，对应于可重组

9、合 -有记号C(n,r),C(n,r)。1.2排列与组合从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，第r个有n-r+1种选择。故有 P(n,r)=n(n-1)(n-r+1)有时也用nr记n(n-1)(n-r+1)1.2排列与组合若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有 C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=nr/r!=( )=易见 P(n,r)=nnrr n!r!(n-r)!若球不同

10、，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有 C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=nr/r!=( )=易见 P(n,r)=n1.2排列与组合例例 有有5 5本不同的日文书，本不同的日文书，7 7本不同本不同的英文书，的英文书，1010本不同的中文书。本不同的中文书。1)1)取取2 2本不同文字的书；本不同文字的书；2)2)取取2 2本相同文字的书；本相同文字的书；3)3)任取两本书任取两本书1.2排列与组合5+7+10 2解解 1) 5 1) 57+57+510+710+710=15

11、5;10=155; 2) C(5,2)+C(7,2)+C(10,2) 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=( )1.2排列与组合 求r1个1，r2个2，rt个t的排列数，设r1+r2+rt=n,设此排列数为P(n;r1,r2,rt),对1，2，t分别加下标，得到P(n；r1,r2,rt)r1!r2!rt! = n! P(n；r1,r2,rt)= =( ) n!r1!r2!rt! nr1 r2 rt1.2排列与组合 从n个中取r个的圆排列的排列数为 P(n,r)/

12、r , 2rn 以4个元素为例 12 4 3 1234 12 4 3 2341 12 4 3 3412 12 4 3 41231.2排列与组合 从n个中取r个的项链排列的排列数为 P(n,r)/2r, 3rn 项链排列就是说排列的方法和项链一样,在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。 例 下面两种方式实际上表示的都是3个元素的同一种排列。 1 1 2 3 3 21.2排列与组合例例 从从1,3001,300中取中取3 3个不同的数，使这个不同的数，使这3 3个数的和能被个数的和能被3 3整除，有多少种方案？整除，有多少种方案？解解 将将1,300分成分成3类：类：

13、 A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)=3,6,9,300. 要满足条件，有四种解法：要满足条件，有四种解法： 1)3个数同属于个数同属于A;2)3个数同属于个数同属于B 3)3个数同属于个数同属于C;4)A,B,C各取一数各取一数.故共有3C(100,3)+100 =485100 =148510031.2排列与组合例例 某车站有某车站有6 6个入口处，每个入口处每个入口处，每个入口处每次只能进一人，一组次只能进一人，一组9 9个人进站的方案有多个人进站的方案有多少？少？解一进站方案表示成：0001100

14、1010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。1.2排列与组合解法1标号可产生5!个14个元的全排列。故若设x为所求方案，则 x5!=14! x=14!/5!=7264857601.2排列与组合解法2在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。故C(14,5)9!即所求1.2排列与组合解法3把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时

15、在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。以此类推，9号有14种选择。 9故所求方案为61.3 Stirling近似公式 组合计数的渐进值问题是组合论的一个研究方向。 Stirling公式给出一个求n!的近似公式，它对从事计算和理论分析都是有意义的。1.3 Stirling近似公式 1)Wallis公式令Ik= sin xdx.显然I0= ,I1=1.k2时，Ik=cosxsin x| + (k1)cos xsin xdx=0+(k1) (1sin x)sin xdx=(k1)(Ik2Ik)k 2k-1 2 0 2 0 2 0 2 02 k-22 k-2故 Ik

16、 = Ik-2 (1-3-1)k-1 k1.3 Stirling近似公式令n! = 135(n-2)n，n是奇数。246(n-2)n，n是偶数。(1-3-2)由(1-3-1)， I1, k是奇数 Ik= I0, k是偶数(k-1)! k!(k-1)! k!当x(0,/2)时， sin x sin x因而 I2k+1I2kI2k-1, k=1,2,。k+1 k1.3 Stirling近似公式 由(1-3-2) ， (2k)! (2k-1)! (2k-2)!(2k+1)! (2k)! 2 (2k-1)!1 1. 2 (2k)!(2k-1)! 1 2k+12k+1 2k2k1.3 Stirling近

17、似公式 所以lim = , (2k)!(2k-1)! 1 2k+12 2klim = ,(2k)!(2k)! (2k)! 1 2k+12 2klim = 。(1-10-3)2 (k!) (2k)! 1 2k+12 2k2k 21.3 Stirling近似公式 2)stirling2)stirling公式公式y y=lnx 0 1 2 3 n-1 n x1.3 Stirling近似公式 令An=lnxdx=xlnx| dx=nlnnn+1 (1-3-4) tn=ln1+ln2+ln(n1)+lnn=ln(n!)lnn (1-3-5) tn的几何意义是由x轴,x=n,以及连接(1,0), (2,l

18、n2),(n1,ln(n1),(n,lnn)诸点而成的折线围成的面积。n n n1 1 11 12 2121.3 Stirling近似公式 Tn=+ln2+ln(n1)+lnn (1-3-6)1 18 2Tn是由三部分面积之和构成的。一是曲线y=lnx在x=k点的切线和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轴包围的矩形面积。因而有 tnAnTn (1-3-7)1212121.3 Stirling近似公式 令bn=An tn.序列b1,b2,是单调增，而且

19、有上界，故有极限，令 limbn=b1 由(1-3-4),(1-3-5) 得 bn=nlnnn+1ln(n!)+lnn = lnnn+1ln(n!)+ln n ln(n!)=1bn+ lnn ln n lne n!=e n ()(1-3-8)0AntnTntn=18n12nn n1-bnnen121.3 Stirling近似公式 令n=e ,limn=. 将(1-3-8)代入(1-3-3),整理得 = 2 . 所以n! 2n ()n1-bnnen1.4模型转换 “一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。 如我们说A集合有n个元素 |A|=n，无非是建立了将A中元与

20、1,n元一一对应的关系。 在组合计数时往往借助于一一对应实现模型转换。 比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。1.4模型转换 例例简单格路问题 |(0,0)(m,n)|=( )从 (0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？m+n my (m,n).0 . . . x1.4模型转换 无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。 则(0,0)(m,n)的每一条路径可表示为m 个x与n个y的一个有重排列。将每一个有重排列的x与y分别

21、编号，可得m!n!个m+n元的无重全排列。1.4模型转换 设所求方案数为p(m+n；m，n) 则P(m+n；m，n)m!n!=(m+n)! 故P(m+n;m,n)= = ( ) =( ) =C(m+n,m) 设ca,db,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=( )(m+n)! m+n m+n m!n! m n(c-a)+(d-b) c-a (c,d)(a,b)1.4模型转换 例例 在上例的基础上若设在上例的基础上若设mn，求，求(0,1)点到点到(m,n)点不接触对角线点不接触对角线x=y的格路的的格路的数目数目 (“接触接触”包括包括“穿过穿过”) 从从(0,1

22、)点到点到(m,n)点的格路，有的接触点的格路，有的接触x=y，有的不接触。，有的不接触。 对每一条接触对每一条接触x=y的格路，做的格路，做(0,1)点到第点到第一个接触点部分关于一个接触点部分关于x=y的对称格路，这的对称格路，这样得到一条从样得到一条从(1,0)到到(m,n)的格路。的格路。1.4模型转换 容易看出从(0,1)到(m,n)接触x=y的格路与 (1,0)到(m,n)的格路(必穿过x=y)一一对应y y=x (m,n)0 (1,0) x(0,1). .y x-y=1 (m,n) x(0,0) (1,-1). . .1.4模型转换 故所求格路数为( )( ) = = ( ) =

23、 ( )=(1 )( ) = ( )m+n-1 m+n-1 m m-1(m+n-1)! (m+n-1)! (m+n-1)! 1 1m!(n-1)! (m-1)!n! (m-1)!(n-1)! m nm+n-1 m+n-1 m m n-m m n n m+n-1 m n-m n 1.4模型转换 若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得xy=1，(0,0)关于xy=1的对称点为(1,-1). 所求格路数为 ( )( ) = = ( )m+n m+n m m-1(m+n)! (m+n)! n+1-m m!n! (m-1)!(n+1)! n+1 m+n m 格路也是一种常用模型1.4

24、模型转换 例例 CnH2n+2是碳氢化合物是碳氢化合物,随着随着n的不同的不同有下列不同的枝链：有下列不同的枝链： H |H C H | H H |H C H |H C H | H H |H C H |H C H |H C H | Hn=1甲烷 n=2 乙烷 n=3 丙烷1.4模型转换 H |H C H |H C H |H C H |H C H | H H | HH C H | |H C C H | |H C H | H Hn=4 丁烷 n=4异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应

25、有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.1.4模型转换 例例 在在100名选手之间进行淘汰赛名选手之间进行淘汰赛(即一场即一场的比赛结果，失败者退出比赛的比赛结果，失败者退出比赛),最后产生最后产生一名冠军，问要举行几场比赛？一名冠军，问要举行几场比赛？ 解解 一种常见的思路是按轮计场，费事。一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛另一种思路是淘汰的选手与比赛(按场计按场计)集一一对应。集一一对应。99场比赛。场比赛。1.4模型转换 例例 (Cayley定理定理) n个有标号的顶点的树个有标号的顶点的树的数目等于的数目等于n

26、。n-2 生长点不是叶子,每个生长点是1,n中的任一元.有n种选择。两个顶点的树是唯一的。1.4模型转换 | | 41 2 5 3逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子，是内点)形成一个序列，序列的长度为n-2例例 给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边) 第一次摘掉，为相邻的顶点，得到序列的第一个数3以此类推，得到序列31551,长度为72 = 5这是由树形成序列的过程。1.4模型转换 由序列形成树的过程：由序列31551得到一个新序列111233455567生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序

27、排序的序列1234567，序列的长度为5+2(即n+2)，然后将11355按照大小插入到序列1234567中，得到111233455567然后将两个序列排在一起 315511112334555671.4模型转换 31551111233455567 15511113455567 55111455567 51115567 11157 17第一步推导：将上下两个序列同时去掉上行序列的第一个元素3(用黄色表示)，去掉下行序列的第一个无重复的元素2(用红色表示)。生成一条边()。依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。 1.4模型转换 上述算法描述：给定序列b=(b1b2

28、bn-2) 设a=(123n-1 n)将b的各位插入a,得a,对( )做操作。a是2n-2个元的可重非减序列。ba操作是从a中去掉最小无重元，设为a1,再从b和a中各去掉一个b中的第一个元素，设为b1，则无序对(a1,b1)是一条边。重复这一操作，得n-2条边，最后a中还剩一条边，共 n-1条边，正好构成一个树。b中每去掉一个元，a中去掉2个元。1.4模型转换 由算法知由树T得b=(b1b2bn-2) ，反之，由b可得T。即 f：Tb 是一一对应。 由序列确定的长边过程是不会形成回路的。因任意长出的边 (u , v) 若属于某回路，此回路中必有一条最早生成的边，不妨就设为 (u , v) ，必

29、须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故由( )得到的边必构成一个n个顶点的树。ba1.4模型转换 证 由一棵n个顶点的树可得到一个长度为n2的序列，且不同的树对应的序列 不同*，因此 | T | n 。 *对n用归纳法可证 反之，由一个长度为n2的序列(每个元素为1 n 的一个整数)，可得到一棵树，且不同的序列对应的树是不同的，因此 n | T | | T | = n #n-2n-2n-21.5全排列的生成算法 就是对于给就是对于给定的字符集，用有效的方法将定的字符集，用有效的方法将所有可能的全排列无重复无遗所有可能的全排

30、列无重复无遗漏地枚举出来。漏地枚举出来。 全排列的生成算法全排列的生成算法1.5全排列的生成算法这里介绍全排列算法四种：(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法1.5.1字典序法 对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。1.5.1字典序法 例例 字符集字符集1,2,3,1,2,3,较小的数字较较小的数字较先先, ,这样按字典序生成的全排列是这样按字典序生成的全排列是: :123,132,213,231,312,321123,132,213,231,312,321。 一个全排列可看做一个字符串，字一

31、个全排列可看做一个字符串，字符串可有前缀、后缀。符串可有前缀、后缀。1.5.1字典序法1）生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。1.5.1字典序法 例例 839647521 839647521是是1-91-9的排列。的排列。1919的排列最前面的是的排列最前面的是123456789123456789，最后面，最后面的是的是987654321987654321，从右向左扫描若都是，从右向左扫描若都是增的，就到了增的，就到了987654321987654321，也就没有下，也就没有下一

32、个了。否则找出第一次出现下降的一个了。否则找出第一次出现下降的位置。位置。1.5.1字典序法求839647521的下一个排列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字典序法在1,n的全排列中,n n-1 321是最后一个排列,其中介数是(n-1,n-2,.,3,2,1)其序号为n-1kk

33、!k=1另一方面可直接看出其序号为n!-1 n-1 n-1于是n!-1= kk! 即 n!=kk! +1 k=1 k=11.5.1字典序法一般而言，设P是1,n的一个全排列。P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pnj=maxi|PiPj对换Pj，Pk，将Pj+1Pk-1PjPk+1Pn翻转，P= P1P2Pj-1PkPnPk+1PjPk-1Pj+1即P的下一个1.5.1字典序法2)计算给定排列的序号839647521的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类。前缀先于8的排列的个数：78!第一位是8,先于83得的排列的个数：27!前2位是83,先

34、于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!前面的系数抽出，放在一起得到 72642321此数的特点： 7：8的右边比8小的数的个数 2：3的右边比3小的数的个数6：9的

35、右边比9小的数的个数4：6的右边比6小的数的个数2：4的右边比4小的数的个数3：7的右边比7小的数的个数2：5的右边比5小的数的个数1：2的右边比2小的数的个数72642321是计算排列839647521的序号的中间环节，我们称之为中介数。这是一个很有用的概念。1.5.1字典序法一般而言,对于1,9的全排列中介数首位的取值为08，第2位的取值为07，以此类推，第8位的取值为0、1。从而序号可表示为： n-1 ki(n-i)! i=1ki：Pi的右边比Pi小的数的个数i=1,2,n-11.5.1字典序法由中介数推出排列的算法例 由72642321推算出839647521方法1：P1 P2 P3

36、P4 P5 P6 P7 P8 P9_ _ _ _ _ _ _ _ _P1=887+1=82+1=3P2=336+1=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这个过程比较麻烦(这酝酿着改进的可能)，该算法从

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

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

39、数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2n)一致。1.5.2递增进位制数法可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，右起第i位逢i+1进1，i=1,2,n-1.这样的中介数我们称为递增进位制数。上面是由中介数求排列。1.5.2递增进位制数法由序号（十进制数）求中介数（递增进位制数）如下： m=m1, 0 m n!-1 m1=2m2+kn-1, 0 kn-1 1 m2=3m3+kn-2, 0 kn-2 2 . mn-2=(n-1)mn-1+k2, 0 k2 n-2 mn-1=k1, 0 k1 n-1 p1p2pn(k1k2kn-1) m1.5.2递

40、增进位制数法在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。为方便起见，令ai+1=kn-I，i=1,2,n-1(k1k2kn-1)=(anan-1a2)ai：i的右边比i小的数字的个数1.5.2递增进位制数法在这样的定义下，有839647521(67342221)(67342221)+1=(67342300) 84961752368+7)7+3)6+4)5+2)4+2)3+2)2+1=2799051.5.2递增进位制数法由(anan-1a2)求p1p2pn。从大到小求出n,n-1,2,1的位置_ . _ n _ _ _ an个空格n的右边有an个空格。n-1的右

41、边有an-1个空格。2的右边有a2个空格。最后一个空格就是1的位置。_ _/ V1.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.3递减进位制数法在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。(anan-1a2)(a2a3an-1an) 839647521

42、(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.4邻位对换法递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。1.5.4邻位对换法这个算法可描述如下：对1n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1n的n 个排列。对1n-1的每一个奇排列，n从左到右插入n个空

43、档，生成1n的n个排列。对2,n的每个数字都是如此。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

44、上箭头向左，2右边有1个数字比2小，b2=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.4邻位对换法ak(p)：p中1k排列的序号，ak(p)的奇偶性与1k排列的奇偶性相同。a9(p)=9a8(p)+b9(p) =9(8a7(p)+b8(p)+b9(p)an(p)，b

45、n(p)简写成an，bn1.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.4邻位对换法序号=13+0)4+1)5+2)6+1)7+3)8+7)9+2=203393(10121372)1.5.4邻位对换法8 83 39 96 64 47 75 52 21 1字字典典序序法法递递增增进进位位制制法法递递减减进进位位制制法法邻邻位位对对换换法法下下一一个个8 83 39 96 65 51 12 24 47 78

46、 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 10 01 12 21 13 37 72 2序序 号号 2971912799053409892033931.6组合的生成 设从1,n中取r元的组合全体为C(n,r). C1C2CrC(n,r).不妨设C1C2Cr iCi(nr+i), i=1,2,r 令j=maxi|Cin

47、r+i. 则C1C2Cr的下一个组合为C1C2Cj-1(Cj+1)(Cj+2)(Cj+rj+1) 这等于给C(n,r)的元素建立了字典序。1.6组合的生成 例 用两种方法计算1,n的无重不相邻组合C(n,r)的计数问题 解法1 00100100100100 其中不可含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-11.6组合的生成 以0结尾： r个10与n-2r个0的排列 r+n-2r = n-r 这样的排列有 ( )个 ()+() = (

48、 ) f(a1a2ar) = b1b2brn-r r n-r n-r n-r+1r-1 r r1.6组合的生成 解法 任给a1a2arC(n,r),a1 a2 ar 令f：a1a2arb1b2br bi = ai-i+1, i= 1,2,r. 1b1 b2 br n-r+1,b1b2brC(n-r+1,r) C(n,r) = C( n-r+1,r)1.7可重组合 C(n,r)的计数问题相当于r相同的球放入n个互异的盒子，每盒球的数目不同的方案的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。 易知所求计数为 = C(n+r-1,r) 即C(n,r)=( )=C(n-1,

49、r)+C(n,r-1) 不含“” 至少含一个“” (n-1+r)! r!(n-1)!n+r-1 r r个相同的球 / 001001100 / /n-1个相同的盒壁1.7可重组合 另证设a1a2arC(n,r)1a1a2 arn, 令C(n,r)上的f，使得bi=ai+i-1,i=1,2,r. 则b1b2br满足1b1b2brn+r-1 b1b2brC(n+r-1,r) f： a1a2arb1b2br 显然f是单射，f ：b1b2bra1a2ar-11.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)

50、C(n+r-1,r) C(n,r)=C(n+r-1,r) 第二个证明可说一种“拉伸压缩”技巧。不可谓不巧妙。但仍不如第一证明来的明快，由此可见组合证明的功效。-11.8若干等式及其组合意义 组合意义或组合证明，含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。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)1.8若干等式及其组合意义 2. C(n,r)=C(n-1,r)+C(n-1,r-1) (1.7.2) 从1,n取

51、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)1.8若干等式及其组合意义 杨辉三角除了(0,0)点，都满足此递推式 0rn,n0r C(n,r)= 1,r = 00,0nr,r0nn0且r0 C(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|-1n+r nr r!1.8若干等式及其组合意义 3.

52、( )+( )+( )+( )=( ) (1.7.3) 1可从(7.2)推论，也可做一下组合证明从1,n+r+1取a1a2anan+1，设a1a2an an+1，可按a1的取值分类：a1=1,2,3,r,r+1. a1=1, a2an+1取自2,n+r+1 有( )种取法n n+1 n+2 n+r n+r+1n n n n nn+r na1=2, a2an+1取自3,n+r+1 有( )种取法n+r-1 n a1=r, a2an+1取自r+1,n+r+1 有( )种取法n+1 na1=r+1, a2an+1取自r+2,n+r+1 有( )种取法nn也可看做按含1不含1，含2不含2,含r不含r的

53、不断分类1.8若干等式及其组合意义 2从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上) ( ),( ),( ) 故有.( )+( )+( )+( )=( ) n n+1 n+rn n nn n+1 n+2 n+r n+r+1n n n n nr (n+1,r) . . .(0,0) n n+11.8若干等式及其组合意义 3 可重组合. 1,n+2的C(n+2,r)模型 ( ) 不含1,含1个1,含2个1,含r个1 C( ),C( ),C( ),C( ) ( ), ( ), ( ), ( )n+r+1 rn+1 n+1 n+1 n+1 r r-1 r-2 0

54、n+r n+r-1 n+r-2 n r r-1 r-2 01.8若干等式及其组合意义 4. ( )( )=( )( ) (1.7.4) 选政治局选政治局,再选常委再选常委,n个中央委员选出个中央委员选出l名政治局委员名政治局委员,再从其中选出再从其中选出r名常委名常委 选常委选常委,再选非常委政治局委员再选非常委政治局委员 两种选法都无遗漏两种选法都无遗漏,无重复地给出可能的无重复地给出可能的方案，应该相等。方案，应该相等。n l n n-rl r r l-r1.8若干等式及其组合意义 5. ( )+( )+( )=2 , m0, (1.7.5) 证证1(x+y) =()x y ,令令x=y=

55、1,得得(1.7.5) 组合证组合证1 1,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)各点的走法各各点的走法各有有( ),( ),( ),( ),( ),( )种种m m m m0 1 m m k m-k m m kk=0mmm m m m m m 0 1 2 m-2 m-1

56、m1.8若干等式及其组合意义 6. ( )-( )+( )-( )=0 (1.7.6) 证证1 在在(x+y)=( )x y 中令中令x=1,y=-1即得即得.n n n n0 1 2 nn n-k knk nk=01.8若干等式及其组合意义 证证2 2 在在1,n1,n的所有组合中的所有组合中, , 含含1 1的组合的组合不含不含1 1的组合的组合. .有有1111对应关系。在任一含对应关系。在任一含1 1组合及与之对组合及与之对应的不含应的不含1 1组合中，必有一奇数个元组合中，必有一奇数个元的组合与一偶数个元的组合。将含的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数奇数个元

57、的组合做成集，将含偶数阁元的组合做成另一集。此二集的阁元的组合做成另一集。此二集的元数相等。元数相等。()=()=() )n ni ii奇 i偶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+n m n m n m n

58、r 0 r 1 r-1 r 0m nr-l lm+n m n r r-l lP(m-r,r) (m+n-r,r) (m-r+l,r-l) l=0,1,2,r Q(m,0) rl=01.8若干等式及其组合意义 8. 在在7.中令中令r=mn,再将再将( )换成换成() 得得()=( )( )+( )( )+( )( )m mk m-km+n m n m n m n m 0 0 1 1 m m 1.9应用举例 例某保密装置须同时使用若干把不同例某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若的钥匙才能打开。现有人，每人持若干钥匙。须人到场，所备钥匙才能开干钥匙。须人到场，所备钥匙才能

59、开锁。问至少有多少把不同的钥匙？锁。问至少有多少把不同的钥匙？每人至少持几把钥匙？每人至少持几把钥匙？ 解解 每人至少缺把钥匙，且每人每人至少缺把钥匙，且每人所缺钥匙不同。故至少共有所缺钥匙不同。故至少共有( )=35把不把不同的钥匙。同的钥匙。731.9应用举例 任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁。故每人至少持()20把不同的钥匙。 为加深理解，举一个较简单的例子：人中人到场，所求如上。共有()=6把不同的钥匙。每人有()=3把钥匙。（见下页图）1.9应用举例 钥 匙 A 人 B C D 1.9应用举例 例例 有有4个相同质点个相同质点,总能量为总能量为4E0,E0是常是常数。每个质点所具能量为数。每个质点所具能量为kE0,k=0,1,2,3,4. A)若能级为若能级为kE0的质点可有的质点可有k +1种状态，种状态，