第一章 排列与组合

1、桂林理工大学理学院桂林理工大学理学院 谢海谢海研究生课程研究生课程组合数学组合数学课程简介课程简介 本课程针对计算机科学中的一个重要学本课程针对计算机科学中的一个重要学科科组合数学，组合数学是数学的一个分组合数学，组合数学是数学的一个分支，它研究事物在结定模式下的配置，研究支，它研究事物在结定模式下的配置，研究这种配置的存在性，所有可能配置的计数和这种配置的存在性，所有可能配置的计数和分类以及配置的各种性质。组合数学在计算分类以及配置的各种性质。组合数学在计算机科学中有着极其广泛的应用。机科学中有着极其广泛的应用。 组合学问题求解方法层出不穷、干变万组合学问题求解方法层出不穷、干变万化，应以理

2、解为基础，善于总结各种技巧，化，应以理解为基础，善于总结各种技巧，掌握科学的组织和推理方法。掌握科学的组织和推理方法。 组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方.前言前言 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486 1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。 组合数学是一个迷人的数学分支, 它起源于古代的游戏和美学鉴赏. 在现代科学技术的发展中, 人们会面临各种各样的组合数学问题. 组合数学在计算机

3、科学中发挥着出极为重要的作用. 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。组合数学的基本内容组合数学的基本内容 组合数学关心的事情是要按照一定方式 “配置”一组事物，主要考虑以下几方面的问题。存在性：(2) 计数与分类：主要内容(3) 构造算法：部分内容(1) (4) 算法优化： 如果人们想把有限多个对象按照它们所应满足的条件来进行安排，当符合要求的安排并非显然存在或显然不存在时，首要的问题就是要证明或者否定它的存在。这就是存在性问题存在性问题。如果所要求的安排存在，则可能

4、有多种不同的安排，这又经常给人们提出这样的问题：有多少种可能的安排方案？如何对安排的方案进行分类？这就是计数问题计数问题。如果一个组合问题有解，则往往需要给出求其某一特定解的算法，这就是所谓的构造性问题构造性问题。如果算法很多，就需要在一定的条件下找出一个或者几个最优或近乎最优的安排方案，这就是优化问题优化问题。 组合数学研究的组合数学研究的中心问题中心问题是按照一定的规则来是按照一定的规则来安排有限多个对象。安排有限多个对象。 组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。 但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。内容：排

5、列与组合，递推关系与母函数，内容：排列与组合，递推关系与母函数， 容容 斥原理与鸽巢原理，斥原理与鸽巢原理， Burnside引理与引理与 Plya定理定理 意义：方法意义：方法(用于编程用于编程), 素质素质(全面，细致全面，细致)难点：方法的应用难点：方法的应用, 例题的题型和思路例题的题型和思路教材：卢开澄教材：卢开澄 卢华明编著卢华明编著 组合数学（第组合数学（第4版）版） 清华大学出版社清华大学出版社讲课：听课为主讲课：听课为主, 课件较完整课件较完整, 板书和说明板书和说明 多种思路的分析，实例的直观理解多种思路的分析，实例的直观理解使用教材：使用教材：第一章第一章 排列组合排列组

6、合1.1 加法法则与乘法法则加法法则与乘法法则加法法则加法法则 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。乘法法则乘法法则 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m n种产生方式。集合论语言：若 |A| = m ，|B| = n，AB = (a,b) | a A,b B，则 |A B| = m n 。 例例1-1 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42 = 8种着色方案

7、。 若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是4 4 = 16， 而只有 4 3 = 12 种。 在乘法法则中要注意事件事件 A 和和 事件事件 B 的相的相互独立性互独立性。另: 全部4位数有 个，不含1的四位数有 个，含1的4位数为两个的差: 。 要点：含要点：含1的总数不含的总数不含1的的49343991044410例例1-2 1)求小于10000的含1的正整数的个数； 2)求小于10000的含0的正整数的个数。解：1)小于10000的不含1的正整数可看做4位数，但0000除外。 故有999916560个。 含1的有：99996560=3439个。1)小于100

8、的不含1的正整数可看做2位数，但00除外。 故有99180个。(00,02,09, 20,22,29, 30,99) 含1的有：9980=19个(01,11,21,91, 10,12,13,19)2)“含含0”和和“含含1”不可直接套用。不可直接套用。0019含1但不含0。 直接套用直接套用, 含含0的的(?)有：有：9980=19个个 (00,10,20,90, 01,02,03,09) 其中其中:黄色黄色的的10个不是含个不是含0的。的。因此因此,修改计算方法为修改计算方法为: 不含不含0的的1位数有位数有9个，个，(1,2,9) 2位数有位数有 个，个，(11,12,19, 21,99)

9、不含不含0小于小于100的正整数有的正整数有81+9=90 含含0小于小于100的正整数有的正整数有9990=9个个 (10,20,90) 292)“含含0”和和“含含1”不可直接套用。不可直接套用。0019含1但不含0。 在组合的习题中有许多类似的在组合的习题中有许多类似的隐含规定规定，要特别留神。，要特别留神。 不含不含0的的1位数有位数有9个，个，2位数有位数有 个，个，3位数有位数有 个，个，4位数有位数有 个个 不含不含0小于小于10000的正整数有的正整数有 含含0小于小于10000的正整数有的正整数有 99997380=2619个个39297380) 19/() 19(99995

10、43249n2例例1-3 长度为n的0，1符号串的数目为 。例如：n3，有8个 000,001,010,011,100,101,110,111。个nninniaaaaa2222., 2 , 1,1 , 0,21解：设由乘法规则, 40, 20, 30lllll60534除尽n的整数的个数是42313117n例例1-4 求除尽n的整数的个数。解：除尽n的整数是例例1-51-5 有a,b,c,d,e这5个字,从中取6个构成一组字符串，要求: (1)第1个和第6个必须是子音b,c,d；(2)每一字符串必有a,e两个母音，且a,e不相邻；(3)相邻两子音不允许相同。求字符串数

11、目。解:格式(2,4): 子 母 子 母 子 子 格式(2,5): 子 母 子 子 母 子 格式(3,5): 子 子 母 子 母 子 格式(2,4): 格式(2,5): 格式(3,5):333333232332232332232323232323注意：条件(2)应改为：每个字符串恰好有不相邻的两位是母音a或e。否则，理解为这两位分别为a和e。64823333 由加法法则：例例1-61-6 有5本不同的日文书，7本不同的英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书。解：解： 注意：加法和乘法 1) 57+510+710=155; 2) C(5,2)+

12、C(7,2)+C(10,2) =10+21+45=76; 3) 155+76=231= =C(5+7+10,2)=C(22,2) 1.2 一一对应一一对应 “一一对应一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。 如我们说A集合有n个元素 |A|=n，无非是建立了将A中元与1,n元一一对应的关系。 在组合计数时往往借助于一一对应实现模型转换。 比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。 例例1-7 CnH2n+2是碳氢化合物,随着n的不同有下列不同的枝链： H |H C H | H H |H C H |H C H | H H

13、 |H C H |H C H |H C H | Hn=1甲烷 n=2 乙烷 n=3 丙烷 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个顶点是叶子。 对于这样结构的每一棵树，就对应有一种特定的化合物。 从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2。 例例1-8 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛)，最后产生一名冠军，问要举行几

14、场比赛？ 解：解：一种常见的思路是按轮计场，费事。 各轮场数502512632199 剩余选手数目：25, 13, 7, 4, 2, 1 另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。 例例1- 9 (Cayley定理定理) n个有标号的顶点的树的数目等于 。2nn解：两个顶点的树是唯一的。12 n3时，数的数目3。 123，132，2132nn思路：思路：n点树 一一对应一一对应 长度n-2序列， n个字母的长度n-2序列的数目是 。逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子，是内点)形成一个序列，序列的长度为n-2 | | 41 2 5 3给定一棵有标号的树边上的标号

15、表示摘去叶的顺序。(摘去一个叶子相应去掉一条边) 第一次摘掉，为相邻的顶点，得到序列的第一个数3，以此类推，消去23465，得到序列31551，长度为72 = 5，这是由树形成序列的过程。 由序列形成树的过程：由序列形成树的过程：由序列31551得到一个新序列111233455567生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序排序的序列1234567，序列的长度为5+2(即n)，然后将11355按照大小插入到序列1234567中，得到111233455567然后将两个序列排在一起 31551111233455567 31551111233455567

16、 15511113455567 55111455567 51115567 11157 17第一步推导：将上下两个序列同时去掉上行序列的第一个元素3(用黄色表示)，去掉下行序列的第一个无重复的元素2(用红色表示)。生成一条边()。由上序列确定3（黄色），再确定2（红色），在下序列最小无重元，于是生成边23。（并消除红黄色点。）依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。 （生成边的序列23，13，45，56，15，17） 上述算法描述：给定序列b=(b1b2bn-2) ，设a=(123n-1 n)将b的各位插入a，得a，对( )做操作。a是2n-2个元的可重非减序列。

17、ba操作是从a中去掉最小无重元，设为a1,再从b和a中各去掉一个b中的第一个元素，设为b1，则无序对(a1,b1)是一条边。重复这一操作，得n-2条边，最后a中还剩一条边，共 n-1条边，正好构成一个树。b中每去掉一个元，a中去掉2个元。 由算法知由树T得b=(b1b2bn-2) ， 反之，由b可得T。 即 f：Tb 是一一对应。 由序列确定的长边过程是不会形成回路的。ba因任意长出的边 (u , v) 若属于某回路，此回路中必有一条最早生成的边，不妨就设为 (u , v) ，必须使u，v都在长出的边中重复出现，但照算法u，v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故由(

18、)得到的边必构成一个n个顶点的树。 证：由一棵n个顶点的树可得到一个长度为n2的序列，且不同的树对应的序列 不同*，因此 。 *对n用归纳法可证。 反之，由一个长度为n2的序列(每个元素为1 n 的一个整数)，可得到一棵树，且不同的序列对应的树是不同的，因此 22nnnTnT2nnT1.1.3 3 排列与组合排列与组合当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为 。),(rnP定义定义 从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重无重排列排列。 nrP排列的个数用P(n,r)或 表示。),(rnC对应于可重组合有记号 。定义定义 从n个不同元素

19、中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合无重组合。rn组合的个数用C(n,r)或 表示。从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记 P(n,r)=n(n-1)(n-r+1)=n!/(n-r)!（1）从n个中取r个的无重排列 P(n,r)=n(n-1)(n-r+1)例：n=3, r=2AB, BA, CA,AC, BC, CB。（2）从n个中取r个的可重排列rnrnP),(例

20、：n=3, r=2AB, BA, CA,AC, BC, CB,AA, BB, CC。若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有 C(n,r)r!=P(n,r),如:n=3,r=2,P(n,r)=3!/1!=6, AB,BA,AC,CA,BC,CBC(n,r)=3!/(1!2!)=3, AB, AC, BC)!( !rnrnrnC(n,r)=P(n,r)/r!=nr/r!=（1）从n个中取r个的无重组合无重组合 )!( !),(rnrnrnrnC（2）从n个中取r个的可重组合(以后介绍)。例：n=3, r

21、=2AB, BC, CA,AA, BB, CC例：n=3, r=2AB, BC, CA, 要点：相同元素的排列 例：求3个1，2个2的全排列数，n=5, 得到 11122, 11212, 12112, 21112, 11221, 12121, 21121, 12211, 21211, 22111 10! 2! 3! 5)2 , 3; 5(P 求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!tttrrrnrrrnrrrnP212121!),;(解：解

22、：RRYY, RYRY, RYYR, YYRR, YRYR, YRRY。例例1-201-20 红，黄二色的旗各两面，4面排成一排，有多少种方案？6) ! 2(! 42YYRR, 代表代表Y1 Y2 R1 R2, Y1 Y2 R2 R1, Y2 Y1 R1 R2，Y2 Y1 R2 R1。例例1-131-13 5面不同的旗帜，面不同的旗帜，20盆不同的花，两盆不同的花，两端是不同的旗帜，中间放端是不同的旗帜，中间放3盆不同的花。有多盆不同的花。有多少方案？少方案？解：解：5面旗取面旗取2面排列面排列 P(5,2)=54=20，20盆花取盆花取3盆排列盆排列 P(20,3)=201918=6840，

23、由乘法法则，由乘法法则， 206840136800。例例1-121-12 男生7名，女生3名，排成一列，头和尾为男生，女生不相邻。有多少方案？解解1 男生全排列（男生全排列（7！种），！种）， 男男男男男男男男男男男男男男女生插入女生插入6个间隔，依次有个间隔，依次有6，5，4个选择个选择 （相当于（相当于6个间隔取个间隔取3个，排列）个，排列）456! 7) 3 , 6(! 7P456! 7! 3) 3 , 4()4 , 7(! 3CP总计总计解解2 女生全排列，女生全排列，3！种，！种， 7男生取男生取4人插入人插入4个位置，个位置，P(7,4)种。种。 男男女男女男女男女男女男女男 4个

24、个位置，可重取位置，可重取3个，个，C(4,3)种。种。 3个可重位置排序，个可重位置排序，3！种。！种。由由1-6节节) ! 3 ! 3/(! 6) 3 , 134() 3 , 4( CC解解3 注意注意1：男男女女男男女女男男女女男男 4个个位置，可重取位置，可重取3 3个，则多个男相邻。个，则多个男相邻。设无重取设无重取3 3个，则个，则至多至多2 2个男相邻。个男相邻。 注意注意2：只能考虑只能考虑4个个位置。位置。设设5个个位置位置 男男女男女男女男女男女男女男则由则由 男男11女女, , 得到得到 男男1 1男男2 2女女,且由且由 男男22女女, , 得到得到 男男1 1男男2

25、2女女, , 重复重复(2)当当 取取3， 有有5种选择，种选择， 从其余从其余8个数字取个数字取2个排列。个排列。12nn3n0n728280448280)2 , 8(51P例例1-15 2000到5000间的偶数中，由不同数字组成的4位数的数目。0123nnnn3n0n解解1 设该设该4位数为位数为取取0,2,4,6,8； 取取2,3,4（为何分组）（为何分组）3n0n12nn448)2 , 8(42P 从其余从其余8个数字取个数字取2个排列。个排列。 (1)当当 取取2,4, 有有4种选择，种选择，12nn例例1-15 (为了显示二解之差，修改了数据为了显示二解之差，修改了数据) (注意

26、:为何后考虑为何后考虑 )0123nnnn3n0n12nn3n3n0n0n12nn224)2 , 8(22P728504224504)2 , 8(33P解解2 设该设该4位数为位数为 取取0,2,4,6,8 取取2,3,4（为何分组）（为何分组） (1)当当 取取2,4, 有有2种选择，种选择， 从其余从其余8个数字取个数字取2个排列。个排列。 (2)当当 取取0,6,8， 有有3种选择，种选择， 从其余从其余8个数字取个数字取2个排列。个排列。例例1-15 解解3 取取0,2,4,6,8 取取2,3,4(1)当当 取取2,4, 取取2,3,4(有有2种种)， 有有1种种, 有有7种种. 共共

27、227=28(2)当当 取取2,4, 取非取非2,3,4(有有7种种)， 有有2种种, 有有7种种. 共共2727=196(3)当当 取取0,6,8, 取取2,3,4(有有3种种)， 有有2种种, 有有7种种. 共共3327=126(4)当当 取取0,6,8, 取非取非2,3,4(有有6种种)， 有有3种种, 有有7种种. 共共3637=3783n0n3n3n0n0n728378126196282n1n0n0n1n1n1n3n3n2n2n2n例例1-16 5个女生和7个男生选出5人，不允许男生甲和女生乙同时选中。有多少方案？1201238910) 3 ,10(7921234589101112)

28、5 ,12(CC解解1 12人取5人的组合 甲和乙同时参加的组合 合计：792120672 25212345678910)5 ,10(4201234789102)4 ,10(2CC例例1-16 解解2 甲或乙之一参加的组合 甲和乙同时不参加的组合 合计：420252672例例1-18 英文Wellcome中， 3个母音e,o,e中e重复， 5个子音w,l,c,m中l重复。 8个字母全排列，3个母音不相邻， 多少排列？00000解：解：5个子音排列，5!/2=60。 3个母音插入6个位置，654/260例例1-19 从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？14851

29、001000000485100100) 3 ,100(33C解：解： 将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)=3,6,9,300. 要满足条件，有四种解法：（为何分类）（为何分类） 1)3个数同属于A; 2)3个数同属于B 3)3个数同属于C; 4)A,B,C各取一数.故共有例例1-20 用11, 12, 13的方块铺设17的模块，有多少方案？解：用7块11，1种 用5块11，1块12，6!/5!=6 种 用4块11，1块13，5!/4!=5 种 用3块11

30、，2块22，5!/(3!2!)=10 种 用2块11，1块12，1块13，4!/2!=12 种 用1块11，3块12，4!/3!=4种 用1块11，2块13，3!/2!=3种 用2块12，1块13，3!/2!=3 种合计：165101243344种例例1-211-21 8人分4组，每组2人，有多少方案？解解1 某人选同组7个选择， 余6人之一选同组5个选择， 余4人之一选同组3个选择， 合计105357 1052484！解解2 8人全排列，8！个选择，按排列分组 1,2,3,4,5,6,7,8， 同组交换，重复度2222， 4组排列，重复度4！， 合计105)2(4! 8! 41! 2! 2!

31、 4! 2! 4! 6! 2! 6! 84！解解3 8人选第一组，C(8,2)个选择， 余6人选第二组，C(6,2)个选择， 余4人选第三组，C(4,2)个选择， 4组排列，重复度4！， 合计例例1-22 某车站有某车站有6个入口处，每个入口处每次个入口处，每个入口处每次只能进一人，一组只能进一人，一组9个人进站的方案有多少？个人进站的方案有多少？解：解：一进站方案表示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给n-1个“1”n个门只用n-1个门框。 任意进站方案可表示成上面14个元素的一个排列。abc 1 1 de 1 f 1 g

32、1 hi注意：注意：门框确定门的排序，门框不必排序门框确定门的排序，门框不必排序解解1 1 标号可产生5!个14个元的全排列。故若设x为所求方案，则 x5!=14! x=14!/5!=726485760解解2 2 在14个元的排列中先确定“1”的位置，有C(14,5)种选择，再确定人的位置，有9！种选择。故C(14,5)9!即所求。解解3 3 把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。以此类推，9号有14种选择。故所求方

33、案数为67891011121314 解解4 4 9个人全排列有9！种。10个空位（两端和8个间隔）插入5个门框，每个空位可以有多个门框。这是从10个不同元中，可重复取5个的组合， （1.6节给出公式）总计： ! 5!14)5 ,10(! 9! 9! 5!14)5 , 1510()5 ,10()5 ,10(CCCC如2个人，3个门。34个方案。12MM, 21MM, 1M2M, 2M1M, M12M, M21M, M1M2, M2M1, 1MM2, 2MM1, MM12, MM21,1.1.4 4 圆周排列圆周排列 要点：要点：从n个中取r个的圆排列的排列数为 P(n,r)/r , 2rn 以4

34、个元素为例：下列4个为同一个圆排列 12 4 3 1234 12 4 3 2341 12 4 3 3412 12 4 3 4123如：P(4,4)/4=61234, 1243, 1324, 1342, 1423, 1432例例1-241-24 5 5个男生和个男生和3 3个女生围圆桌坐，个女生围圆桌坐，(1)A,B(1)A,B不相邻有多少方案？不相邻有多少方案？(2)3(2)3女生不相邻，有多少？女生不相邻，有多少？解：解：(1)B(1)B以外以外7 7人圆周排列人圆周排列6 6！种，！种，B B插入插入5 5个间隔个间隔( (除去除去A A两边两边2 2个间隔个间隔) )。总计。总计6 6！

35、5 5个方案。个方案。(2)5(2)5男生圆排列男生圆排列4 4！种，！种，3 3女生依次插入女生依次插入5 5个间个间隔。总计隔。总计4 4！5 54 43 3个方案。个方案。 例例1-251-25 n n对夫妻围一圆桌而坐，每对夫妻相对夫妻围一圆桌而坐，每对夫妻相邻而坐，有多少方案？邻而坐，有多少方案？解： .)()()()(162)!13(2)!1(32)!1(3311221122332233112211331133223322113311221122332233112211331133223322113fmmffmmffmfmfmfmmffmmffmmffmfmfmfmmffmfmfm

36、fmfmfmfmfmfmfmfmfmfmfmfmfmfmfmnnnnn时， 要点：要点：从n个中取r个的项链排列项链排列的排列数为 P(n,r)/2r, 3rn 项链排列项链排列就是说排列的方法和项链一样,在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。 例例 下面两种方式实际上表示的都是3个元素的同一种项链排列。 P(3,3)/(23)=1 123, 231, 312, 321, 213, 132 1 1 2 3 3 21.5 全排列的生成算法全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。介绍全排列生成的主要算

37、法：(A) 序数法(B) 字典序法(C) 邻位对换法1.5.1序数法, 110, 200, 32023013! 11! 20! 32201! 11! 22! 331! 499990105101100108801510910910910911015092120202110012121212112123012301234012301234aaa如新进制如十进制如二进制1! 41! 3! 331! 2! 22! 3311! 11! 22! 33! 11! 22! 33! 11! 22! 331! 4证明：新进制由序数2，0，1 ，求十进制m13 23！02！11！13) 1 , 0 , 2(),(2

38、, 0424340,! 3! 32363231,! 2! 2! 2! 36213212),(! 1! 2! 3131123323123123123aaaannaannaaannaaaaaan序数余数余数余数序数由十进制m13，求序数2，0，1 1, 2 , 1,0! 1! 2)!2()!1(1221niiaaananaminn其中序数 n!个，对应n元的n!个序列。规则(序列序数)：序列(p)= 是(p)中数字i+1后面比i+1小的数的个数 如 (p)=(4213) 对应 =(301) n4 (p)=(3412) 对应 =(220)规则(序数序列)：如其中的序列(220)所对应的排列: 先由

39、=2决定4的位置 x4xx 再由 =2决定3的位置 34xx 再由 =0决定2的位置 34x2 则 3412),(21nppp),(121aaan),(123aaa),(123aaa1aia3a2a 对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。1.5.2 字典序法 例例 字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。一个全排列可看做一个字符串，字符串可有前缀前缀、后缀后缀。 对给定的字符集中的字符规定了一个先先后关系后关系，在此基础上规定两个全排列的先后是从左到右逐个

40、比较左到右逐个比较对应的字符的先后。3544 3135生成给定全排列的下一个排列：所谓一个的下一个一个的下一个就是这一个这一个与下一个下一个之间没有其他没有其他的的。这就要求这一个与下一个有尽可能长长的共同前缀共同前缀，也即变化限制在尽可能短短的后缀后缀上。例例 求83964 47521的下一个排列。找出比右边数字小的第一个数4在后缀7521中找出比4大的最小数 54，5 对换成为 839657421将此后缀7421翻转成为 1247接上前缀83965得到839651247即839647521的下一个。1.5.3 邻位对换法 递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易

41、。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向单向的，从右向左，而邻位对换法的换位是双向双向的。活动数是箭头所指相邻数比自己小的数。对换规则：活动数中最大的数m，交换箭头所指相邻数。同时，比m大的数，改变方向。42312431234123143214324134214321mmmmmmmm1.6 允许重复的组合与不相邻的组合1.6.1 允许重复的组合从n个不同元素中取r个可重复的元素的可重组合数目 C(n,r) = C( n+r-1,r)如n=3，r=2。C( 3+2-1,2)= C( 4,2)=6 AA, BB, CC, AB,

42、AC, BC相当于r个相同的球放入n个互异的盒子 200，020，002，110，101，011 r个相同的球 / 001001100 / /n-1个相同的盒壁),(rnC 的计数问题相当于r相同的球放入n个互异的盒子，每盒球的数目不同的方案的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。) 1,(), 1(),(), 1()!1( !)!1(rnCrnCrnCrrnCnrrn所求计数为不含“” 至少含一个“”), 1(),(), 1(),(), 1(),(), 1(1,.,111, 2 , 1, 1:1),(,.,11212121212121rrnCrnCrrnCr

43、nCfrrnCrnCfrrnCbbbrrnrnbbbriiabbbbaaafnaaarnCaaarnrriirrrr则是单射，是单射，个中无重取从则满足使得是无重组合，构造函数个中可重取从证：234,134,124,123,4222,122,112,111,44) 1 , 4(), 1(134,314,.,1144311422, 312, 101134122:22211122,32 , 1321321为个为个个中无重取从则满足其中：是无重组合，构造函数个中可重取从如：bbbaaaCrrnCrnrnfnrn4)(zyx例1-29 有多少项？yzxzxyzyzxyxyxzxzyyzxyzzxyxz

44、yxzyxC3333332222222224444444444121212666)(15) ! 2! 4/(! 6)4 , 134(解：解：从3个元素可重复的取4个的组合数目。从n个不同元素中取r个的可重排列数目 aa,bb,cc,ab,ac,bc,ba,ca,cb9)2 , 3(, 2, 3),(6)2 , 3(, 2, 3)!/(!),(PrnnrnPPrnrnnrnPr如如总结：总结：从n个不同元素中取r个不重排列数目 ab,ac,bc,ba,ca,cb6)2 , 4()2 , 3(, 2, 3), 1(),(3)2 , 3(, 2, 3)!( !/!),(CCrnrrnCrnCCrnr

45、nrnrnC如如总结：从n个不同元素中取r个不重组合数目 ab,ac,bc从n个不同元素中取r个的可重组合数目 aa,bb,cc,ab,ac,bc1.6.2 不相邻的组合 从n个不同元素中取r个不相邻的元素的不相邻组合数目C( n-r+1,r) 如n=5,r=2. C( 5-2+1,2)= C( 4,2)=6 AC, AD, AE, BD, BE, CE), 1(111, 1,1212122112121rrnCbbbrnbbbrabababnaaaaaarrrrrr则满足令属于不相邻的组合设证明：)3 , 3()3 , 135(1353332132521315312)3 , 7()3 , 13

46、5(13573765432172561515511354321CCCC）个组合（取，对应从，改为，）不相邻：（）个组合（取，对应从，改为，）可重合：（个组合，取，从说明：1.6.3 线性方程的整数解的个数问题已知线性方程 和 都是整数 ， 求此方程的非负整数解的个数。nbxxxn,21b1n证：方程的每个非负整数解 对应一个将b个无区别的球，放进n个有标志的盒子 的情况，允许一盒多于一个球的，故非负整数解的数目等价于1到n 正整数取b个作允许重复的组合，其组合数为),(21n),(21nxxxbbn1。bn21ni, 2 , 1,2211nnxxx使等价于 盒有 个球， 。ixi321nxxx

47、10353133例如，0120030212011113000302101201021.6.4 组合的生成 设1,2,3,4,5,6中取3个的组合，20个， 按照字典序排列。 123，124，125，126，134， 135，136，145，146，156， 234，235，236，245，246， 256，345，346，356，456。 第1位1到4，第2位2到5，第3位3到6。 如256，345，346，356，456。 256中，5和6到最大。 2加1为3，后接4，5等。为345。 如156，234，235，236，245， 156中，5和6到最大。 1加1为2，后接3，4等。为234。

48、 236中，6到最大。 3加1为4，后接5等。为245。1.7 组合意义的解释例例1-30 简单格路问题从 (0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？y (m,n).0 . . . xmnmnm),()0 , 0( 无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。 则(0,0)(m,n)的每一条路径可表示为m 个x与n个y的一个相同元素排列。将每一个相同元素排列的x与y分别编号，可得m!n!个m+n元的无重全排列。,!)!(1232121321yyxxxyyxxxnmnmmnm

49、(c,d)(a,b)acbdacdcbadcbabdacmnmnmnmnmnmPnmnmnmnmPnmnmP)()(),)(,(),(),(,!)!(),;()!(!),;(),;(的简单格路数为到则由设故则设所求方案数为 xxxyy, xxyxy, xyxxy, yxxxy, xxyyx, xyxyx, yxxyx, xyyxx, yxyxx, yyxxx 10! 2! 3)!23()2 , 3; 23(),;(, 2, 3PnmnmPnm则设 例例1-44 在上例的基础上若设mn，求(0,1)点到(m,n)点不接触对角线x=y(xy)的格路的数目 (“接触”包括“穿过”) 从(0,1)点到

50、(m,n)点的格路，有的接触x=y，有的不接触。 对每一条接触x=y的格路，做(0,1)点到第一个接触点部分关于x=y的对称格路，这样得到一条从(1,0)到(m,n)的格路。 容易看出从(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). . .mnmnmnmnmnmmnnmnmnmmnmmnm111)!1( !)!1()!1( !)!1()!1( !)!1(111故所求格路数为(0,1)到(m,n)路径数减去(1,0)到(m,n)路径数。2

51、2431213232111mnmnm如m=2,n=3. 方案数2。yyyxx, yyxyx 例 若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得xy=1， (0,0)关于xy=1的对称点为(1,-1). 所求格路数为(0,0)到(m,n)路径数减去(1,-1)到(m,n)路径数如m=2,n=3. 方案数5。yyyxx, yyxyx, yxyxy, yxyyx, yyxxymnmnmnmnnmnmnmmnmmnm11)!1()!1()!(!)!(1 组合意义或组合证明，含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。等式1.例1-31 组合意义：从1,n去掉一个r子集，剩下一

52、个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。故又证：),()!(!),(),(),(),(),(rnnCrnrnrnCrnnCrnCrnnCrnC 等式2.例1-32 组合意义： ) 1, 1(), 1(),(), 1(1) 1, 1(1,1, 1 ) 1, 1(), 1(),(112121rnCrnCrnCrnCarnCanaaaaaanrnCrnCrnCrr共有种方案有种方案有对取法分类：设，取从 另一个组合意义 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) 另可证),(

53、)!(!)()!(!)!1()!()!1()!1()!1(!)!1() 1, 1(), 1(rnCrnrnrrnrnrnrnrnrnrnrnCrnC 杨辉三角除了(0,0)点，都满足此递推式 C(3,2)=3, C(2,2)+C(2,1)=1+2=3 C(4,1)=4, C(3,1)+C(3,0)=3+1=4 等式3 例1-33rrnrrnnn1110rrnnnrrnrrnrrnrrnrrnrrn110112111证：证：可从例1-32推论，也可做一下组合证明 组合意义： 从1,n+r+1取r个的组合是右边。 左边最后一项不含1 ，n+r个取r 左边最后第二项含1不含2, n+r-1个取r-1 左边最后第三项含1,2不含3, n+r-2个取r-2 , 左边第一项含1,2,r, 则不取r+1以后rrnrrnnn1110 另组合意义:从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上) 故