湖南大学《离散数学》课件-第1章组合数学

组合数学杨圣洪源自刘晓华1

湖南大学离散数学引言组合数学包括组合分析、图论、组合算法、组合设计、算法复杂性分析等部分内容。本课程内容实际上属于组合分析范围。组合分析研究的主要内容是计数和枚举，即算出某问题所指对象有多少个，必要时将其列举出来。算法研究是计算机科学的一个重要领域。对于一个具体算法，有时为了评估其优劣，往往需要对其计算量和存储单元数进行估计，这就是算法的时间复杂性和空间复杂性分析，它属于组合算法的研究内容。组合分析是组合算法的基础。1,2,3,4,5,6,7,8,9,102第一章排列与组合§1基本计数法则：加法法则与乘法法则⒈加法法则例1

某人从长沙去武汉，可乘火车、飞机或长途汽车，问此人从长沙去武汉可有多少种方法？长

沙武汉

乘飞机乘火车乘长途汽车

显然，此人共有1＋1＋1＝3种不同方法。例2

上例中，若一天内长沙到武汉有时间不同的火车5次，飞机3班，长途汽车2次，问此人从长沙到武汉可有多少种走法？显然，此人共有5＋3＋2＝10种不同走法。1,2,3,4,5,6,7,8,9,103加法法则如果完成一件事情有k类方法，第一类方法中有m1种不同做法，第二类方法中有m2种不同做法，…,第k类方法中有mk种不同做法，则完成这件事共有m1+m2+…+mk种不同的方法。始点终点m1种m2种mk种……….1,2,3,4,5,6,7,8,9,104⒉乘法法则例3某人从长沙经武汉到上海。从长沙到武汉可乘火车、飞机或长途汽车，从武汉到上海可乘船、火车、飞机或长途汽车，问此人从长沙到上海可有多少种走法？

长沙武汉上海乘船乘火车乘飞机乘长途汽车乘火车乘飞机乘长途汽车此人共有3×4＝12种不同方法(见下页分析）。1,2,3,4,5,6,7,8,9,105长沙武汉武汉武汉上海上海上海上海上海上海上海上海上海上海上海上海乘火车乘飞机乘长途汽车乘飞机乘火车乘船乘长途汽车乘长途汽车乘长途汽车乘飞机乘火车乘火车乘飞机乘船乘船1,2,3,4,5,6,7,8,9,106乘法法则如果完成一件事需经n个阶段，其中第一个阶段有m1种不同的方法，第二个阶段有m2种不同的方法，…,第n个阶段有mn种不同的方法，那么完成此事共有m1×m2×…×mn

种不同方法。始点终点(共m1种)(共mn种)…….…….第1阶段…….第n阶段…….…….ABC33第一个字符第二个字符5种3种例1.2（p.1)例1.1（p.1)填一个字符为一阶段，故共有

5×3＝15种方式。A到C共有3×3＝9条不同的道路。1,2,3,4,5,6,7,8,9,107例1.3（p.2)填一位数字为一阶段，则不含1的数共有

9×9×9×9＝6561种，但0000不是正数，故不含1的正数共有6561－1＝6560种，从而含1的正数个数为9999－6560＝3439。千位个位十位百位99991,2,3,4,5,6,7,8,9,1084．应用举例例1.4

求长度为n的二元码的个数。填入一码为一个阶段，共n阶段。每阶段有2种填法，故共有2n

个二元码。例1.5

脱氧核糖核酸DNA

填入1位为1阶段，共2.1×1010

阶段，每阶段有4种填法，故共有个DNA。

例1.6

求n个自变量的布尔函数的个数。

n个自变量共有2n

组不同的取值，每组自变量的取值对应有一个函数值（0或1）。定义一个函数，就是对每一组自变量的取值定义一个对应的函数值。因此对一组自变量的取值定义对应的函数值为一阶段，共2n

阶段，每阶段有2种选择，故布尔函数的个数为。

例1.7例1.81,2,3,4,5,6,7,8,9,1094．应用举例例1.6Bn=73*112*134,求除尽n的整数个数

m=7a*11b*13c,则a=0,1,2,3，b=0,1,2，c=0,1,2,3,4能除尽n的整数个数=4*3*5=60。

例1.7

由{a,b,c,d,e}的字符构成长为6的字符串，(1)该串的第1个与第6个必须{b,c,d}中字符,(2)其中必须有a,e，但不相邻,可重复出现;(3){b,c,d}中字符不能二个相同的相邻a,e位于(2,4)

a,e位于(2,5)

a,e位于(3,5)

(2,4)时：3*2*3*2*3*2=27*8=(2,5)时：3*2*3*2*2*3=27*8=(3,5)时：3*2*2*3*2*3=27*8=共有：27*8+27*8+27*8=81*8=6481,2,3,4,5,6,7,8,9,10101235641234651234651234654．应用举例例1.8日文5本，英文7本，中文10本(1)从中取2本不同语言的书：

5*(7+10)+7*(5+10)+10*(5+7)=310

没有前后秩序之分310/2=155(a)日英各一本：5*7=35英日不考虑(b)日中各一本：5*10=50中日不考虑(c)英中各一本：7*10=70中英不考虑35+50+70=155(2)二本是相同文字：(a)同为日文：5*4/2=10(b)同为英文：7*6/2=21(c)同为中文：10*9/2=4510+21+45=76(3)任取2本不限文字：22*21/2=231=76+155

1,2,3,4,5,6,7,8,9,101112例1.9由

26个字母组成长为5的字符串：(1){a,e,i,o,u}不允许连续2个元音

(2)不允许连续3个辅音(3)不允许连续2个相同的辅音α表示元音β表示辅音，构造出其模式

αββαβ:6*20*19*6*20=62*202*19=273600

αβαβα:6*20*6*20*6=86400αβαββ:6*20*6*20*19=273600

ββαββ:20*19*6*20*19=866400

ββαβα:20*19*6*20*6=273600βαββα:20*6*20*19*6=273600βαβαβ:20*6*20*6*20=288000合计:23352001,2,3,4,5,6,7,8,9,101212354§2一一对应1.定义设A,B是两个集合。若存在A到B的一个双射

:A→B，则说集合A与B是一一对应的。2.当有限集合A与B是一一对应的时候，A与B的元素个数是一样多的。因此，求A的元素个数可以转化为求B的元素个数。1,2,3,4,5,6,7,8,9,1013往水平方向走一步记为x，往垂直方向走一步记为y，第i位置表示第i步(i=1,2,…,m+n)，则下列排列就表示从(0,0)到(m,n)的一条路径：

xxyxyyx…xy(m个x，n个y)(＊)这样,形如上述的一个排列就对应(0,0)到(m,n)的一条路径，反过来(0,0)到(m,n)的一条路径也可对应形如(＊)的一个排列,即路径集合与形如(＊)的排列集合形成一一对应关系。确定了x位置后，剩下的是y步数为：C(m+n,m)类比(m,n)(0,0)yx3.示例例1(p.34)

路径问题1,2,3,4,5,6,7,8,9,1014例3(p.6)100名选手参加单打淘汰赛，求产生冠军时比赛的场数。(逆向思维)

一场比赛淘汰一名选手，比赛集合与淘汰选手集合是一一对应的。100名选手只剩冠军时淘汰了99名选手，故比赛场数为99场。例1.10(p.7)碳氢氧化物CnH2n+2

对应一棵树（有3n+2个顶点，其中2n+2个树叶，

n个内点,内点度数为4，叶子均为1度数和=4n+2n+2=6n+2,边有3n+1,这种形式的树多少棵？）

1,2,3,4,5,6,7,8,9,1015Cayley定理

过n个有标号的顶点的树的数目为nn-2.n个城市用一条边连起来，共nn-2.=42=16设顶点标号为1,2,…,n，建立树与序列的一一对应。

(i)设T为任意一棵树，去标号最小树叶a1及边(a1,b1)(b1为内点)，记下b1

；再在剩下树中去标号最小树叶a2及边(a2,b2)记下b2

；……反复进行上述步骤，直到只剩一条边为止。树T就对应一个数字序列b1b2...

bn-2.例如，树(2,3)3

(3,1)1(4,5)5

(6,5)5

(7,1)1树T-->3155123176541,2,3,4,5,6,7,8,9,1016317654176541765对应序列3，1，5，5，1(内点序列)(ii)反过来，任意给定一个数列b1b2...

bn-2

（每个数为不超过n的自然数），可以找到一棵树与之对应：考虑序列

b1b2...

bn-2(1)1，2，3，…，n(2)在序列(2)中找出不在(1)中的最小数a1

，建立一边(a1,b1)，并去掉(1)中的b1和下列(2)中的a1；再在剩下的序列(2)中找出不在剩下的序列(1)最小数a2

，建立一边(a2,b2)，并分别去掉剩下的两序列中的b2和a2；……；反复上述步骤，当(2)只剩两顶点ak,bk时，连接ak,bk即可。例如，序列3，1，5，5，1对应一棵1,2,..,n中每个数出现b1b2...

bn-2

n*n*n...*n=nn-2.

碳氢化合物n=3m+2顶点,共有n(n-2)/(2n+2)/n?23176541,2,3,4,5,6,7,8,9,1017§3排列与组合一排列1.定义从n个不同元素中取出r个，按照一定顺序排成一列，称为从n中取r个的一个排列。例A

从A，B，C中取2个的所有不同排列为：

AB，BA，AC，CA，BC，CB.nn-r+1n-2n-1……..2.排列数从n个不同元素中取r个的全部不同排列的个数记为.=n(n-1)…(n-r+1)=n!/(n-r)!以上计数问题可看成是从n个不同的球中取r个放到r个已排好顺序的盒子里去的问题(因为两问题是一一对应的):1,2,3,4,5,6,7,8,9,10183.n的全排列从n个不同元素中取n个的排列数称为n的全排列数，其值为n!.花星状物花花星状物

52019184故共有

5×4×20×19×18=136800种不同图案。

例1.15A单位的人共有7!种排列。A单位的人排列固定后，再排列B单位的人。设A单位的排列为A1A2A3A4A5A6A7，则B单位的人只能排在下面标*号的位置：A1*A2*A3*A4*A5*A6*A7，故B单位的第一人有6种选择，第二人有5种选择，第三人有4种选择，因此不同的排列方案共有

7!×6×5×4=604800种。例1.135面不同颜色旗,20种不同的花,中间是花二边是旗。1,2,3,4,5,6,7,8,9,1019

例.

7名男3名女。(1)首尾为男，女不相邻:男先排好7!,女选位置6*5*4(2)女相邻排在首尾二端：3!(3女先排好)*2*7!(3)女相邻位置不做要求：3!*7!*81,2,3,4,5,6,7,8,9,102012345671234567

例1.16(p.13)设所求数为abcde,则

a∈{2,3,4,5,6},e∈{0,2,4,6,8}.

由于每位数各不相同，故a为偶数时有

3××4=4032个，a为奇数时有2××5=3360个，因此总个数为

4032+3360=7392个。

这样的数共有

个。设S1，S2，S3，S4分别为这64个数的个位、十位、百位和千位的数值之和，则S1=(1+3+5+7)+3×(1+3+5+7)+3×2×(1+3+5+7)+3×2×1(1+3+5+7)=16×(1+3+5+7)=256，S2=3×(1+3+5+7)+3×2×(1+3+5+7)+3×2×1(1+3+5+7)=15×(1+3+5+7)=240，S3=3×2×(1+3+5+7)+3×2×1(1+3+5+7)=12×(1+3+5+7)=192，S4=3×2×1(1+3+5+7)=96，从而

S=S1+10×S2+100×S3+1000×S4

=117856.例1.17(p.13)求由{1，3，5，7}组成的无重复数字的整数（即同一整数内任意两位都不相同）的和。1,2,3,4,5,6,7,8,9,1021

例

求2000--7000之间的偶数，由不同的数字组成的4位数的个数。设4位数：abcda是{2,3,4,5,6},d为{0,2,4,6,8}冲突在哪？(1):a取偶数2,4,6时,d从剩下4个中选1个,bc从剩下8位取2位：3*4*P(8,2)=12*8*7=672(2):首位a不取{2,4,6}而取{3,5}时，个位可取d{0,2,4,6,8},bc只能剩下8位中取2位：

2*5*P(8,2)=2*5*8*7=560或者：a=2d

in{0,4,6,8}1*4*P(8,2)a=4din{0,2,6,8}1*4*P(8,2)a=6din{0,2,4,8}1*4*P(8,2)a=3din{0,2,4,6,8}1*5*P(8,2)a=5din{0,2,4,6,8}1*5*P(8,2)1,2,3,4,5,6,7,8,9,1022abcd

例

求1357不重复出现的数字组成的整数的和。4位数：abcdP(4,4)=4!=2413571375153715731753173563157317535713517371537516513751735371531757315713671357153735173157531751363位数：abcP(4,3)=4*3*2=2413513715315717517363153173573513713756513517537531573571671371573573175375162位数：abP(4,2)=4*3=12131517313537515357717375.1位数：aP(4)=413571,2,3,4,5,6,7,8,9,1023abcd

例

求1357不重复出现的数字组成的整数的和。1位数：aP(4)=41357S1各数和=162位数：abP(4,2)=4*3=12131517313537515357717375.个位数S1：只能是1357,累计3组：3*16=483位数：abcP(4,3)=4*3*2=241351371531571751736315317357351371375651351753753157357167137157357317537516个位数S1：只能是1357,累计6组：6*16=96位数：abcdP(4,4)=4!=241357137515371573175317356315731753571351737153751651375173537153175731571367135715373517315753175136个位数S1：只能是1357,累计6组：6*16=9696+96+48+16=256

十位：（48+96+96）*10百位：（96+96）*100千位：96*100001,2,3,4,5,6,7,8,9,1024abcd

例

5女7同组成5人小组，不准某男及某女参加这是组合问题

(1)不做限制C(12,5)=12*11*10*9*8/5!==12*11*10*9*8/(5*4*3*2) =12*11*3*2=792(2)必须参加，只要选3个就可以C(10,3)=10*9*8/3!=10*9*8/(3*2)=10*3*4=120(3)不准参加的：792-120=672

1,2,3,4,5,6,7,8,9,1025

例

从1到300间选取3个数，其和正好被3除尽

。A=除3余数为0={3,6,9,..,300}=100个B=除3余数为1={1,4,7,..,298}=100个C=除3余数为2={2,5,8,..,299}=100个

m+n+i被3除尽，(1)m,n,i的余数相同。同为A

,C(100,3)=100*99*98/6=100*33*49同为B

,C(100,3)=100*99*98/6=100*33*49同为C,C(100,3)=100*99*98/6=100*33*49(2)m,n,i的一个属于A,一个属于B,一个属于C

100*100*100=1000000共有：3*100*33*49+1003=1485100

1,2,3,4,5,6,7,8,9,1026

例

红、黄、蓝、绿四色旗各4面，共16面排成列，问有多少种方案。有重复元素的排列问题

P(16,16)=16!，当为16种不同色时但4面红旗的不同排列4!视同于一种方案16!/(4!*4!*4!*4!)

1,2,3,4,5,6,7,8,9,1027

例

1*1、1*2、1*3铺设1*7的地面，有多少种方案。有重复元素的排列问题

(1)7块1*1,一种排列方式:1(2)5块1*1,1块1*2,要6块,这二种块可交互出现6!/5!=6(3)4块1*1,1块1*3,要5块,这二种块可交互出现5!/4!=5(4)3块1*1,2块1*2,要5块,这二种块可交互出现5!/(3!*2!)=5*4*3*2/(3*2*2)=10(5)2块1*1,1块1*2,1块1*3,要4块,这三种可交互出现4!/(2!)=4*3*2/2=12(6)1块1*1,3块1*2,要4块,这二种可交互出现4!/(3!)=4*3*2/3!=4(7)1块1*1,2块1*3,要3块,这二种可交互出现3!/(2!)=3(8)2块1*2,1块1*3,要3块,这二种可交互出现2!/(2!)=3共要？

1,2,3,4,5,6,7,8,9,1028

例

有A1,A2,...,A8八位,分成4组每组2个，有多少种？第1组选:可从8人中选2个,C(8,2)=8*7/2=28第2组选：剩下6个,6人任选2个一组C(6,2)=6*5/2=15第3组选：还剩下4个,4人任选2个一组C(4,2)=4*3/2=6第4组选：最后剩下2人就是一组1种分成4个环节，用乘法28*15*6=2520但是这个分组是人为的，其实谁是第1组不重要，因此最后结果：C(8,2)*C(6,2)*C(4,2)/4!=28*15*6/(4*3*2)=7*15=1058个人的全排列P(8,8)=8!

让12名第1组34名第2组56名第3组78名第4组，组内2个没有先后之分，所以8!/2!/2!/2!/2!

第1组、第2组、第3组、第4组也是人为，没有先后8!/2!/2!/2!/2!/4!=8*7*6*5*4*3*2/(2*2*2*2*4*3*2)=105

2n成员组成n组呢？

1,2,3,4,5,6,7,8,9,1029

例

有9个有标志的棋子，放在6*9的棋盘上,模拟9人从6个出口离开，方案？每行第1格是出口

棋子1可6选1，方案6种

棋子2可与棋1不同行,同行有

在棋1之前或棋1之后,共7种

棋子3可4+2+2=8

。。。棋子8可6+8=14

共有6*7*8*9...*14=下次让9棋子排一列a1a2a3a4a5a6a7a8a9，插入5个*号a1a2*a3*a4*a5a6*a7*a8a9,12同口、56同口、89同口a1a2*a3*a4*a5a6**a7a8a9

第45口只用一个P(14,14)/P(5,5)=14!/5!5个*可以任排列都是一种方案

1,2,3,4,5,6,7,8,9,1030654321

例

求5位数

abcde中,至少出现一个6，被3整除个数？

5位数从10000-99999共有99999-10000+1=90000

能被3整除的10002-999999共有90000/3=3000030000个,a+b+c+d+e=3的倍数至少1个6：6出现的次数>=1，对立面：6出现次数<1即为0，6不出现！每位不出现能被3整除，则是各位数字和是3的倍数

6不出现只能是0,1,2,3,4,5,7,8,9a:1,2,3,4,5,7,8,9:8种可能

b:0,1,2,3,4,5,7,8,9:9种可能

c:0,1,2,3,4,5,7,8,9:9种可能

d:0,1,2,3,4,5,7,8,9:9种可能

e:0,1,2,3,4,5,7,8,9:

若a+b+c+d=3k则e=0,3,9

若a+b+c+d=3k+1则e=2,5,8

若a+b+c+d=3k+2则e=1,4,7

不管前面情况如何,e只有3种选择

8*9*9*9*3不出现6，至少1个6=90000-17496

1,2,3,4,5,6,7,8,9,1031二

圆排列排列在一个圆周上的排列称为是一个圆排列，从n个元素中取r个可作的全部圆排列的个数用表示。将长为r

的一个圆排列在其每一个间隔处分开，可得r个不同的直线排列。不难看出，长为r的一个圆排列恰好对应r个不同的排列。因此例1.19(p.15)8个珠子互不相同，因此(a)8个珠子作圆排列有

8!/8=7!种排法。(b)不允许蓝色珠子相邻时，先将红色珠子作圆排列，而后在其间隔(5个)中放入蓝色珠子：

5!/5×=1440.(c)蓝色珠子在一起时，先将蓝色珠子作排列，而后把排列固定后的蓝色珠子作为一个整体与红色珠子（看作6个）作圆排列：3!×(6!/6)=3!×5!.例1.20(p.16)(a)任意围圆桌而坐，方案数为=9！

(b)每对夫妇在一起，方案数为×25=768.1,2,3,4,5,6,7,8,9,1032二组合，1.定义从n个不同元素中取出r个（不考虑顺序），称为从n中取r个的一个组合。例B求从A，B，C，D中取3个的全部排列和全部组合。

ABC,ACB,BAC,BCA,CAB,CBA

A,B,C

ABD,ADB,BAD,BDA,DAB,DBA

A,B,DACD,ADC,CAD,CDA,DAC,DCA

A,C,D

BCD,BDC,CBD,CDB,DBC,DCB

B,C,D这里含字母相同的一组排列(每组6个排列)恰好对应一个组合。2.组合数C(n,r)

从n个不同元素中取r个的全部不同组合的个数记为C(n,r)，.

因为一个组合对应

r!个排列，故

C(n,r)=P(n,r)/r!=n!/[r!(n-r)!]1,2,3,4,5,6,7,8,9,1033三示例例1.21用3除，按余数为0、1、2将1～300分为3组：

C={3,6,9,…,300},A={1,4,7,…,298},B={2,5,8,…,299}.在1～300中任取三个数，则此三数所属集合有三种情形：

⒈三数属于A,B,C中的同一个集合；

⒉三数属于A,B,C中的其中两个集合；

⒊三数分别属于A,B,C。只有第一、三情形能被3除尽。故总方案数为

C(100,3)+C(100,3)+C(100,3)+1003=1485100.1,2,3,4,5,6,7,8,9,1034§6排列的生成算法1.字典序法算法

(i)从排列1234…n开始；

(ii)迭代.若已知排列p1p2p3…pn，按下列方法求下一个排列:①在p1p2p3…pn中，从右到左找满足下列关系的第一个不等式：pi＜pi+1.②让p1p2…pi-1不变，将{pi,…,pn}中比pi大的最小数放在位置i，将其余元素由小到大排在其后，这样得到的排列即为所求。多数情况下pi+1换到pi处，新pi之后的小到大排反复迭代，直到满足①中的不等式找不到时为止。从1234开始起，首个3<4，比3大的最小数4，12431243首个2<4比2大的最小数是3,13241324首个2<4比2大的最小数是4，13421342首个3<4比3大的最小数是4,14231,2,3,4,5,6,7,8,9,10351234首个小于式3<4，比3大的最小数4，12431243首个小于式2<4后面比2大的最小数是3,13241324首个小于式2<4后面比2大的最小数是4，13421342首个小于式3<4后面比3大的最小数是4,14231423首个小于式2<3后面比2大的最小数是3，14321432首个小于式1<4后面比1大的最小数是2,21342134首个小于式3<4后面比3大的最小数是421432143首个小于式1<4后面比1大的最小数是323142314首个小于式1<4后面比1大的最小数是423412341首个小于式3<4后面比3大的最小数是4，24132413首个小于式1<3后面比1大的最小数是324312431首个小于式2<4后面比2大的最小数是331243124首个小于式2<4后面比2大的最小数是431423142首个小于式1<4后面比1大的最小数是232141,2,3,4,5,6,7,8,9,10362.邻位互换法

如果已得n-1个元素的全部排列，则易得n个元素的全部排列，因为只需在前者的每个排列的每个间隔位置插入n即得。此方法简便直观，但其缺点是存储量过大。

123首个小于式2<3,后面大于2的最小数3132132首个小于式1<3,后面大于1的最小数1213213首个小于式1<3,后面大于1的最小数为3231231首个小于式2<3，后面大于2的最小数为3，312312首个小于式1<2，后面大于1的最小数为2，321321P(3,3)=3!=3*2*1=6

已经得到n-1个元素的全部排列，将4插入到位间隔1234123142312431234132413214321342132421342132413214321342134213241321432134312

431234123142312432143213421324132141,2,3,4,5,6,7,8,9,1037

邻位互换算法:从一个(n-1)的排列出发得到所有n元的排列(1)从排列1234…n开始，将每个数上置标志“←”。一个数所指方向的相邻数比其小时，称该数处于活动状态；

(2)迭代.若已知排列p1p2p3…pn，按下列方法求下一个排列:找出活动状态最大者m，m与箭头方向的邻数互换，比m大(不一定活跃者)者换向。

反复迭代，直到不存在处于活动状态的数为止。1<2<3<4<活中最大者4与邻换1<2<4<3<比4大者换方向1<2<4<3<活中最大者4与邻换1<4<2<3<比4大者换方向1<4<2<3<活中最大者4与邻换4<1<2<3<比4大者换方向4<1<2<3<此时4的左边为空，没有比它小的，它不是活的活中最大者3与邻换4<1<3<2<比3大者换方向4>1<3<2<活中最大者4与邻换1>4<3<2比4大者换方向1,2,3,4,5,6,7,8,9,1038

活动状态的数最大者邻数互换位置，比m大箭头改变方向。

1<2<3<4<活中最大者4与邻换1<2<4<3<比4大者换方向1<2<4<3<活中最大者4与邻换1<4<2<3<比4大者换方向1<4<2<3<活中最大者4与邻换4<1<2<3<比4大者换方向4<1<2<3<此时4的左边为空，没有比它小的，它不是活的活中最大者3与邻换4<1<3<2<比3大者换方向4>1<3<2<活中最大者4与邻换1<4>3<2<比4大者换方向1<4>3<2<活中最大者4与邻换1<3<4>2<比4大者换向1<3<4>2<活中最大者4与邻换1<3<2<4>比4大者换向1<3<2<4>4的边为空不活，活中最大者3与邻换3<1<2<4>

比3大者换向3<1<2<4<3<1<2<4<活中最大者4与邻换3<1<4<2<，比4大者换向3<1<4<2<活中最大者4与邻换3<4<1<2<,比4大者换向3<4<1<2<活中最大者3与邻换4<3<1<2<,比4大者换向4<3<1<2<此时4左边为空不活活中最大者2与邻换4<3<2<1<

比2大的换向4>3>2<1<4>3>2<1<活中最大者4与邻换3>4>2<1<，比4大者换向

1,2,3,4,5,6,7,8,9,1039

活动状态的数最大者邻数互换位置，比m大箭头改变方向。

3<1<2<4<活中最大者4与邻换3<1<4<2<，比4大者换向3<1<4<2<活中最大者4与邻换3<4<1<2<,比4大者换向3<4<1<2<活中最大者3与邻换4<3<1<2<,比4大者换向4<3<1<2<此时4左边为空不活活中最大者2与邻换4<3<2<1<

比2大的换向4>3>2<1<4>3>2<1<活中最大者4与邻换3>4>2<1<，比4大者换向3>4>2<1<活中最大者4与邻换3>2<4>1<,比4大者换向3>2<4>1<活中最大者4与邻换3>2<1<4>,比4大者换向3>2<1<4>此时4右边为空不活了，活中最大者3与邻换

2<3>1<4>，比3大者换向2<3>1<4<2<3>1<4<活中最大者4与邻换2<3>4<1<，比4大者换向2<3>4<1<活中最大者4与邻换2<4<3>1<,比4大者换向2<4<3>1<活中最大者4与邻换4<2<3>1<,比4大者换向4<2<3>1<4左边为空不活，活中最大者3与换邻4<2<1<3>

比3大者换向4>3<1<3>4>2<1<3>活中最大者4与邻换2<4>1<3>，比4大者换向

1,2,3,4,5,6,7,8,9,1040

活动状态的数最大者邻数互换位置，比m大箭头改变方向。

4>3>2<1<活中最大者4与邻换3>4>2<1<，比4大者换向3>4>2<1<活中最大者4与邻换3>2<4>1<,比4大者换向3>2<4>1<活中最大者4与邻换3>2<1<4>,比4大者换向3>2<1<4>此时4右边为空不活了，活中最大者3与邻换

2<3>1<4>，比3大者换向2<3>1<4<2<3>1<4<活中最大者4与邻换2<3>4<1<，比4大者换向2<3>4<1<活中最大者4与邻换2<4<3>1<,比4大者换向2<4<3>1<活中最大者4与邻换4<2<3>1<,比4大者换向4<2<3>1<4左边为空不活，活中最大者3与换邻4<2<1<3>

比3大者换向4>3<1<3>4>2<1<3>活中最大者4与邻换2<4>1<3>，比4大者换向2<4>1<3>活中最大者4与邻换2<1<4>3>,比4大者换向2<1<4>3>活中最大者4与邻换2<1<3>4>,比4大者换向2<1<3>4>1所指2不比其小2左边为空

3所指4不比其小4所右边为空

所以没有活动中，算法到此结束！

1,2,3,4,5,6,7,8,9,10413.序数法--这是一个好办法，一个排列对应一个数1)预备

①基为阶乘的整数表示法，将整数表示阶乘的组合

k是0～n!-1

中的任一整数，均可唯一表示为：

k=

an-1(n-1)!＋an-2(n-2)!＋…＋a22!＋a11!(*)其中0≤ai≤i,i=1,2,3,…,n-1.对(*)两边除以2，(n-1)!,(n-2)!,...2!均含因数2，故余数即得a1。对除以2的商式再除以3，(n-1)!,(n-2)!,..3!均含因数3，故余数即得a2。对其商除4后取余数即得a3，…,反复进行上述过程，直到商等于0时为止。上述做法不仅给出了确定a1,a2,…,an-2,an-1的方法，同时还证明了(*)式的唯一性，以及(*)式成立的可能性(因为k<n!，故至多除到n时迭代可以终止)。例4000=5·6!+3·5!+4!+2·3!+2·2!

除2得a1，除3得a2，除n得an-1，在黑板上写1,2,3,4,5,6,7,8,9,1042于是，一个整数k对应一个向量a=(an-1,an-2,…a2,a1)；反过来，一个向量

(an-1,an-2,…a2,a1)按(*)式求出一个整数k.。②向量(an-1,an-2,…a2,a1)(n-1个数)与n个元素的排列p1p2p3…pn是一一对应的。对应规则：

A)把ai看成是排列p1p2p3…pn中数i+1在其位置后比它小的数的个数,:

an-1an-2…a2a1(nn-1…32后比其小的数的个数)

例如，排列4213对应的向量a3a2a1为301。

a3表示数i+1=4之后比其小的数3a2表示数i+1=3之后比其小的数无即0a1表示数i+1=2之后比其小的数1个B)*反过来，向量(an-1,an-2,…a2,a1)得到排列的规则是：1,2,3,4,5,6,7,8,9,1043a1的值确定2后面1的个数。为0则2后面没1，则2在最右边，1在2的左边1..2为1由2后面有1，则最后二位为21..21由于a2确定3后面的12的形式a2为0，则3后面没有比其1小的数形如...3,在上步基础上进行处理。a2为1，则3后面有一个1或2，a2为2，则3后面有12或21,；一般地，若已知ai的值和排列p1p2…pi，则可将数i+1插入p1p2…pi从右侧起的第ai个间隔处，i=2,3,…,n-1.例如，当(a3a2a1)为(301)时，对应排列可这样得到；

1→21→213

→4213

.2)算法:(i)令k:=0，得排列123…n,k:=k+1；(ii)由k得其阶乘表示法的系数向量a=(an-1,an-2,…a2,a1)，然后由a得对应的排列p1p2p3…pn。令k:=k+1，若k＞n!结束，否则返回(ii)。例用序数法求4个元素1,2,3,4的全部排列。（见p.25表）1,2,3,4,5,6,7,8,9,1044a1的值确定2后面1的个数。为0后面没1则2在最右边由a1是0或1知2在1的右边或左边，从而得排列12或21；又由a2的值(0,1或2)知3应插入排列q1q2(由1，2组成)中的哪个间隔处；…；一般地，若已知ai的值和排列p1p2…pi，则可将数i+1插入p1p2…pi从右侧起的第ai个间隔处，i=2,3,…,n-1.例如，当(a3a2a1)为(301)时，对应排列可这样得到；

1→21→213

→4213

.2)算法:(i)令k:=0，得排列123…n,k:=k+1；(ii)由k得其阶乘表示法的系数向量a=(an-1,an-2,…a2,a1)，然后由a得对应的排列p1p2p3…pn。令k:=k+1，若k＞n!结束，否则返回(ii)。k=0的向量(0000)得到排列1234n!-1=15k=1(0001)比2小有一个21341,2,3,4,5,6,7,8,9,1045k=0的向量(000)得到排列1234n!-1=23手工构造排列k=1%2(001)比2小有1个，比3小无，比4小无，2134k=2%2%3(010)比2小无,比3小有1个,比4小无1--12-132-1324k=3%2%3(011)比2小1个，比3小1个，比4小无1-21-231-2314k=4%2%3(020)比2小0个,比3小2个,比4小无1-12-312-3124k=5%2%3(021)比2小1个,3小2个,比4小无1-21-321-3214k=6%2%3%4(100)比2小0个,3小0个,比4小1

1-12-123-1243k=7%2%3%4(101)比2小1个,3小0个,比4小1

1-21-213-2143k=8%2%3%4(110)比2小0个,3小1个,比4小1

1-12-132-1342k=9%2%3%4(111)比2小1个,3小1个,比4小1

1-21-231-2341k=10%2%3%4(120)比2小0个,3小2个,比4小1

1-12-312-3142k=11%2%3%4(121)比2小1个,3小2个,比4小1

1-21-321-3241k=12%2%3%4(200)比2小0个,3小0个,比4小2

1-12-123-1423k=13%2%3%4(201)比2小1个,3小0个,比4小2

1-21-213-2413k=14%2%3%4(210)比2小0个,3小1个,比4小2

1-12-132-1432k=15%2%3%4(211)比2小1个,3小1个,比4小2

1-21-231-24311,2,3,4,5,6,7,8,9,1046k=0的向量(000)得到排列1234n!-1=23手工构造排列k=1%2(001)比2小有1个，比3小无，比4小无，2134k=2%2%3(010)比2小无,比3小有1个,比4小无1--12-132-1324k=3%2%3(011)比2小1个，比3小1个，比4小无1-21-231-2314k=4%2%3(020)比2小0个,比3小2个,比4小无1-12-312-3124k=5%2%3(021)比2小1个,3小2个,比4小无1-21-321-3214k=6%2%3%4(100)比2小0个,3小0个,比4小1

1-12-123-1243k=7%2%3%4(101)比2小1个,3小0个,比4小1

1-21-213-2143k=8%2%3%4(110)比2小0个,3小1个,比4小1

1-12-132-1342k=9%2%3%4(111)比2小1个,3小1个,比4小1

1-21-231-2341k=10%2%3%4(120)比2小0个,3小2个,比4小1

1-12-312-3142k=11%2%3%4(121)比2小1个,3小2个,比4小1

1-21-321-3241k=12%2%3%4(200)比2小0个,3小0个,比4小2

1-12-123-1423k=13%2%3%4(201)比2小1个,3小0个,比4小2

1-21-213-2413k=14%2%3%4(210)比2小0个,3小1个,比4小2

1-12-132-1432k=15%2%3%4(211)比2小1个,3小1个,比4小2

1-21-231-2431k=15%2%3%4(211)比2小1个,3小1个,比4小2

1-21-231-2431k=16%2%3%4(220)比2小0个,3小2个,比4小2

1-12-312-3412k=17%2%3%4(221)比2小1个,3小2个,比4小2

1-12-312-3412k=18%2%3%4(300)比2小0个,3小2个,比4小3

1-12-123-41231,2,3,4,5,6,7,8,9,1047k=6%2%3%4(100)比2小0个,3小0个,比4小1

1-12-123-1243k=7%2%3%4(101)比2小1个,3小0个,比4小1

1-21-213-2143k=8%2%3%4(110)比2小0个,3小1个,比4小1

1-12-132-1342k=9%2%3%4(111)比2小1个,3小1个,比4小1

1-21-231-2341k=10%2%3%4(120)比2小0个,3小2个,比4小1

1-12-312-3142k=11%2%3%4(121)比2小1个,3小2个,比4小1

1-21-321-3241k=12%2%3%4(200)比2小0个,3小0个,比4小2

1-12-123-1423k=13%2%3%4(201)比2小1个,3小0个,比4小2

1-21-213-2413k=14%2%3%4(210)比2小0个,3小1个,比4小2

1-12-132-1432k=15%2%3%4(211)比2小1个,3小1个,比4小2

1-21-231-2431k=15%2%3%4(211)比2小1个,3小1个,比4小2

1-21-231-2431k=16%2%3%4(220)比2小0个,3小2个,比4小2

1-12-312-3412k=17%2%3%4(221)比2小1个,3小2个,比4小2

1-12-312-3412k=18%2%3%4(300)比2小0个,3小0个,比4小3

1-12-123-4123k=19%2%3%4(301)比2小1个,3小0个,比4小3

1-21-213-4213k=20%2%3%4(310)比2小0个,3小1个,比4小3

1-12-132-4132k=21%2%3%4(311)比2小1个,3小1个,比4小3

1-21-231-4231k=22%2%3%4(320)比2小0个,3小2个,比4小3

1-12-312-4312k=23%2%3%4(321)比2小1个,3小2个,比4小3

1-21-321-43211,2,3,4,5,6,7,8,9,1048§7组合的生成从1,2,3,…,n中取r个不同元素的算法:(i)从组合123…r开始；

(ii)若已知组合c1c2c3…cr(c1<c2<c3<…<cr)，求下一个组合的步骤是：按下列顺序依次考察，找出第一个不成立的式子：

cr=n,cr-1=n-1,cr-2=n-2,…,ck=n+k-r,…设第一个不成立的为ci≠n+i-r,则

①让c1c2…ci-1不变；

②让ci:=ci+1；

③取ci+1:=ci+1，ci+2:=ci+1+1,…,cr:=cr-1+1。例从1,2,3,4,5,6中取3个不同元素的组合时，256的下一个组合是345。1,2,3,4,5,6,7,8,9,1049§7组合的生成例从1,2,3,4,5,6中取3个不同元素的组合时，256的下一个组合是345。123C3=3<>6+3-3，所以124124C3=4<>6+3-3所以125125C3=5<>6+3-3所以126126C3=6=6+3-3C2=2<>6+2-3134C3=4<>6+3-3=6135C3=5<>6+3-3=6136C3=6=6+3-3=6C2=3<>6+2-3=5145C3=5<>6+3-3=6146C3=6=6+3-3=6C2=4<>6+2-3=5156C3=6=6+3-3=6C2=5=6+2-3=5C1=1<>6+1-3=4234C3=4<>6+3-3=62351,2,3,4,5,6,7,8,9,1050§8A允许重复的组合下次{1,2,...,n}取出r个{a1,a2,...,ar},当ij时ai=aj定理从n个不同元素中取r个允许有重复的元素的组合数为C(n+r-1,r).证明：从n个不同元素中取r个允许有重复的元素的组合与从n+r-1个不同元素中取r个无重复的元素的组合是一一对应的。①不妨设不同元素为1,2,3,…,n，在其中任取r个允许有重复的元素排序后依次记为a1,a2,…,ar，即

a1≤a2≤…≤ar

,因为重复可能相等

则

a1＜a2+1＜a3+2＜…

＜ar+r-1,从a2起各加1

所以从1,2,…,n中取的有重复组合a1,a2,…,ar相当于从1,2,…,n+r-1中取r个无重复组合a1,a2+1,…,ar+r-1。②反过来，在1,2,3,…,n+r-1中任取r个无重复的元素，排序后记为b1,b2,…,br,即：b1<b2<…<br

,（无重复）则b1≤b2-1≤b3-2≤…≤br-r+1,（有重复）一个n+r-1中r个无重复，变成n中有重复的r无重复的组合1,2,3,4,5,6,7,8,9,1051

则b1≤b2-1≤b3-2≤…≤br-r+1,

这样，无重复组合b1,b2,…,br即对应于有重复组合b1,b2-1,…,br-r+1。证毕。例问(x+y+z)4有几项？即要求具有形式

xkymzn（每项出现x,y,z的幂次方，并且k+m+n=4）的项有多少项。这可以看成从三个元素x,y,z中取四个有重复元素的组合的问题，故有n=3,A={x,y,z}r=4取4个元素，可以重复出现

C(3+4-1,4)=15项.(x+y+z)2(x+y+z)2=(x2+y2+z2+2xy+2xz+2yz)2=x4+y4+z4+4x3y+4x3z+4x2yz+4xy3+4xy2z+4y3z+4xyz2+4xz3+4yz3+4x2yz+4xy2z+4xyz2.1,2,3,4,5,6,7,8,9,1052§8B不相邻的组合定理从n个不同元素{1,2,…,n}中取r个不相邻的元素的组合的个数为C(n-r+1,r)。相差2个以上如3,5不相邻,但3,4相邻证明：从n个不同元素中取r个不相邻的元素的组合与从n-r+1个不同元素中取r个无重复的元素的组合一一对应。①不妨设不同元素为1,2,3,…,n，在其中任取r个不相邻的元素，排序后记为a1,a2,…,ar，设

a1＜a2＜…＜ar

,至少相差2个，减1后仍不相同则a1＜a2-1＜a3-2＜…＜ar-r+1,所以从1,2,…,n中取的不相邻元素组合a1,a2,…,ar

对应于从1,2,…,n-r+1中取的无重复组合a1,a2-1,…,ar-r+1。②反过来，在1,2,3,…,n-r+1中任取r个无重复的元素b1,b2,…,br,设

b1<b2<…<br

,不重复,依次加1后相差2个则b1＜b2+1＜b3+2＜…＜br+r-1,

这样，无重复组合b1,b2,…,br即对应于1,2,3,…,n的不相邻组合b1,b2+1,…,br+r-1。证毕。1,2,3,4,5,6,7,8,9,1053§8B不相邻的组合定理从n个不同元素{1,2,…,n}中取r个不相邻的元素的组合的个数为C(n-r+1,r)。相差2个以上如3,5不相邻,但3,4相邻例从1,2,3,4,5,6,7中选3个不相邻的组合个数为

C(7-3+1,3)=10

不相邻--要求更严--组合少些C(n-r+1,r)

可重复--要求更宽--组合多数C(n+r-1,r)1,2,3,4,5,6,7,8,9,1054§9若干恒等式及其组合意义C(n,r)=P(n,r)/r!=n*(n-1)*(n-2)*...(n-r+1)/r!=n!/((n-r)!r!)⒈

C(n,r)=C(n,n-r)，定义式可证明组合意义：从n个不同元素中取走的r个元素，与剩下的n-r个元素是一一对应的，故它们的组合数是相同的。⒉C(n,r)=C(n-1,r)+C(n-1,r-1)组合意义1：设a是其中一个元素。从n个元素中取r个的所有组合(C(n,r)个)中，包括两部分：一是不含有a的所有组合(C(n-1,r)个)，二是含有a的所有组合(C(n-1,r-1)个)。Pascal三角形(杨辉)与(a+b)n展开式各项系数的关系组合意义2：p.37图中从(0,0)到(m,n)的路径总数C(m+n,m)（见p.24），等于(0,0)到(m,n-1)的路径数C(m+n-1,m)和(0,0)到(m-1,n)的路径总数C(m+n-1,m-1)之和。1,2,3,4,5,6,7,8,9,1055⒊C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+...+C(n,0)

可反复利用等式2证明之。

*组合意义1：从元素a1,a2,…,an+r+1中取r个无重复的所有组合，可分为：无a1的组合；有a1但无a2的组合；有a1a2但无a3的组合；有a1a2a3但无a4的组合；

………………

组合意义2：p.38图