组合数学第一章

组合数学第一章第一页，共一百四十二页，2022年，8月28日1.1

加法法则与乘法法则[加法法则] 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言： 若|A|=m,|B|=n,AB=,则|AB|=m+n。第二页，共一百四十二页，2022年，8月28日1.1

加法法则与乘法法则[例]北京每天直达上海的客车有5次，客机有3次，则每天由北京直达上海的旅行方式有5+3=8种。第三页，共一百四十二页，2022年，8月28日1.1

加法法则与乘法法则[乘法法则] 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有m·n种产生方式。集合论语言：若|A|=m,|B|=n,AB={(a,b)|aA,bB},则|AB|=m·n。第四页，共一百四十二页，2022年，8月28日1.1

加法法则与乘法法则[例]某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有53=15个。[例]从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6条道路。第五页，共一百四十二页，2022年，8月28日1.1

加法法则与乘法法则例某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是44=16，而只有43=12种。[要注意题目中隐含的条件或约束]在乘法法则中要注意事件A和事件B的相互独立性。第六页，共一百四十二页，2022年，8月28日1.1

加法法则与乘法法则例

n=73×112×134，求除尽n的整数个数。第七页，共一百四十二页，2022年，8月28日1.1应用举例例某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干钥匙。须４人到场，所备钥匙才能开锁。问①至少有多少把不同的钥匙？②每人至少持几把钥匙？解①每３人至少缺１把钥匙，且每３人所缺钥匙不同。故至少共有()=35把不同的钥匙。73第八页，共一百四十二页，2022年，8月28日1.1应用举例任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁。故每人至少持(

)＝20把不同的钥匙。为加深理解，举一个较简单的例子：４人中３人到场，所求如上。共有(

)=6把不同的钥匙。每人有(

)=3把钥匙。（见下页图）６３４２３２第九页，共一百四十二页，2022年，8月28日1.1应用举例钥匙１２３４５６

A√√√人B√√√C√√√D√√√第十页，共一百四十二页，2022年，8月28日1.2一一对应例在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？解

一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。第十一页，共一百四十二页，2022年，8月28日1.2一一对应例

(Cayley定理)n个有标号的顶点的树的数目等于n。n-2第十二页，共一百四十二页，2022年，8月28日1.2一一对应⑦⑥||②—③—①—⑤—④41253逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子，是内点)形成一个序列，序列的长度为n-2例给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)第一次摘掉②，③为②相邻的顶点，得到序列的第一个数3以此类推，得到序列31551,长度为7－2=5这是由树形成序列的过程。第十三页，共一百四十二页，2022年，8月28日排列与组合定义从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的个数用P(n,r)表示。当r=n时称为全排列。一般不说可重即无重。第十四页，共一百四十二页，2022年，8月28日排列与组合定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的个数用C(n,r)表示，

第十五页，共一百四十二页，2022年，8月28日排列组合举例例把八位同学分成四组，每组两人，有多少种方案？第十六页，共一百四十二页，2022年，8月28日排列组合举例例某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案有多少？第一个人可以有6种进站的方式，也就是从6个入口的任意一个站进站，那么第二个人也可以有6种选择入口的方法，但是假如他和第一个人选择的入口是相同的话，就有谁在前的情况，所以第二个人就有了7种进站方案；同理，第三个人进站的话就有8种进站方案，这样算下去，那么第九个人就有14种进站的方法。根据乘法原理，这9个人的进站方案共有：6×7×8×...×14=726485720种。

第十七页，共一百四十二页，2022年，8月28日圆周排列在一圆周上讨论排列问题，即将一排列排到一圆周上，称之为圆周排列问题。n个元素的r圆周排列方案数：Q(n,r)=P(n,r)/r第十八页，共一百四十二页，2022年，8月28日圆周排列例5个男生，3个女生围一桌而坐，若要求男生B1不和女生G1相邻而坐，有多少种方案？若要求女生不相邻，又有多少种方案？第十九页，共一百四十二页，2022年，8月28日圆周排列例有12对夫妻平分为两桌，围圆桌而坐，问共有几种方案？第二十页，共一百四十二页，2022年，8月28日售票问题某场电影的票价为50元，如果某窗口排队的购票者中，分别有n和m位手持50元和100元面值。问该窗口能正常完成售票（即不出现没钱找零的情形）的概率是多少？第二十一页，共一百四十二页，2022年，8月28日多重集的排列多重集是元素可多次出现的集合，通常把含有k中不同元素的多重集S记作

{n1•a1,n2•a2,…,nk•ak}第二十二页，共一百四十二页，2022年，8月28日多重集的排列设多重集S={n1•a1,n2•a2,…,nk•ak}，且对i=1,2,…k，都有ni≥r，则S的r-排列数为kr.例：求不多于四位的二进制数的个数解：24=16第二十三页，共一百四十二页，2022年，8月28日多重集的排列设多重集S={n1•a1,n2•a2,…,nk•ak}，且有n=n1+n2+…+nk，则S的排列数为

第二十四页，共一百四十二页，2022年，8月28日多重集的排列例：用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？解：N=(5!)/(2!3!)=10.第二十五页，共一百四十二页，2022年，8月28日多重集的组合设多重集S={n1•a1,n2•a2,…,nk•ak}，且对i=1,2,…k，都有ni≥r，则S的r-组合数为C(k+r-1,r).证明：一一对应法第二十六页，共一百四十二页，2022年，8月28日多重集的组合例：试问(x+y+z)4有多少项？解：(x+y+z)4

=(x+y+z)(x+y+z)(x+y+z)(x+y+z)相当于多重集{4•x,4•y4•z}的4-组合，于是N=C(3+4-1,4)=15.第二十七页，共一百四十二页，2022年，8月28日不相邻的组合所谓不相邻的组合，是指从A={1,2,…,n}取r个不相邻的数的组合，即不存在含有相邻两个数j和j+1的组合。例如，对n=7,r=3,有组合{1,3,5},{1,3,6},{1,3,7},{1,4,6},{1,4,7},{1,5,7},{2,4,6},{2,4,7},{2,5,7},{3,5,7}第二十八页，共一百四十二页，2022年，8月28日不相邻的组合定理：从A={1,2,…,n}中取r个作不相邻的组合，其组合数为C(n-r+1,r)。证明：一一对应法第二十九页，共一百四十二页，2022年，8月28日线性方程整数解的个数问题已知线性方程x1+x2+…+xn=b，n和b都是整数，求此方程的非负整数解的个数。定理：上述方程非负整数解的个数为C(n+b-1，b)第三十页，共一百四十二页，2022年，8月28日组合意义的解释例：从(0,0)到(m,n)的最短路径的数量。例：C(n,r)=C(n,n-r)例：C(n,r)=C(n-1,r)+C(n-1,r-1)第三十一页，共一百四十二页，2022年，8月28日组合意义的解释例(杨辉三角)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)第三十二页，共一百四十二页，2022年，8月28日组合意义的解释例：

C(n,l)C(l,r)=C(n,r)C(n-r,l-r)(l≥r)第三十三页，共一百四十二页，2022年，8月28日组合意义的解释例：C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0)其中，r≤min(m,n)第三十四页，共一百四十二页，2022年，8月28日2)“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有9个，2位数有9个，3位数有9个，4位数有9个不含0小于10000的正整数有9+9+9+9=(9－1)/(9－1)=7380个含0小于10000的正整数有9999－7380=2619个2342345第三十五页，共一百四十二页，2022年，8月28日1.2排列与组合定义从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为

-P(n,r),P(n,r)。l第三十六页，共一百四十二页，2022年，8月28日1.2排列与组合定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)表示，对应于可重组合

-有记号C(n,r),C(n,r)。第三十七页，共一百四十二页，2022年，8月28日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)有时也用[n]r记n(n-1)······(n-r+1)第三十八页，共一百四十二页，2022年，8月28日1.2排列与组合若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有

C(n,r)·r!=P(n,r),C(n,r)=P(n,r)/r!=[n]r/r!=(

)=易见P(n,r)=nnrr

n!———r!(n-r)!第三十九页，共一百四十二页，2022年，8月28日1.2排列与组合例有5本不同的日文书，7本不同的英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书第四十页，共一百四十二页，2022年，8月28日1.2排列与组合解

1)5×7+5×10+7×10=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=()5+7+102第四十一页，共一百四十二页，2022年，8月28日1.2排列与组合例从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解将[1,300]分成3类：

A={i|i≡1(mod3)}={1,4,7,…,298},B={i|i≡2(mod3)}={2,5,8,…,299},C={i|i≡3(mod3)}={3,6,9,…,300}.

要满足条件，有四种解法：1)3个数同属于A;2)3个数同属于B3)3个数同属于C;4)A,B,C各取一数.故共有3C(100,3)+100=485100+1000000=14851003第四十二页，共一百四十二页，2022年，8月28日1.2排列与组合例某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案有多少？其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。第四十三页，共一百四十二页，2022年，8月28日1.2排列与组合[解法1]标号可产生5!个14个元的全排列。故若设x为所求方案，则

x·5!=14!∴x=14!/5!=726485760第四十四页，共一百四十二页，2022年，8月28日1.2排列与组合[解法2]在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。故C(14,5)·9!即所求第四十五页，共一百四十二页，2022年，8月28日1.2排列与组合[解法3]把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。以此类推，9号有14种选择。

9故所求方案为[6]第四十六页，共一百四十二页，2022年，8月28日1.3Stirling近似公式组合计数的渐进值问题是组合论的一个研究方向。Stirling公式给出一个求n!的近似公式，它对从事计算和理论分析都是有意义的。第四十七页，共一百四十二页，2022年，8月28日1.3Stirling近似公式1)Wallis公式令Ik=∫sinxdx.显然I0=,I1=1.k≥2时，Ik=－cosxsinx|+∫(k－1)cosxsinxdx=0+(k－1)∫(1－sinx)sinxdx=(k－1)(Ik－2－Ik)kπ－

2k-1π－20π－20π－20π－202k-22k-2故

Ik=——Ik-2(1-3-1)k-1k第四十八页，共一百四十二页，2022年，8月28日1.3Stirling近似公式令n!!=1·3·5·…·(n-2)·n，n是奇数。2·4·6·…·(n-2)·n，n是偶数。(1-3-2)由(1-3-1)，———I1,k是奇数

Ik=———I0,k是偶数(k-1)!!k!!(k-1)!!k!!当x∈(0,π/2)时，sinx<sinx因而I2k+1<I2k<I2k-1,k=1,2,…。k+1k第四十九页，共一百四十二页，2022年，8月28日1.3Stirling近似公式由(1-3-2)————<————·—<————，(2k)!!(2k-1)!!π(2k-2)!!(2k+1)!!(2k)!!2(2k-1)!!1<——————<——1.π—2[——](2k)!!(2k-1)!!1·——2k+12k+12k2k→∞第五十页，共一百四十二页，2022年，8月28日1.3Stirling近似公式所以lim=,(2k)!!(2k-1)!!1·——2k+12[——]π—2k→∞lim

=,(2k)!!(2k)!!(2k)!1·——2k+12[————]π—2k→∞lim=。(1-10-3)2(k!)(2k)!1·——2k+12[——]π—2k→∞2k2第五十一页，共一百四十二页，2022年，8月28日1.3Stirling近似公式2)stirling公式yy=lnx

0123n-1nx第五十二页，共一百四十二页，2022年，8月28日1.3Stirling近似公式令An=∫lnxdx=xlnx|－∫dx=nlnn－n+1

(1-3-4)tn=－ln1+ln2+…+ln(n－1)+－lnn =ln(n!)－－lnn(1-3-5)tn的几何意义是由x轴,x=n,以及连接(1,0),(2,ln2),…,(n－1,ln(n－1)),(n,lnn)诸点而成的折线围成的面积。nnn111112 212第五十三页，共一百四十二页，2022年，8月28日1.3Stirling近似公式Tn=－+ln2+…+ln(n－1)+－lnn(1-3-6)1182Tn是由三部分面积之和构成的。一是曲线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轴包围的矩形面积。因而有

tn<An<Tn

(1-3-7)121212第五十四页，共一百四十二页，2022年，8月28日1.3Stirling近似公式令bn=An

－tn.序列b1,b2,…是单调增，而且有上界，故有极限，令limbn=b1由(1-3-4),(1-3-5)得 bn=nlnn－n+1－ln(n!)+－lnn

=

lnn－n+1－ln(n!)+－lnn

ln(n!)=1－bn+lnn－lnn

－lne∴n!=en(－)

(1-3-8)0<An－tn<Tn－tn=－18n→∞12n√√nn1-bn√nen第五十五页，共一百四十二页，2022年，8月28日1.3Stirling近似公式令βn=e,limβn=β.将(1-3-8)代入(1-3-3),整理得 β=2π.所以 n!~2πn(－)n→∞1-bn√√nen第五十六页，共一百四十二页，2022年，8月28日1.4模型转换“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与[1,n]元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换。比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。第五十七页，共一百四十二页，2022年，8月28日1.4模型转换例简单格路问题|(0,0)→(m,n)|=()从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？m+nmy(m,n)...0...x第五十八页，共一百四十二页，2022年，8月28日1.4模型转换无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。则(0,0)→(m,n)的每一条路径可表示为m个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。第五十九页，共一百四十二页，2022年，8月28日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)设c≥a,d≥b,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=()(m+n)!m+nm+nm!n!mn(c-a)+(d-b)c-a(c,d)(a,b)第六十页，共一百四十二页，2022年，8月28日1.4模型转换例在上例的基础上若设m<n，求(0,1)点到(m,n)点不接触对角线x=y的格路的数目(“接触”包括“穿过”)从(0,1)点到(m,n)点的格路，有的接触x=y，有的不接触。对每一条接触x=y的格路，做(0,1)点到第一个接触点部分关于x=y的对称格路，这样得到一条从(1,0)到(m,n)的格路。第六十一页，共一百四十二页，2022年，8月28日1.4模型转换容易看出从(0,1)到(m,n)接触x=y的格路与(1,0)到(m,n)的格路(必穿过x=y)一一对应yy=x(m,n)0(1,0)x(0,1)..yx-y=1(m,n)x(0,0)(1,1).....第六十二页，共一百四十二页，2022年，8月28日1.4模型转换故所求格路数为()－()=———－———=————(—－—)=——()=(1－—)()=——()m+n-1m+n-1mm-1(m+n-1)!(m+n-1)!(m+n-1)!11m!(n-1)!(m-1)!n!(m-1)!(n-1)!mnm+n-1m+n-1mm

n-mmnnm+n-1m

n-mn第六十三页，共一百四十二页，2022年，8月28日1.4模型转换若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得x－y=1，(0,0)关于x－y=1的对称点为(1,-1).所求格路数为()－()=——－————=———()m+nm+nmm-1(m+n)!(m+n)!n+1-mm!n!(m-1)!(n+1)!

n+1m+nm格路也是一种常用模型第六十四页，共一百四十二页，2022年，8月28日1.4模型转换例

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丙烷第六十五页，共一百四十二页，2022年，8月28日1.4模型转换

H|H—C—H|H—C—H|H—C—H|H—C—H|H

H|HH—CH||H—C—C—H||H—CH|HHn=4丁烷n=4异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.第六十六页，共一百四十二页，2022年，8月28日1.4模型转换例在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？解

一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。第六十七页，共一百四十二页，2022年，8月28日1.4模型转换例

(Cayley定理)n个有标号的顶点的树的数目等于n。n-2生长点不是叶子,每个生长点是[1,n]中的任一元.有n种选择。两个顶点的树是唯一的。第六十八页，共一百四十二页，2022年，8月28日1.4模型转换⑦⑥||②—③—①—⑤—④41253逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子，是内点)形成一个序列，序列的长度为n-2例给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)第一次摘掉②，③为②相邻的顶点，得到序列的第一个数3以此类推，得到序列31551,长度为7－2=5这是由树形成序列的过程。第六十九页，共一百四十二页，2022年，8月28日1.4模型转换由序列形成树的过程：由序列31551生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序排序的序列1234567，序列的长度为5+2(即n+2)，然后将11355按照大小插入到序列1234567中，得到111233455567然后将两个序列排在一起31551第七十页，共一百四十二页，2022年，8月28日1.4模型转换

31551111233455567②—③

15511113455567①—③

55111455567④—⑤

51115567⑤—⑥

11157①—⑤

17第一步推导：将上下两个序列同时去掉上行序列的第一个元素3(用黄色表示)，去掉下行序列的第一个无重复的元素2(用红色表示)。生成一条边(②—③)。依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。第七十一页，共一百四十二页，2022年，8月28日1.4模型转换上述算法描述：给定序列b=(b1b2…bn-2)设a=(123…n-1n)将b的各位插入a,得a’,对()做操作。a’是2n-2个元的可重非减序列。ba’操作是从a’中去掉最小无重元，设为a1,再从b和a’中各去掉一个b中的第一个元素，设为b1，则无序对(a1,b1)是一条边。重复这一操作，得n-2条边，最后a’中还剩一条边，共n-1条边，正好构成一个树。b中每去掉一个元，a’中去掉2个元。第七十二页，共一百四十二页，2022年，8月28日1.4模型转换由算法知由树T得b=(b1b2…bn-2)，反之，由b可得T。即f：T→b是一一对应。由序列确定的长边过程是不会形成回路的。因任意长出的边(u,v)若属于某回路，此回路中必有一条最早生成的边，不妨就设为(u,v)，必须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故由()得到的边必构成一个n个顶点的树。ba’第七十三页，共一百四十二页，2022年，8月28日1.4模型转换证由一棵n个顶点的树可得到一个长度为n－2的序列，且不同的树对应的序列不同*，因此|T

|≤n。*对n用归纳法可证反之，由一个长度为n－2的序列(每个元素为1~n的一个整数)，可得到一棵树，且不同的序列对应的树是不同的，因此 n≤|T||T|=n#n-2n-2n-2第七十四页，共一百四十二页，2022年，8月28日1.5全排列的生成算法

就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。全排列的生成算法第七十五页，共一百四十二页，2022年，8月28日1.5全排列的生成算法这里介绍全排列算法四种：(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法第七十六页，共一百四十二页，2022年，8月28日字典序法

对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。第七十七页，共一百四十二页，2022年，8月28日字典序法[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。※※

一个全排列可看做一个字符串，字符串可有前缀、后缀。第七十八页，共一百四十二页，2022年，8月28日字典序法1）生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。第七十九页，共一百四十二页，2022年，8月28日字典序法[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。第八十页，共一百四十二页，2022年，8月28日字典序法求839647521的下一个排列7521

74＜7

4<5

5

4>2

2

4>1

1

在后缀7521中找出比4大的数75找出其中比4大的最小数55

4、5

对换8396

72154后缀变为7421将此后缀翻转1247接上前缀83965得到839651247即839647521的下一个。[例]为后缀大于4的用橙色表示小于4的用绿色表示

找出比右边数字小的第一个数4第八十一页，共一百四十二页，2022年，8月28日字典序法在[1,n]的全排列中,nn-1…321是最后一个排列,其中介数是(n-1,n-2,...,3,2,1)其序号为n-1∑k×k!k=1另一方面可直接看出其序号为n!-1

n-1n-1于是n!-1=∑k×k!

即

n!=∑k×k!+1

k=1k=1第八十二页，共一百四十二页，2022年，8月28日字典序法一般而言，设P是[1,n]的一个全排列。P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pnj=max{i|Pi<Pi+1},k=max{i|Pi>Pj}对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转，P’=P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个第八十三页，共一百四十二页，2022年，8月28日字典序法2)计算给定排列的序号839647521的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类。前缀先于8的排列的个数：7×8!第一位是8,先于83得的排列的个数：2×7!前2位是83,先于839得的排列的个数：6×6!先于此排列的的排列的个数：7×8!+2×7!+6×6!前3位是839,先于8396得的排列的个数：4×5!+4×5!前4位是8396,先于83964得的排列的个数：2×4!+2×4!前5位是83964,先于839647得的排列的个数：3×3!+3×3!前6位是839647,先于8396475得的排列的个数：2×2!+2×2!前7位是8396475,先于83964752得的排列的个数：1×1!+1×1!297191前8位固定，则最后一位也随之固定将8!,7!,…,1!前面的系数抽出，放在一起得到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的序号的中间环节，我们称之为中介数。※这是一个很有用的概念。第八十四页，共一百四十二页，2022年，8月28日字典序法一般而言,对于[1,9]的全排列中介数首位的取值为0—8，第2位的取值为0—7，以此类推，第8位的取值为0、1。从而序号可表示为：

n-1∑ki(n-i)!i=1ki：Pi的右边比Pi小的数的个数i=1,2,…,n-1第八十五页，共一百四十二页，2022年，8月28日字典序法由中介数推出排列的算法[例]由72642321推算出839647521方法1：P1P2P3P4P5P6P7P8P9_________P1=88→7+1=82+1=3→P2=336+1=7，但3已在P3左边出现，↑7+1=8，但8已在P3左边出现，↑8+1=9→P3=994+1=5，但3已经在P4左边出现，5+1=6→P4=66↑2+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=121这个过程比较麻烦(这酝酿着改进的可能)，该算法从左到右依次推出P1,P2,…,P9。下述算法依次定出1,2,3,…,9的位置。第八十六页，共一百四十二页，2022年，8月28日字典序法方法2-1：72642321中未出现0，1在最右边中介数右端加一个0扩成9位，先定1，每定一位，其左边未定位下加一点，从（位－位下点数=0）的位中选最左的。726423210定1的位置1●●●●●●●●22●●●●●●●33●44●●●55●●●●66●●77●●8899由72642321推算出839647521第八十七页，共一百四十二页，2022年，8月28日字典序法方法2-2：已定出上标‘●’，找左起第一个0，下标‘__’由72642321推算出839647521

●72642321-11111111=61531210________12

●●●●61531210-11111110=504201003●●●●50420100-10000000=404201004●●●●●40420100-10110000=303101005●●●●●●●●30310100-10110100=202000006●●●●●●●●●●20200000-10100000=101000007●●●●●●●●●●●●10100000-10100000=000000008●●●●●●●000000009以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数→进位链（中介数的后继）→递增进位制数第八十八页，共一百四十二页，2022年，8月28日递增进位制数法1)由排列求中介数在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。

在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2—n)一致。第八十九页，共一百四十二页，2022年，8月28日递增进位制数法可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，…，右起第i位逢i+1进1，i=1,2,…,n-1.这样的中介数我们称为递增进位制数。上面是由中介数求排列。第九十页，共一百四十二页，2022年，8月28日递增进位制数法由序号（十进制数）求中介数（递增进位制数）如下：

m=m1,0≤m≤n!-1m1=2m2+kn-1,0≤kn-1≤1m2=3m3+kn-2,0≤kn-2≤2

…………….

mn-2=(n-1)mn-1+k2,0≤k2≤n-2mn-1=k1,0≤k1≤n-1

p1p2…pn←→(k1k2…kn-1)↑←→m第九十一页，共一百四十二页，2022年，8月28日递增进位制数法在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。为方便起见，令ai+1=kn-I，i=1,2,…,n-1(k1k2…kn-1)↑=(anan-1…a2)↑ai：i的右边比i小的数字的个数第九十二页，共一百四十二页，2022年，8月28日递增进位制数法在这样的定义下，有839647521←→(67342221)↑(67342221)↑+1=(67342300)↑←→8496175236×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1=279905第九十三页，共一百四十二页，2022年，8月28日递增进位制数法由(anan-1…a2)↑求p1p2…pn。从大到小求出n,n-1,…,2,1的位置_..._n__…_

an个空格n的右边有an个空格。n-1的右边有an-1个空格。…………2的右边有a2个空格。最后一个空格就是1的位置。\____________/

V第九十四页，共一百四十二页，2022年，8月28日递增进位制数法_________

67342221↓↓↓↓↓↓↓↓

a9a8a7a6a5a4a3a2★\____________________/

V

6个空格9★\____________________________/

V

7个空格8★★★★★★\________/

V

3个空格765431\________________/

V

4个空格\____/

V

2个空格1个空格

序号

nm=∑ak(k-1)!

k=22第九十五页，共一百四十二页，2022年，8月28日递减进位制数法在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。(anan-1…a2)↑→(a2a3…an-1an)↓839647521→(12224376)↓

nnm=∑akn!/k!=n!∑ak/k!

k=2k=2(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989

※※

求下一个排列十分容易第九十六页，共一百四十二页，2022年，8月28日邻位对换法递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。第九十七页，共一百四十二页，2022年，8月28日邻位对换法这个算法可描述如下：对1—n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1—n的n个排列。对1—n-1的每一个奇排列，n从左到右插入n个空档，生成1—n的n个排列。对[2,n]的每个数字都是如此。第九十八页，共一百四十二页，2022年，8月28日邻位对换法[例]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上加一个点。1—8上共有3个(奇数)点，9上箭头向右。P=839647521→()↓b2b3b4b5b6b7b8b9101213722上箭头向左，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=2839647521的中介数为10121372←→→→→→→←第九十九页，共一百四十二页，2022年，8月28日邻位对换法ak(p)：p中1—k排列的序号，ak(p)的奇偶性与1—k排列的奇偶性相同。a9(p)=9×a8(p)+b9(p)=9×(8×a7(p)+b8(p))+b9(p)※※an(p)，bn(p)简写成an，bn第一百页，共一百四十二页，2022年，8月28日邻位对换法已知(10121372)↓求排列。9的位置由b9和a8的奇偶性决定。a8的奇偶性同b8的奇偶性。a7的奇偶性同b7+b6的奇偶性。b2=0,1。→←→b8奇→9，b6+b7偶→8，b6奇→7，→→

b4+b5奇→6，b4奇→5第一百零一页，共一百四十二页，2022年，8月28日邻位对换法序号=1·3+0)·4+1)·5+2)·6+1)·7+3)·8+7)·9+2=203393←→(10121372)↓第一百零二页，共一百四十二页，2022年，8月28日邻位对换法第一百零三页，共一百四十二页，2022年，8月28日1.6组合的生成设从[1,n]中取r元的组合全体为C(n,r).C1C2…Cr∈C(n,r).不妨设C1＜C2＜…＜Cri≤Ci≤(n－r+i),i=1,2,…,r令j=max{i|Ci＜n－r+i}.则C1C2…Cr的下一个组合为C1C2…Cj-1(Cj+1)(Cj+2)…(Cj+r－j+1)这等于给C(n,r)的元素建立了字典序。12…r的序号为0，n-r+1n-r+2…n的序号为()－1____________

nr第一百零四页，共一百四十二页，2022年，8月28日1.6组合的生成例在C(10,4)中4679的序号是首位小于4的组合的个数；首位是4，第2位小于6的组合的个数；前2位是46，第3位小于7的组合的个数；前3位是467，第4位小于9的组合的个数之和。反之，也可以由序号求组合。第一百零五页，共一百四十二页，2022年，8月28日1.6组合的生成A(m,l)：[1,m]的l-组合(或l-子集)。第1个组合：{1,2,…,l-1,l}.最后1个组合：{1,2,…,l-1,m}A(n,k)=A(n-1,k)，A(n-1,k-1)○{n}A：将有序集A(或线性表)的顺序逆转的有序集。A○n：将A中每个元素(是集合)都与{n}求并的有序集__×__×____第一百零六页，共一百四十二页，2022年，8月28日1.6组合的生成例

用两种方法计算[1,n]的无重不相邻组合C’(n,r)的计数问题解法1

0…010…010…010…010…0其中不可含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第一百零七页，共一百四十二页，2022年，8月28日1.6组合的生成②以0结尾：r个10与n-2r个0的排列r+n-2r=n-r这样的排列有()个(

)+(

)=(

)

f(a1a2…ar)=b1b2…brn-rrn-rn-rn-r+1r-1rr第一百零八页，共一百四十二页，2022年，8月28日1.6组合的生成解法２任给a1a2…ar∈C’(n,r),

a1＜

a2＜

…＜

ar令f：a1a2…ar→b1b2…brbi=ai-i+1,i=1,2,…,r.1≤b1＜

b2＜

…＜

br≤n-r+1,

b1b2…br∈C(n-r+1,r)C’(n,r)=C(n-r+1,r)第一百零九页，共一百四十二页，2022年，8月28日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个相同的球/\———————————————／\0…010…01…10…0

\/————————\/

n-1个相同的盒壁第一百一十页，共一百四十二页，2022年，8月28日1.7可重组合另证设a1a2…ar∈C(n,r)

1≤a1≤a2≤…≤ar≤n,令C(n,r)上的f，使得bi=ai+i-1,i=1,2,…,r.