组 合 数 学前言组合数学是一个古老而又年轻的数学分支。
据传说，大禹在 4000多年前就观察到神龟背上的幻方 …...
前言幻方可以看作是一个 3阶方阵，其元素是 1
到 9的正整数，
每行、每列以及两条对角线的和都是 15。
5
1
9
3 7
24
8 6
前言贾宪 北宋数学家（约 11世纪） 著有《黄帝九章细草》、《算法斅古集》斅 音“笑（“古算法导引”）都已失传。杨辉著《详解九章算法》（ 1261年）中曾引贾宪的“开方作法本源”
图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早 600
年，后者比霍纳（ William Geoge Horner，
1786— 1837） 的方法（ 1819年）早 770年。
前言
1666年莱布尼兹所著《组合学论文》
一书问世，这是组合数学的第一部专著。
书中首次使用了组合论（ Combinatorics）
一词。
前言组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。
前言
本学期主要讲组合分析（计数和枚举）
以及组合优化的一部分（线性规划的单纯形解法）。
组合分析是组合算法的基础。
前言组合数学经常使用的方法并不高深复杂。最主要的方法是 计数时的合理分类 和 组合模型的转换。
但是，要学好组合数学并非易事，
既需要一定的数学修养，也要进行相当的训练。
第一章 排列组合
1.1 加法法则与乘法法则
1.1 加法法则与乘法法则
[ 加法法则 ] 设事件 A有 m种产生方式，
事件 B有 n种产生方式，则事件 A或 B之一有 m+n种产生方式。
集合论语言：
若 |A| = m,|B| = n,A?B =?,则
|A?B| = 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,
A?B = {(a,b) | a?A,b? B},
则 |A? B| = m ·n 。
1.1 加法法则与乘法法则
[例 ] 某种字符串由两个字符组成，第一个字符可选自 {a,b,c,d,e},第二个字符可选自 {1,2,3}，则这种字符串共有 5?3
= 15 个。
[例 ] 从 A到 B有三条道路，从 B到 C有两条道路，则从 A经 B到 C有 3?2=6 条道路。
1.1 加法法则与乘法法则
例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、
橙、黄，条纹色可选黑、白，则共有 4?2
= 8种着色方案。
若此例改成底色和条纹都用红、蓝、橙、
黄四种颜色的话，则，方案数就不是 4?
4 = 16,而只有 4? 3 = 12 种。
在乘法法则中要注意事件 A 和 事件 B 的相互独立性。
1.1 加法法则与乘法法则例 1)求小于 10000的含 1的正整数的个数
2)求小于 10000的含 0的正整数的个数
1)小于 10000的不含 1的正整数可看做 4位数,
但 0000除外,
故有 9× 9× 9× 9－ 1＝ 6560个,
含 1的有,9999－ 6560=3439个另,全部 4位数有 10 个,不含 1的四位数有 9 个,
含 1的 4位数为两个的差,10 － 9 = 3439个4 4
4 4
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个
2
3 4
2 3 4 5
1.2排列与组合定义 从 n个不同的元素中，取 r个不重复的元素，按次序排列，称为从 n个中取
r个的 无重排列 。排列的全体组成的集合用 P(n,r)表示。排列的个数用 P(n,r)表示。当 r=n时称为 全排列 。一般不说可重即无重。可重排列的相应记号为
-P(n,r),P(n,r)。
1.2排列与组合定义从 n个不同元素中取 r个不重复的元素组成一个子集，而不考虑其元素的顺序，
称为从 n个中取 r个的 无重组合 。
组合的全体组成的集合用 C(n,r)表示，组合的个数用 C(n,r)表示，对应于可重组合-
有记号 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)
有时也用 [n]r记 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!=[n]r/r!=( )=
易见 P(n,r)=n
nr
r
n!———
r!(n-r)!
若球不同，盒子相同，则是从 个中取 个的 组合 的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有 个标号方案。
故有易见
1.2排列与组合例 有 5本不同的日文书,7本不同的英文书,10本不同的中文书。
1)取 2本不同文字的书；
2)取 2本相同文字的书；
3)任取两本书
1.2排列与组合
5+7+10
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=( )
1.2排列与组合
求 r1个 1,r2个 2,…,rt个 t的排列数，设
r1+r2+…+r t=n,设此排列数为 P(n;r1,r2,…,r t),
对 1,2,…,t分别加下标，得到
P(n； r1,r2,…,r t)·r1!·r2!·… ·rt! = n!
∴ P(n； r1,r2,…,r t)= ———— =( )n!r
1!r2!…r t!
nr
1 r2 … r t
1.2排列与组合
从 n个中取 r个的圆排列的排列数为
P(n,r)/r,2≤r≤n
以 4个元素为例
1
2 4
3
1234
1
2 4
3
2341
1
2 4
3
3412
1
2 4
3
4123
1.2排列与组合
从 n个中取 r个的项链排列的排列数为
P(n,r)/2r,3≤r≤n
项链排列就是说排列的方法和项链一样,
在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。
例 下面两种方式实际上表示的都是 3个元素的同一种排列。
1 1
2 3 3 2
1.2排列与组合例 从 [1,300]中取 3个不同的数，使这
3个数的和能被 3整除，有多少种方案？
解 将 [1,300]分成 3类：
A={i|i≡1(mod 3)}={1,4,7,…,298},
B={i|i≡2(mod 3)}={2,5,8,…,299},
C={i|i≡3(mod 3)}={3,6,9,…,300}.
要满足条件，有四种解法：
1)3个数同属于 A;2)3个数同属于 B
3)3个数同属于 C;4)A,B,C各取一数,
故共有 3C(100,3)+100 =485100+1000000=14851003
1.2排列与组合例 某车站有 6个入口处，每个入口处每次只能进一人，一组 9个人进站的方案有多少？
[解 ]一进站方案表示成,00011001010100
其中,0”表示人，,1”表示门框，其中,0”是不同元，,1”是相同元。给,1” n个门只用 n-1
个门框。任意进站方案可表示成上面 14个元素的一个排列。
1.2排列与组合
[解法 1]标号可产生 5!个 14个元的全排列。
故若设 x为所求方案，则
x·5!=14!
∴x=14!/5!=726485760
1.2排列与组合
[解法 2]在 14个元的排列中先确定,1”
的位置，有 C(14,5)种选择，在确定人的位置，有 9！种选择。
故 C(14,5)·9! 即所求
1.2排列与组合
[解法 3]把全部选择分解成若干步，使每步宜于计算。不妨设 9个人编成 1至 9号。 1号有 6种选择； 2号除可有 1号的所有选择外，
还可（也必须）选择当与 1号同一门时在 1
号的前面还是后面，故 2号有 7种选择； 3号的选择方法同 2号，故共有 8种。
以此类推,9号有 14种选择。
9故所求方案为 [6]
1.3 Stirling近似公式
组合计数的渐进值问题是组合论的一个研究方向。
Stirling公式给出一个求 n!的近似公式，它对从事计算和理论分析都是有意义的。
1.3 Stirling近似公式
1)Wallis公式令 Ik=∫ sin xdx.显然 I0=,I1=1.
k≥2时，
Ik=－ cosxsin x| +∫ (k－ 1)cos xsin xdx
=0+(k－ 1)∫ (1－ sin x)sin xdx
=(k－ 1)(Ik－ 2－ Ik)
k π－
2
k-1 π－ 2
0
π－
2
0π－
2
0
π－
2
0
2 k-2
2 k-2
故
Ik = —— Ik-2 (1-3-1)k-1k
1.3 Stirling近似公式令 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)时,sin x < sin x
因而 I2k+1<I2k<I2k-1,k=1,2,… 。
k+1 k
1.3 Stirling近似公式
由 (1-3-2)
———— < ———— ·— < ————,(2k)!! (2k-1)!! π (2k-2)!!(2k+1)!! (2k)!! 2 (2k-1)!!
1< —————— < —— 1.
π—
2
[—— ] (2k)!!(2k-1)!! 1· ——2k+1
2k+1
2k2 k→∞
1.3 Stirling近似公式
所以
lim =,(2k)!!(2k-1)!! 1· ——2k+1
2[—— ] π—
2k→∞
lim =,(2k)!!(2k)!!(2k)! 1· ——2k+1
2[———— ] π—
2k→∞
lim = 。 (1-10-3)2 (k!)(2k)! 1· ——2k+1
2[—— ] π—
2k→∞
2k 2
1.3 Stirling近似公式
2)stirling公式
y
y=lnx
0 1 2 3 n-1 n x
1.3 Stirling近似公式
令 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)诸点而成的折线围成的面积。
n n n
1 1 1
1 1
2 21
2
1.3 Stirling近似公式
Tn=－ +ln2+…+ln( n－ 1)+－ lnn (1-3-6)1 18 2
Tn是由三部分面积之和构成的。一是曲线
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)
12
12
12
1.3 Stirling近似公式
令 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!)+－ ln n
ln(n!)=1－ bn+ lnn － ln n － lne
∴ n!=e n (－ ) (1-3-8)
0<An－ tn<Tn－ tn=－ 18
n→∞
12
n √
√n n
1-bn√ ne n
12
1.3 Stirling近似公式
令 βn=e,limβn=β.
将 (1-3-8)代入 (1-3-3),整理得
β= 2π,
所以
n! ~ 2πn (－ )
n→∞
1-bn
√
√ ne n
1.4模型转换
,一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。
如我们说 A集合有 n个元素 |A|=n,无非是建立了将 A中元与 [1,n]元一一对应的关系。
在组合计数时往往借助于一一对应实现模型转换。
比如要对 A集合计数，但直接计数有困难，
于是可设法构造一易于计数的 B,使得 A
与 B一一对应。
1.4模型转换
例 简单格路问题 |(0,0)→(m,n)|=( )
从 (0,0)点出发沿 x轴或 y轴的正方向每步走一个单位，最终走到 (m,n)点，有多少条路径？
m+nm
y
(m,n)
..
.
0,,,x
1.4模型转换
无论怎样走法，在 x方向上总共走 m步，
在 y方向上总共走 n步。若用一个 x表示 x
方向上的一步，一个字母 y表示 y方向上的一步。
则 (0,0)→(m,n)的每一条路径可表示为 m
个 x与 n个 y的一个有重排列。将每一个有重排列的 x与 y分别编号，可得 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)
设 c≥a,d≥b,则由 (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模型转换
例 在上例的基础上若设 m<n,求 (0,1)
点到 (m,n)点不接触对角线 x=y的格路的数目 (“接触”包括“穿过” )
从 (0,1)点到 (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模型转换
故所求格路数为 ( )－ ( ) = —
—— － ——— = ———— ( — － — )
= —— ( )=(1－ — )( )
= —— ( )
m+n-1 m+n-1m m-1
(m+n-1)! (m+n-1)! (m+n-1)! 1 1
m!(n-1)! (m-1)!n! (m-1)!(n-1)! m n
m+n-1 m+n-1m mn-m m
n n
m+n-1 m n-m
n
1.4模型转换
若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得 x－ y=1，
(0,0)关于 x－ y=1的对称点为 (1,-1).
所求格路数为 ( )－ ( )
= —— － ———— = ——— ( )
m+n m+nm m-1
(m+n)! (m+n)! n+1-m
m!n! (m-1)!(n+1)! n+1
m+n m
格路也是一种常用模型
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
|
H
n=1甲烷 n=2 乙烷 n=3 丙烷
1.4模型转换
H
|
H — C — H
|
H — C — H
|
H — C — H
|
H — C — H
|
H
H
| H
H — C H
| |
H — C — C — H
| |
H — C H
| H
H
n=4 丁烷 n=4异丁烷这说明对应 CnH2n+2的枝链是有 3n+2个顶点的一棵树，其中 n个顶点与之关联的边数为 4；其它 2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物 CnH2n+2.
1.4模型转换
例 在 100名选手之间进行淘汰赛 (即一场的比赛结果，失败者退出比赛 ),最后产生一名冠军，问要举行几场比赛？
解 一种常见的思路是按轮计场，费事。
另一种思路是淘汰的选手与比赛 (按场计 )
集一一对应。 99场比赛。
1.4模型转换
例 (Cayley定理 ) n个有标号的顶点的树的数目等于 n 。n-2
生长点不是叶子,每个生长点是 [1,n]中的任一元,有 n种选择。两个顶点的树是唯一的。
1.4模型转换
⑦ ⑥| |
② — ③ — ① — ⑤ — ④
4
1 2 5 3
逐个摘去标号最小的叶子，叶子的相邻顶点 (不是叶子，是内点 )形成一个序列，
序列的长度为 n-2
例 给定一棵有标号的树边上的标号表示摘去叶的顺序。 (摘去一个叶子相应去掉一条边 )
第一次摘掉②，③为②相邻的顶点，
得到序列的第一个数 3
以此类推，得到序列 31551,长度为 7－ 2 = 5
这是由树形成序列的过程。
1.4模型转换
由序列形成树的过程：
由序列 31551得到一个新序列 111233455567
生成的过程是首先将 31551排序得到 11355，
因为序列 31551的长度为 5，得到按升序排序的序列 1234567，序列的长度为 5+2(即 n+2)，
然后将 11355按照大小插入到序列 1234567中，
得到 111233455567
然后将两个序列排在一起 31551111233455567
1.4模型转换
31551
111233455567
② — ③ 1551
1113455567
① — ③ 551
11455567
④ — ⑤ 51
115567
⑤ — ⑥ 1
1157
① — ⑤
17
第一步推导：将上下两个序列同时去掉上行序列的第一个元素 3(用 黄色 表示 )，去掉下行序列的第一个无重复的元素 2(用 红色表示 )。生成一条边 (② — ③ )。
依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。
1.4模型转换
上述算法描述：
给定序列 b=(b1b2…b n-2) 设 a=(123… n-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=(b1b2…b n-2),反之，由 b可得 T。 即 f,T→b 是一一对应。
由序列确定的长边过程是不会形成回路的。因任意长出的边 (u,v) 若属于某回路，此回路中必有一条最早生成的边，不妨就设为 (u,v),
必须使 u,v都在长出的边中重复出现，但照算法
u,v之一从下行消失，不妨设为 u,从而不可能再生成与 u有关的边了，故由 ( )得到的边必构成一个 n个顶点的树。
ba’
1.4模型转换
证 由一棵 n个顶点的树可得到一个长度为 n－ 2的序列，且不同的树对应的序列不同 *，因此 | T |≤ n 。
*对 n用归纳法可证
反之，由一个长度为 n－ 2的序列 (每个元素为 1~ n 的一个整数 )，可得到一棵树，
且不同的序列对应的树是不同的，因此
n ≤| T |
| T | = n #
n-2
n-2
n-2
1.5全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列 无重复无遗漏 地枚举出来。
全排列的生成算法
1.5全排列的生成算法这里介绍全排列算法四种：
(A)字典序法
(B)递增进位制数法
(C)递减 进位制数法
(D)邻位对换法
1.5.1字典序法对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。
1.5.1字典序法
[例 ]字符集 {1,2,3},较小的数字较先,这样按字典序生成的全排列是,
123,132,213,231,312,321。
※※ 一个全排列可看做一个字符串，字符串可有 前缀,后缀 。
1.5.1字典序法
1） 生成给定全排列的下一个排列所谓 一个的下一个 就是 这一个 与下一个 之间 没有其他的 。这就要求这一个与下一个有尽可能 长 的共同前缀,也即变化限制在尽可能 短 的 后缀 上。
1.5.1字典序法
[例 ] 839647521是 1--9的排列。 1— 9
的排列最前面的是 123456789，最后面的是 987654321，从右向左扫描若都是增的，就到 了 987654321，也就没有下一个了。否则找出第一次出现下降的位置 。
1.5.1字典序法求 839647521的下一个排列
7 5 2 1
4＜ 7<54>2>1
在后缀 7521中找出比 4大的数 7 5找出其中比 4大的最小数 5
5
4,5 对换
8396 7 214
后缀变为 7421将此后缀翻转
12 4 7
接上前缀 83965得到 839651247
即 839647521的下一个。
[例 ]
为后缀大于 4的用 橙 色表示小于 4的用 绿 色表示找出比右边数字小的第一个数 4
1.5.1字典序法在 [1,n]的全排列中,n n-1 … 321
是最后一个排列,其中介数是 (n-1,
n-2,...,3,2,1)其序号为 n-1∑k× k!
k=1
另一方面可直接看出其序号为 n!-1
n-1 n-1
于是 n!-1= ∑k× k! 即 n!=∑k× k! +1
k=1 k=1
1.5.1字典序法一般而言，设 P是 [1,n]的一个全排列。
P=P1P2…P n=P1P2…P j-1PjPj+1…P k-1PkPk+1…P n
j=max{i|Pi<Pi+1},k=max{i|Pi>Pj}
对换 Pj,Pk,将 Pj+1…P k-1PjPk+1…P n翻转，
P’= P1P2…P j-1PkPn…P k+1PjPk-1…P j+1即 P的下一个
1.5.1字典序法
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小 的数的个数,4的右边 比 4小 的数的个数3,7的右边 比 7小 的数的个数,5的右边 比 5小 的数的个数1,2的右边 比 2小 的数的个数
72642321是计算排列 839647521的序号的中间环节，
我们称之为 中介数 。
※ 这是一个很有用的概念。
1.5.1字典序法一般而言,对于 [1,9]的全排列中介数首位的取值为 0— 8，第 2位的取值为 0— 7，以此类推，第 8位的取值为 0,1。从而序号可表示为：
n-1∑ k
i(n-i)!
i=1
ki,Pi的右边比 Pi小的数的个数
i=1,2,…,n-1
1.5.1字典序法由中介数推出排列的算法
[例 ] 由 72642321推算出 839647521
方法 1,P1 P2 P3 P4 P5 P6 P7 P8 P9_ _ _ _ _ _ _ _ _
P1=8
8
→7+1=82+1=3 → P2=3
3
6+1=7，但 3已在 P3左边出现，
↑
7+1=8，但 8已在 P3左边出现，
↑
8+1=9 → P3=9
9
4+1=5，但 已经在 P4左边出现，
5+1=6 → P4=6
6
，但 已经在 5左边出现，
3+1=4 =4
4
3+1=4，但 3,4已经在 P6左边出现，
4+1+1=6，但 6已经在 P6左边出现，
6+1=7 → P6=7
7
，但 已经在 7左边出现，
4，但 4已经在 P7左边出现，
4+1=5 7=5
5
1+1=2 → P8=2
→ P9=1
2 1
这个过程比较麻烦 (这酝酿着改进的可能 )，
该算法从左到右依次推出 P1,P2,…,P 9。
下述算法依次定出 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 的位置
1
● ● ● ● ● ● ● ●
2
2
● ● ● ● ● ● ● 3
3
● 4
4
● ● ● 5
5
● ● ● ●
6
6
● ●
7
7
● ●
8
8
9
9
由 72642321推算出 839647521
1.5.1字典序法方法 2-2：
已定出上标‘ ● ’，找左起第一个 0，下标‘ __’
由 72642321推算出 839647521
●72642321-11111111=61531210
_ _ _ _ _ _ _ _ 12
● ● ● ●61531210 0 5042010
3
● ● ● ●
50420100 10000000=40420100
4
● ● ● ● ●
40420100 - 0 000 =3 31 00
5
● ● ● ● ● ● ● ●
30310100 2 200000
6
● ● ● ● ● ● ● ● ● ●
20200000 10100000=10100000
7
● ● ● ● ● ● ● ● ●● ● ●
10100000 -10100000= 0000000
8
● ● ● ●● ● ●00000000
9
以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数 →进位链（中介数的后继） →递增进位制数
1.5.2递增进位制数法
1)由排列求中介数在 字典序法 中，中介数的各位是由排列数的 位 决定的,中介数位的下标与排列的位的下标一致。
在 递增进位制数法 中，中介数的各位是由排列中的 数字 决定的。即中介数中各位的下标与排列中的数字 (2— n)一致。
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≤ k n-1 ≤1
m2=3m3+kn-2,0≤ k n-2 ≤2
…………….
mn-2=(n-1)mn-1+k2,0≤ k 2 ≤n -2
mn-1=k1,0≤ k 1 ≤n -1
p1p2… pn←→ (k1k2… kn-1)↑ ←→ m
1.5.2递增进位制数法在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。
为方便起见，令 ai+1=kn-I,i=1,2,…,n -1
(k1k2…k n-1)↑=(anan-1…a 2)↑
ai,i的右边比 i小的数字的个数
1.5.2递增进位制数法在这样的定义下，有
839647521←→ (67342221)↑
(67342221)↑+1=(67342300)↑
←→ 849617523
6× 8+7)× 7+3)× 6+4)× 5+2)× 4+2)× 3+2)× 2+1
=279905
1.5.2递增进位制数法由 (anan-1… a2)↑ 求 p1p2… pn。
从大到小求出 n,n-1,…,2,1 的位置
_,.,_ n _ _ …_
an个空格
n的右边有 an个空格。
n-1的右边有 an-1个空格。
…………
2的右边有 a2个空格。
最后一个空格就是 1的位置。
\______ ______/V
1.5.2递增进位制数法
_ _ _ _ _ _ _ _ _ 6 7 3 4 2 2 2 1
↓↓↓↓↓↓↓↓a
9 a8 a7 a6 a5 a4 a3 a2
★
\__________ __________/V
6个空格
9
★
\______________ ______________/V
7个空格
8
★ ★ ★ ★ ★ ★
\____ ____/V
3个空格
76 543 1
\________ ________/V
4个空格
\__ __/V
2个空格
1个空格序号
nm=∑a
k(k-1)!
k=2
2
1.5.3递减进位制数法在递增进位制数法中，中介数的最低位是逢 2进 1，进位频繁，这是一个缺点。
把递增进位制数翻转,就得到 递减进位制数 。
(anan-1…a 2)↑→(a2a3…a n-1an)↓
839647521→ (12224376)↓n n
m=∑akn!/k!=n!∑ak/k!
k=2 k=2(12224376)↓
=1× 3+2)× 4+2)× 5+2)× 6+4)× 7+3)× 8+7)× 9+6
=340989
※※ 求下一个排列十分容易
1.5.4邻位对换法递减进位制数法的中介数进位不频繁，
求下一个排列在不进位的情况下很容易。
这就启发我们，能不能设计一种算法，
下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左,而邻位对换法的换位是双向的 。
1.5.4邻位对换法这个算法可描述如下：
对 1— n-1的每一个 偶 排列,n从右到左 插入 n个空档 (包括两端 )，生成 1— n的 n 个排列。
对 1— n-1的每一个 奇 排列,n从左到右 插入 n个空档，生成 1— n的 n个排列。
对 [2,n]的每个数字都是如此。
1.5.4邻位对换法
[例 ] 839647521→ 836947521●→
[解 ]
2的右边有 1个数字 (奇数 )比 2小,2上加一个点。
●●
3的右边有 2个数字 偶数 比 3小,3上不加点。4的右边有 2个数字 (偶数 )比 4小,4上不加点。5的右边有 个数字 偶数 比 5小,5上不加点。6的右边有 个数字 偶数 比 6小,6上不加点。7的右边有 3个数字 奇数 比 7小,7上加一个点。8的右边有 7个数字 奇数 比 8小,8上加一个点。1— 8上共有 3个 (奇数 )点,9上箭头向右。
P= 839647521→ ( )↓
b2 b3 b4 b5 b6 b7 b8 b9
1 0 1 2 1 3 7 2
2上箭头向左,2右边有 1个数字比 2小,b2=13上箭头向右,3左边有 0个数字比 3小,b3=04上箭头向右,4左边有 1个数字比 4小,4=15上箭头向右,5左边有 2个数字比 5小,5=26上箭头向右,6左边有 个数字比 6小,67上箭头向左,7右边有 3个数字比 7小,7=38上箭头向左,8右边有 7个数字比 8小,8=79上箭头向右,9左边有 个数字比 9小,9839647521的中介数为 10121372
←→→→→→→←
1.5.4邻位对换法
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
1.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奇 →5
1.5.4邻位对换法序号
=1·3+0)·4+1)·5+2)·6+1)·7+3)·8+7)·9+2
=203393←→ (10121372)↓
1.5.4邻位对换法
8 3 9 6 4 7 5 2 1
字典序法递增进位制法递减进位制法邻位对换法下一个 839651247 849617523 893647521 836947521
中介数 72642321 ↑ 6 7 342221 ↑ 122243 7 6 ↓ 10121372 ↓
序 号 297191 279905 340989 203393
1.6组合的生成
设从 [1,n]中取 r元的组合全体为 C(n,r).
C1C2…C r? C(n,r).不妨设 C1＜ C2＜ … ＜ Cr
i≤Ci≤(n－ r+i),i=1,2,…,r
令 j=max{i|Ci＜ n－ r+i}.
则 C1C2…C r的下一个组合为
C1C2…C j-1(Cj+1)(Cj+2)…(C j+r－ j+1)
这等于给 C(n,r)的元素建立了 字典序 。
12… r的序号为 0,n-r+1 n-r+2…n 的序号为 ( )－ 1
______ ______
n
r
1.6组合的生成
例 在 C(10,4)中 4679的序号是
首位小于 4的组合的个数；首位是 4，第 2
位小于 6的组合的个数；前 2位是 46，第 3
位小于 7的组合的个数；前 3位是 467，第
4位小于 9的组合的个数之和。
反之，也可以由序号求组合。
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}
求并的有序集
__
×
__
×
__ __
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-r
r-1
1.6组合的生成
②以 0结尾,r个 10
与 n-2r个 0的排列 r+n-2r =
n-r
这样的排列有 ( )个
( )+( ) = ( )
f(a1a2…a r) = b1b2…b r
n-rr
n-r n-r n-r+1r-1 r r
1.6组合的生成
解法２
任给 a1a2…a r? C’(n,r),a1 ＜ a2 ＜ … ＜ ar
令 f,a1a2…a r→b1b2…b r
bi = ai-i+1,i= 1,2,…,r.
1≤b1 ＜ b2 ＜ … ＜ br ≤ n-r+1,
b1b2…b r? C(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,r)+C(n,r-1)
不含“１” 至少含一个“１”
(n-1+r)!————
r!(n-1)!n+r-1
r
r个相同的球 /\
——————— ————————／ \0…010…01…10…0
\ /———— ————\/
n-1个相同的盒壁
1.7可重组合
另证 设 a1a2…a r? C(n,r)
1≤a1≤a2 ≤… ≤ar≤n,
令 C(n,r)上的 f,使得 bi=ai+i-1,i=1,2,…,r.
则 b1b2…b r满足 1≤b1＜ b2＜ … ＜ br≤n+r-1
b1b2…b r? C(n+r-1,r)
f,a1a2…a r→b1b2…b r
显然 f是单射,f,b1b2…b r→a1a2…a r
－
－
-1
1.7可重组合
ai=bi-i+1,i=1,2,…,r.
a1a2…a r? C(n,r)
f是单射 C(n,r)≤C(n+r-1,r)
f 是单射 C(n,r)≥C(n+r-1,r)
∴ C(n,r)=C(n+r-1,r)
第二个证明可说一种“拉伸压缩”技巧。
不可谓不巧妙。但仍不如第一证明来的明快，由此可见 组合证明 的功效。
—
—
—-1
—
1.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]取 a1,a2,…,a r.设 1≤a1＜ a2＜ … ＜ ar≤n,对取法分类,a1=1,有 C(n-1,r-1)种方案
a1>1,有 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)点，都满足此递推式
0<r≤n,n<0<r
C(n,r)= 1,r = 0
0,0≤n<r,r<0≤n
n<0且 r<0
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
[n]r——
r!
1.8若干等式及其组合意义
3.( )+( )+( )+…+( )=( ) (1.7.3)
[1]可从 (7.2)推论，也可做一下组合证明从 [1,n+r+1]取 a1a2…a nan+1，
设 a1＜ a2＜ … ＜ an ＜ an+1，
可按 a1的取值分类,a1=1,2,3,…r,r+1.
a1=1,a2…a n+1取自 [2,n+r+1] 有 ( )种取法
n n+1 n+2 n+r n+r+1
n n n n n
n+r
n2 取自 3 有 种取法
n+r-1
n… … …r,a2…a n+1取自 [r+1,n+r+1] 有 ( )种取法
n+1
n+1,a2…a n+1取自 [r 2,n+r+1] 有 ( )种取法nn
也可看做按含 1不含 1，含 2不含 2,…,
含 r不含 r的不断分类
1.8若干等式及其组合意义
[2]从 (0,0)到 (n+1,r),过且仅过一条带箭头的边,而过这些边的路径有 (从下到上 )
( ),( ),…,( )
故有,( )+( )+( )+…+( )=( )
n n+1 n+rn n n
n n+1 n+2 n+r n+r+1
n n n n n
r (n+1,r)
..
.
(0,0) n n+1
1.8若干等式及其组合意义
[3] 可重组合,
[1,n+2]的 C(n+2,r)模型 ( )
不含 1,含 1个 1,含 2个 1,…,含 r个 1
C( ),C( ),C( ),…,C( )
( ),( ),( ),…,( )
n+r+1r
n+1 n+1 n+1 n+1r r-1 r-2 0
n+r n+r-1 n+r-2 nr r-1 r-2 0
1.8若干等式及其组合意义
4,( )( )=( )( ) (1.7.4)
①选政治局,再选常委,n个中央委员选出 l
名政治局委员,再从其中选出 r名常委
②选常委,再选非常委政治局委员
两种选法都 无遗漏,无重复 地给出可能的方案，应该相等。
n l n n-r
l r r l-r
1.8若干等式及其组合意义
5,( )+( )+…+( )=2,m≤0,(1.7.5)
证 1(x+y)=∑ ( )x y,令 x=y=1,得 (1.7.5)
组合证 1 [1,m]的所有方案,每一子集都可取 k[1,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 m
0 1 m
m k m-km m
kk=0
m
m
m m m m m m
0 1 2 m-2 m-1 m
1.8若干等式及其组合意义
6,( )-( )+( )-… ± ( )=0 (1.7.6)
证 1
在 (x+y)=∑ ( )x y 中令 x=1,y=-1即得,
n n n n
0 1 2 n
n n-k knkn
k=0
1.8若干等式及其组合意义
证 2 在 [1,n]的所有组合中,
含 1的组合 ←→ 不含 1的组合,有 1— 1对应关系。在任一含 1组合及与之对应的不含
1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数阁元的组合做成另一集。
此二集的元数相等。
∑ ( )=∑( )n ni i
i奇 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
r 0 r 1 r-1 r 0
m n
r-l l
m+n m n
r r-l l
P(m-r,r) (m+n-r,r)
(m-r+l,r-l) l=0,1,2,…,r
Q(m,0)
r
l=0
1.8若干等式及其组合意义
李善兰 (1811— 1882），清代数学家
李善兰恒等式：
∑( )( )( )=( )( )k l n+k+l-j n+k n+lj j k+l k l
j≥0
证,利用 Vandermonde恒等式及
( )( )=( )( )=( )( )
(接下页 )
n v n n-p n n-p
v p p n-v p v-p
1.8若干等式及其组合意义有 ∑( )( )( )
=∑( )( )(∑( )( ) )
=∑( )∑( )( )( )
=∑( )∑( )( )( )
=∑( )( )( )
=∑( )( )( )
=( )∑( )( )
=( )( )
k l n+k+l-j
j j k+l
k l n+k l-j
j j k+v l-v
n+k k l l-j
k+v j j l-v
n+k k l v
k+v j v l
n+k l k+v
k+v v kn+k n l
k n-v v
n+k n l
k n-v v
n+k n+l
k l
j≥0
j≥0 v≥j
v≥0 j≥0
v≥0 j≥0
v≥0
v≥0
v≥0
1.8若干等式及其组合意义
8,在 7.中令 r=m≤n,再将 ( )换成 ( )
得 ( )=( )( )+( )( )+…+( )( )
m m
k m-k
m+n m n m n m n
m 0 0 1 1 m m
1.9应用举例
例 某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干钥匙。须４人到场，所备钥匙才能开锁。问①至少有多少把不同的钥匙？②
每人至少持几把钥匙？
解 ①每３人至少缺１把钥匙，且每３人所缺钥匙不同。故至少共有 ( )=35把不同的钥匙。
73
1.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种状态，
而且服从 Bose-Einstein分布，即同能级的质点可以处于相同的状态，问系统有几种不同的状态？（或图像）
B)若能级为 kE0的质点可有 2(k +1)种状态，
而且服从 Fermi-Dirac分布，即不允许同能级的两个质点有相同状态，问系统有几种不同状态？（或图像）
2
2
1.9应用举例
解 能级 k 0 1 2 3 4
A) k +1 1 2 5 10 17 状
B)2(k +1) 2 4 10 20 34 态
2
2
能量分布 0,0,0,4 0,0,1,3 0,0,2,2
A) 1·1·1·17 1·1·2·10 1·1·C(5,2)
B) C(2,3)·34 C(2,2)·4·20 C(2,2)·C(10,2)
能量分布 0,1,1,2 1,1,1,1
A) 1·C(2,2)·5 C(2,4) 72
B) 2C(4,2)·10 C(4,4) 246
—
— —
1.9应用举例
例
3个相同的质点分布在 2个相同的势阱里，这 3个质点的总能量为 3E0,每个质点的能级为 kE0,k=0,1,2,3,能级为 kE0的质点有 2(k +1)种状态，服从 Fermi-Dirac
分布即同一势阱中的质点不可处于同一状态，问系统有几种状态？
2
1.9应用举例
0,0|3 0|0,3 0,1|2 0|1,2 1|0,2
1·1·20 2·2·20 2·4·10 80 80
=20 =80 =80
1,1|1 111|φ 0,0,3|φ 0,1,2|φ
C(4,2)·4 ( ) 1·1·20 2·4·10
=24 =4 =20 =80
43
20·2+80·5+24+4=468
解,
1.9应用举例
例设 n位长能纠 r个错的码字的个数为 M，
则 2 /∑( )≤M≤2 /∑( )
n位长的 0-1字符串共有 2 个。但不能每个串都设为码字，否则市区纠错能力。
n n
k nk
n2r
k=0
r
k=0
1.9应用举例
Hamming距离 设 a=a1a2…a n,b=b1b2…b n是
n位串。则 a,b的 Hamming距离为
d(a,b)=∑|ai-bi|
即对应位不同的位的个数。
d(a,b)+d(b,c)≥d(a,c)
d(a,b)=∑|ai-bi|,d(b,c)=∑|bi-ci|
d(a,b)+d(b,c)=∑|ai-bi|+∑|bi-ci|
≥∑|(ai-bi)+(bi-ci)|=d(a,c)
n
i=1
a
r
上图表示以 a为球心,r位半径的球体中的串都作为 a处理
1.9应用举例
若规定 a是码字，收到 a’有 d(a,a’)≤r即将 a’
当作 a发生最多 r个错误
此时两个码字 a,b应满足 d(a,b)≥2r+1当作
a处理的串有 ( )+( )+…+( ) 个
故 M∑( )≤2
另一方面任一串与最近的码字的距离不大于 2r,否则此串本身可作为一新的码字，即以 2r位半径的各码字为球心，应当使任一串落入某球内，故 M∑( )≥2
n n n0 1 r
nk
nk
n
n
r
k=0
2r
k=0
1.9应用举例
例 脱氧核糖核酸 (DNA)的分子由 A(腺嘌呤 ),G(鸟嘌呤 ),C(胞嘧啶 )和 T(胸腺嘧啶 )4种碱基核糖核苷酸，以不同数目和种类排列成两条多核苷酸单链，这两条单链之间通过氢键把配对的碱基连接起来，形成双螺旋结构。连接过程总是 A和 T配对,G和 C
配对。显然长度为 n的核苷酸链共有 4 种不同方式。
n
1.9应用举例
生物遗传信息是由 DNA分子中 4个碱基核苷酸象电报密码似的以不同的排列顺序记录下来，它载着人类的全部基因或全部遗传信息。所谓基因就是 DNA上一小段,平均长度为 900-1500个碱基对。人的 DNA约有 3× 10 碱基对。
核糖核酸 (RNA)也是一种遗传物质，它是由 A,G,C,U(尿嘧啶 )4种碱基核苷酸排列而成的多核苷酸单链。
9
1.9应用举例
通过基因将它的遗传信息传递给 RNA,然后再传给蛋白质来表现其功能。
(1)蛋白质分子中有 20种氨基酸，在 RNA
中以一定顺序相连的 3个核苷酸决定 1种氨基酸，三联体遗传密码有 4 =64个排列方式。它保证了 20种氨基酸密码的需要。
(2)例如 RNA链,CCGGUCCGAAAG
酶将它分解成为 G片断 (即利用 G将
RNA分解 )。 CCG,G,UCCG,AAAG.
3
1.9应用举例
显然有 4!=24种不同的 RNA链有与此相同的 G片段。
若利用 U,C酶将上述的 RNA链分解成 U,C
片段,C,C,GGU,C,C,GAAAG
由于 GAAAG片段只能在最后出现，而且
C出现 4次，故有 C(5,4)=5种不同的核苷酸链，它的 U,C片段是上述的 C,C,C,C,GGU,
GAAAG,它们是
1.9应用举例
CCCCGGUGAAAG
CCCGGUCGAAAG
CCGGUCCGAAAG
CGGUCCCGAAAG
GGUCCCCGAAAG
(接上页 )
据传说，大禹在 4000多年前就观察到神龟背上的幻方 …...
前言幻方可以看作是一个 3阶方阵，其元素是 1
到 9的正整数，
每行、每列以及两条对角线的和都是 15。
5
1
9
3 7
24
8 6
前言贾宪 北宋数学家（约 11世纪） 著有《黄帝九章细草》、《算法斅古集》斅 音“笑（“古算法导引”）都已失传。杨辉著《详解九章算法》（ 1261年）中曾引贾宪的“开方作法本源”
图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早 600
年，后者比霍纳（ William Geoge Horner，
1786— 1837） 的方法（ 1819年）早 770年。
前言
1666年莱布尼兹所著《组合学论文》
一书问世，这是组合数学的第一部专著。
书中首次使用了组合论（ Combinatorics）
一词。
前言组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。
前言
本学期主要讲组合分析（计数和枚举）
以及组合优化的一部分（线性规划的单纯形解法）。
组合分析是组合算法的基础。
前言组合数学经常使用的方法并不高深复杂。最主要的方法是 计数时的合理分类 和 组合模型的转换。
但是，要学好组合数学并非易事，
既需要一定的数学修养，也要进行相当的训练。
第一章 排列组合
1.1 加法法则与乘法法则
1.1 加法法则与乘法法则
[ 加法法则 ] 设事件 A有 m种产生方式，
事件 B有 n种产生方式，则事件 A或 B之一有 m+n种产生方式。
集合论语言：
若 |A| = m,|B| = n,A?B =?,则
|A?B| = 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,
A?B = {(a,b) | a?A,b? B},
则 |A? B| = m ·n 。
1.1 加法法则与乘法法则
[例 ] 某种字符串由两个字符组成，第一个字符可选自 {a,b,c,d,e},第二个字符可选自 {1,2,3}，则这种字符串共有 5?3
= 15 个。
[例 ] 从 A到 B有三条道路，从 B到 C有两条道路，则从 A经 B到 C有 3?2=6 条道路。
1.1 加法法则与乘法法则
例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、
橙、黄，条纹色可选黑、白，则共有 4?2
= 8种着色方案。
若此例改成底色和条纹都用红、蓝、橙、
黄四种颜色的话，则，方案数就不是 4?
4 = 16,而只有 4? 3 = 12 种。
在乘法法则中要注意事件 A 和 事件 B 的相互独立性。
1.1 加法法则与乘法法则例 1)求小于 10000的含 1的正整数的个数
2)求小于 10000的含 0的正整数的个数
1)小于 10000的不含 1的正整数可看做 4位数,
但 0000除外,
故有 9× 9× 9× 9－ 1＝ 6560个,
含 1的有,9999－ 6560=3439个另,全部 4位数有 10 个,不含 1的四位数有 9 个,
含 1的 4位数为两个的差,10 － 9 = 3439个4 4
4 4
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个
2
3 4
2 3 4 5
1.2排列与组合定义 从 n个不同的元素中，取 r个不重复的元素，按次序排列，称为从 n个中取
r个的 无重排列 。排列的全体组成的集合用 P(n,r)表示。排列的个数用 P(n,r)表示。当 r=n时称为 全排列 。一般不说可重即无重。可重排列的相应记号为
-P(n,r),P(n,r)。
1.2排列与组合定义从 n个不同元素中取 r个不重复的元素组成一个子集，而不考虑其元素的顺序，
称为从 n个中取 r个的 无重组合 。
组合的全体组成的集合用 C(n,r)表示，组合的个数用 C(n,r)表示，对应于可重组合-
有记号 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)
有时也用 [n]r记 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!=[n]r/r!=( )=
易见 P(n,r)=n
nr
r
n!———
r!(n-r)!
若球不同，盒子相同，则是从 个中取 个的 组合 的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有 个标号方案。
故有易见
1.2排列与组合例 有 5本不同的日文书,7本不同的英文书,10本不同的中文书。
1)取 2本不同文字的书；
2)取 2本相同文字的书；
3)任取两本书
1.2排列与组合
5+7+10
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=( )
1.2排列与组合
求 r1个 1,r2个 2,…,rt个 t的排列数，设
r1+r2+…+r t=n,设此排列数为 P(n;r1,r2,…,r t),
对 1,2,…,t分别加下标，得到
P(n； r1,r2,…,r t)·r1!·r2!·… ·rt! = n!
∴ P(n； r1,r2,…,r t)= ———— =( )n!r
1!r2!…r t!
nr
1 r2 … r t
1.2排列与组合
从 n个中取 r个的圆排列的排列数为
P(n,r)/r,2≤r≤n
以 4个元素为例
1
2 4
3
1234
1
2 4
3
2341
1
2 4
3
3412
1
2 4
3
4123
1.2排列与组合
从 n个中取 r个的项链排列的排列数为
P(n,r)/2r,3≤r≤n
项链排列就是说排列的方法和项链一样,
在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。
例 下面两种方式实际上表示的都是 3个元素的同一种排列。
1 1
2 3 3 2
1.2排列与组合例 从 [1,300]中取 3个不同的数，使这
3个数的和能被 3整除，有多少种方案？
解 将 [1,300]分成 3类：
A={i|i≡1(mod 3)}={1,4,7,…,298},
B={i|i≡2(mod 3)}={2,5,8,…,299},
C={i|i≡3(mod 3)}={3,6,9,…,300}.
要满足条件，有四种解法：
1)3个数同属于 A;2)3个数同属于 B
3)3个数同属于 C;4)A,B,C各取一数,
故共有 3C(100,3)+100 =485100+1000000=14851003
1.2排列与组合例 某车站有 6个入口处，每个入口处每次只能进一人，一组 9个人进站的方案有多少？
[解 ]一进站方案表示成,00011001010100
其中,0”表示人，,1”表示门框，其中,0”是不同元，,1”是相同元。给,1” n个门只用 n-1
个门框。任意进站方案可表示成上面 14个元素的一个排列。
1.2排列与组合
[解法 1]标号可产生 5!个 14个元的全排列。
故若设 x为所求方案，则
x·5!=14!
∴x=14!/5!=726485760
1.2排列与组合
[解法 2]在 14个元的排列中先确定,1”
的位置，有 C(14,5)种选择，在确定人的位置，有 9！种选择。
故 C(14,5)·9! 即所求
1.2排列与组合
[解法 3]把全部选择分解成若干步，使每步宜于计算。不妨设 9个人编成 1至 9号。 1号有 6种选择； 2号除可有 1号的所有选择外，
还可（也必须）选择当与 1号同一门时在 1
号的前面还是后面，故 2号有 7种选择； 3号的选择方法同 2号，故共有 8种。
以此类推,9号有 14种选择。
9故所求方案为 [6]
1.3 Stirling近似公式
组合计数的渐进值问题是组合论的一个研究方向。
Stirling公式给出一个求 n!的近似公式，它对从事计算和理论分析都是有意义的。
1.3 Stirling近似公式
1)Wallis公式令 Ik=∫ sin xdx.显然 I0=,I1=1.
k≥2时，
Ik=－ cosxsin x| +∫ (k－ 1)cos xsin xdx
=0+(k－ 1)∫ (1－ sin x)sin xdx
=(k－ 1)(Ik－ 2－ Ik)
k π－
2
k-1 π－ 2
0
π－
2
0π－
2
0
π－
2
0
2 k-2
2 k-2
故
Ik = —— Ik-2 (1-3-1)k-1k
1.3 Stirling近似公式令 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)时,sin x < sin x
因而 I2k+1<I2k<I2k-1,k=1,2,… 。
k+1 k
1.3 Stirling近似公式
由 (1-3-2)
———— < ———— ·— < ————,(2k)!! (2k-1)!! π (2k-2)!!(2k+1)!! (2k)!! 2 (2k-1)!!
1< —————— < —— 1.
π—
2
[—— ] (2k)!!(2k-1)!! 1· ——2k+1
2k+1
2k2 k→∞
1.3 Stirling近似公式
所以
lim =,(2k)!!(2k-1)!! 1· ——2k+1
2[—— ] π—
2k→∞
lim =,(2k)!!(2k)!!(2k)! 1· ——2k+1
2[———— ] π—
2k→∞
lim = 。 (1-10-3)2 (k!)(2k)! 1· ——2k+1
2[—— ] π—
2k→∞
2k 2
1.3 Stirling近似公式
2)stirling公式
y
y=lnx
0 1 2 3 n-1 n x
1.3 Stirling近似公式
令 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)诸点而成的折线围成的面积。
n n n
1 1 1
1 1
2 21
2
1.3 Stirling近似公式
Tn=－ +ln2+…+ln( n－ 1)+－ lnn (1-3-6)1 18 2
Tn是由三部分面积之和构成的。一是曲线
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)
12
12
12
1.3 Stirling近似公式
令 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!)+－ ln n
ln(n!)=1－ bn+ lnn － ln n － lne
∴ n!=e n (－ ) (1-3-8)
0<An－ tn<Tn－ tn=－ 18
n→∞
12
n √
√n n
1-bn√ ne n
12
1.3 Stirling近似公式
令 βn=e,limβn=β.
将 (1-3-8)代入 (1-3-3),整理得
β= 2π,
所以
n! ~ 2πn (－ )
n→∞
1-bn
√
√ ne n
1.4模型转换
,一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。
如我们说 A集合有 n个元素 |A|=n,无非是建立了将 A中元与 [1,n]元一一对应的关系。
在组合计数时往往借助于一一对应实现模型转换。
比如要对 A集合计数，但直接计数有困难，
于是可设法构造一易于计数的 B,使得 A
与 B一一对应。
1.4模型转换
例 简单格路问题 |(0,0)→(m,n)|=( )
从 (0,0)点出发沿 x轴或 y轴的正方向每步走一个单位，最终走到 (m,n)点，有多少条路径？
m+nm
y
(m,n)
..
.
0,,,x
1.4模型转换
无论怎样走法，在 x方向上总共走 m步，
在 y方向上总共走 n步。若用一个 x表示 x
方向上的一步，一个字母 y表示 y方向上的一步。
则 (0,0)→(m,n)的每一条路径可表示为 m
个 x与 n个 y的一个有重排列。将每一个有重排列的 x与 y分别编号，可得 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)
设 c≥a,d≥b,则由 (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模型转换
例 在上例的基础上若设 m<n,求 (0,1)
点到 (m,n)点不接触对角线 x=y的格路的数目 (“接触”包括“穿过” )
从 (0,1)点到 (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模型转换
故所求格路数为 ( )－ ( ) = —
—— － ——— = ———— ( — － — )
= —— ( )=(1－ — )( )
= —— ( )
m+n-1 m+n-1m m-1
(m+n-1)! (m+n-1)! (m+n-1)! 1 1
m!(n-1)! (m-1)!n! (m-1)!(n-1)! m n
m+n-1 m+n-1m mn-m m
n n
m+n-1 m n-m
n
1.4模型转换
若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得 x－ y=1，
(0,0)关于 x－ y=1的对称点为 (1,-1).
所求格路数为 ( )－ ( )
= —— － ———— = ——— ( )
m+n m+nm m-1
(m+n)! (m+n)! n+1-m
m!n! (m-1)!(n+1)! n+1
m+n m
格路也是一种常用模型
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
|
H
n=1甲烷 n=2 乙烷 n=3 丙烷
1.4模型转换
H
|
H — C — H
|
H — C — H
|
H — C — H
|
H — C — H
|
H
H
| H
H — C H
| |
H — C — C — H
| |
H — C H
| H
H
n=4 丁烷 n=4异丁烷这说明对应 CnH2n+2的枝链是有 3n+2个顶点的一棵树，其中 n个顶点与之关联的边数为 4；其它 2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物 CnH2n+2.
1.4模型转换
例 在 100名选手之间进行淘汰赛 (即一场的比赛结果，失败者退出比赛 ),最后产生一名冠军，问要举行几场比赛？
解 一种常见的思路是按轮计场，费事。
另一种思路是淘汰的选手与比赛 (按场计 )
集一一对应。 99场比赛。
1.4模型转换
例 (Cayley定理 ) n个有标号的顶点的树的数目等于 n 。n-2
生长点不是叶子,每个生长点是 [1,n]中的任一元,有 n种选择。两个顶点的树是唯一的。
1.4模型转换
⑦ ⑥| |
② — ③ — ① — ⑤ — ④
4
1 2 5 3
逐个摘去标号最小的叶子，叶子的相邻顶点 (不是叶子，是内点 )形成一个序列，
序列的长度为 n-2
例 给定一棵有标号的树边上的标号表示摘去叶的顺序。 (摘去一个叶子相应去掉一条边 )
第一次摘掉②，③为②相邻的顶点，
得到序列的第一个数 3
以此类推，得到序列 31551,长度为 7－ 2 = 5
这是由树形成序列的过程。
1.4模型转换
由序列形成树的过程：
由序列 31551得到一个新序列 111233455567
生成的过程是首先将 31551排序得到 11355，
因为序列 31551的长度为 5，得到按升序排序的序列 1234567，序列的长度为 5+2(即 n+2)，
然后将 11355按照大小插入到序列 1234567中，
得到 111233455567
然后将两个序列排在一起 31551111233455567
1.4模型转换
31551
111233455567
② — ③ 1551
1113455567
① — ③ 551
11455567
④ — ⑤ 51
115567
⑤ — ⑥ 1
1157
① — ⑤
17
第一步推导：将上下两个序列同时去掉上行序列的第一个元素 3(用 黄色 表示 )，去掉下行序列的第一个无重复的元素 2(用 红色表示 )。生成一条边 (② — ③ )。
依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。
1.4模型转换
上述算法描述：
给定序列 b=(b1b2…b n-2) 设 a=(123… n-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=(b1b2…b n-2),反之，由 b可得 T。 即 f,T→b 是一一对应。
由序列确定的长边过程是不会形成回路的。因任意长出的边 (u,v) 若属于某回路，此回路中必有一条最早生成的边，不妨就设为 (u,v),
必须使 u,v都在长出的边中重复出现，但照算法
u,v之一从下行消失，不妨设为 u,从而不可能再生成与 u有关的边了，故由 ( )得到的边必构成一个 n个顶点的树。
ba’
1.4模型转换
证 由一棵 n个顶点的树可得到一个长度为 n－ 2的序列，且不同的树对应的序列不同 *，因此 | T |≤ n 。
*对 n用归纳法可证
反之，由一个长度为 n－ 2的序列 (每个元素为 1~ n 的一个整数 )，可得到一棵树，
且不同的序列对应的树是不同的，因此
n ≤| T |
| T | = n #
n-2
n-2
n-2
1.5全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列 无重复无遗漏 地枚举出来。
全排列的生成算法
1.5全排列的生成算法这里介绍全排列算法四种：
(A)字典序法
(B)递增进位制数法
(C)递减 进位制数法
(D)邻位对换法
1.5.1字典序法对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。
1.5.1字典序法
[例 ]字符集 {1,2,3},较小的数字较先,这样按字典序生成的全排列是,
123,132,213,231,312,321。
※※ 一个全排列可看做一个字符串，字符串可有 前缀,后缀 。
1.5.1字典序法
1） 生成给定全排列的下一个排列所谓 一个的下一个 就是 这一个 与下一个 之间 没有其他的 。这就要求这一个与下一个有尽可能 长 的共同前缀,也即变化限制在尽可能 短 的 后缀 上。
1.5.1字典序法
[例 ] 839647521是 1--9的排列。 1— 9
的排列最前面的是 123456789，最后面的是 987654321，从右向左扫描若都是增的，就到 了 987654321，也就没有下一个了。否则找出第一次出现下降的位置 。
1.5.1字典序法求 839647521的下一个排列
7 5 2 1
4＜ 7<54>2>1
在后缀 7521中找出比 4大的数 7 5找出其中比 4大的最小数 5
5
4,5 对换
8396 7 214
后缀变为 7421将此后缀翻转
12 4 7
接上前缀 83965得到 839651247
即 839647521的下一个。
[例 ]
为后缀大于 4的用 橙 色表示小于 4的用 绿 色表示找出比右边数字小的第一个数 4
1.5.1字典序法在 [1,n]的全排列中,n n-1 … 321
是最后一个排列,其中介数是 (n-1,
n-2,...,3,2,1)其序号为 n-1∑k× k!
k=1
另一方面可直接看出其序号为 n!-1
n-1 n-1
于是 n!-1= ∑k× k! 即 n!=∑k× k! +1
k=1 k=1
1.5.1字典序法一般而言，设 P是 [1,n]的一个全排列。
P=P1P2…P n=P1P2…P j-1PjPj+1…P k-1PkPk+1…P n
j=max{i|Pi<Pi+1},k=max{i|Pi>Pj}
对换 Pj,Pk,将 Pj+1…P k-1PjPk+1…P n翻转，
P’= P1P2…P j-1PkPn…P k+1PjPk-1…P j+1即 P的下一个
1.5.1字典序法
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小 的数的个数,4的右边 比 4小 的数的个数3,7的右边 比 7小 的数的个数,5的右边 比 5小 的数的个数1,2的右边 比 2小 的数的个数
72642321是计算排列 839647521的序号的中间环节，
我们称之为 中介数 。
※ 这是一个很有用的概念。
1.5.1字典序法一般而言,对于 [1,9]的全排列中介数首位的取值为 0— 8，第 2位的取值为 0— 7，以此类推，第 8位的取值为 0,1。从而序号可表示为：
n-1∑ k
i(n-i)!
i=1
ki,Pi的右边比 Pi小的数的个数
i=1,2,…,n-1
1.5.1字典序法由中介数推出排列的算法
[例 ] 由 72642321推算出 839647521
方法 1,P1 P2 P3 P4 P5 P6 P7 P8 P9_ _ _ _ _ _ _ _ _
P1=8
8
→7+1=82+1=3 → P2=3
3
6+1=7，但 3已在 P3左边出现，
↑
7+1=8，但 8已在 P3左边出现，
↑
8+1=9 → P3=9
9
4+1=5，但 已经在 P4左边出现，
5+1=6 → P4=6
6
，但 已经在 5左边出现，
3+1=4 =4
4
3+1=4，但 3,4已经在 P6左边出现，
4+1+1=6，但 6已经在 P6左边出现，
6+1=7 → P6=7
7
，但 已经在 7左边出现，
4，但 4已经在 P7左边出现，
4+1=5 7=5
5
1+1=2 → P8=2
→ P9=1
2 1
这个过程比较麻烦 (这酝酿着改进的可能 )，
该算法从左到右依次推出 P1,P2,…,P 9。
下述算法依次定出 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 的位置
1
● ● ● ● ● ● ● ●
2
2
● ● ● ● ● ● ● 3
3
● 4
4
● ● ● 5
5
● ● ● ●
6
6
● ●
7
7
● ●
8
8
9
9
由 72642321推算出 839647521
1.5.1字典序法方法 2-2：
已定出上标‘ ● ’，找左起第一个 0，下标‘ __’
由 72642321推算出 839647521
●72642321-11111111=61531210
_ _ _ _ _ _ _ _ 12
● ● ● ●61531210 0 5042010
3
● ● ● ●
50420100 10000000=40420100
4
● ● ● ● ●
40420100 - 0 000 =3 31 00
5
● ● ● ● ● ● ● ●
30310100 2 200000
6
● ● ● ● ● ● ● ● ● ●
20200000 10100000=10100000
7
● ● ● ● ● ● ● ● ●● ● ●
10100000 -10100000= 0000000
8
● ● ● ●● ● ●00000000
9
以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数 →进位链（中介数的后继） →递增进位制数
1.5.2递增进位制数法
1)由排列求中介数在 字典序法 中，中介数的各位是由排列数的 位 决定的,中介数位的下标与排列的位的下标一致。
在 递增进位制数法 中，中介数的各位是由排列中的 数字 决定的。即中介数中各位的下标与排列中的数字 (2— n)一致。
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≤ k n-1 ≤1
m2=3m3+kn-2,0≤ k n-2 ≤2
…………….
mn-2=(n-1)mn-1+k2,0≤ k 2 ≤n -2
mn-1=k1,0≤ k 1 ≤n -1
p1p2… pn←→ (k1k2… kn-1)↑ ←→ m
1.5.2递增进位制数法在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。
为方便起见，令 ai+1=kn-I,i=1,2,…,n -1
(k1k2…k n-1)↑=(anan-1…a 2)↑
ai,i的右边比 i小的数字的个数
1.5.2递增进位制数法在这样的定义下，有
839647521←→ (67342221)↑
(67342221)↑+1=(67342300)↑
←→ 849617523
6× 8+7)× 7+3)× 6+4)× 5+2)× 4+2)× 3+2)× 2+1
=279905
1.5.2递增进位制数法由 (anan-1… a2)↑ 求 p1p2… pn。
从大到小求出 n,n-1,…,2,1 的位置
_,.,_ n _ _ …_
an个空格
n的右边有 an个空格。
n-1的右边有 an-1个空格。
…………
2的右边有 a2个空格。
最后一个空格就是 1的位置。
\______ ______/V
1.5.2递增进位制数法
_ _ _ _ _ _ _ _ _ 6 7 3 4 2 2 2 1
↓↓↓↓↓↓↓↓a
9 a8 a7 a6 a5 a4 a3 a2
★
\__________ __________/V
6个空格
9
★
\______________ ______________/V
7个空格
8
★ ★ ★ ★ ★ ★
\____ ____/V
3个空格
76 543 1
\________ ________/V
4个空格
\__ __/V
2个空格
1个空格序号
nm=∑a
k(k-1)!
k=2
2
1.5.3递减进位制数法在递增进位制数法中，中介数的最低位是逢 2进 1，进位频繁，这是一个缺点。
把递增进位制数翻转,就得到 递减进位制数 。
(anan-1…a 2)↑→(a2a3…a n-1an)↓
839647521→ (12224376)↓n n
m=∑akn!/k!=n!∑ak/k!
k=2 k=2(12224376)↓
=1× 3+2)× 4+2)× 5+2)× 6+4)× 7+3)× 8+7)× 9+6
=340989
※※ 求下一个排列十分容易
1.5.4邻位对换法递减进位制数法的中介数进位不频繁，
求下一个排列在不进位的情况下很容易。
这就启发我们，能不能设计一种算法，
下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左,而邻位对换法的换位是双向的 。
1.5.4邻位对换法这个算法可描述如下：
对 1— n-1的每一个 偶 排列,n从右到左 插入 n个空档 (包括两端 )，生成 1— n的 n 个排列。
对 1— n-1的每一个 奇 排列,n从左到右 插入 n个空档，生成 1— n的 n个排列。
对 [2,n]的每个数字都是如此。
1.5.4邻位对换法
[例 ] 839647521→ 836947521●→
[解 ]
2的右边有 1个数字 (奇数 )比 2小,2上加一个点。
●●
3的右边有 2个数字 偶数 比 3小,3上不加点。4的右边有 2个数字 (偶数 )比 4小,4上不加点。5的右边有 个数字 偶数 比 5小,5上不加点。6的右边有 个数字 偶数 比 6小,6上不加点。7的右边有 3个数字 奇数 比 7小,7上加一个点。8的右边有 7个数字 奇数 比 8小,8上加一个点。1— 8上共有 3个 (奇数 )点,9上箭头向右。
P= 839647521→ ( )↓
b2 b3 b4 b5 b6 b7 b8 b9
1 0 1 2 1 3 7 2
2上箭头向左,2右边有 1个数字比 2小,b2=13上箭头向右,3左边有 0个数字比 3小,b3=04上箭头向右,4左边有 1个数字比 4小,4=15上箭头向右,5左边有 2个数字比 5小,5=26上箭头向右,6左边有 个数字比 6小,67上箭头向左,7右边有 3个数字比 7小,7=38上箭头向左,8右边有 7个数字比 8小,8=79上箭头向右,9左边有 个数字比 9小,9839647521的中介数为 10121372
←→→→→→→←
1.5.4邻位对换法
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
1.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奇 →5
1.5.4邻位对换法序号
=1·3+0)·4+1)·5+2)·6+1)·7+3)·8+7)·9+2
=203393←→ (10121372)↓
1.5.4邻位对换法
8 3 9 6 4 7 5 2 1
字典序法递增进位制法递减进位制法邻位对换法下一个 839651247 849617523 893647521 836947521
中介数 72642321 ↑ 6 7 342221 ↑ 122243 7 6 ↓ 10121372 ↓
序 号 297191 279905 340989 203393
1.6组合的生成
设从 [1,n]中取 r元的组合全体为 C(n,r).
C1C2…C r? C(n,r).不妨设 C1＜ C2＜ … ＜ Cr
i≤Ci≤(n－ r+i),i=1,2,…,r
令 j=max{i|Ci＜ n－ r+i}.
则 C1C2…C r的下一个组合为
C1C2…C j-1(Cj+1)(Cj+2)…(C j+r－ j+1)
这等于给 C(n,r)的元素建立了 字典序 。
12… r的序号为 0,n-r+1 n-r+2…n 的序号为 ( )－ 1
______ ______
n
r
1.6组合的生成
例 在 C(10,4)中 4679的序号是
首位小于 4的组合的个数；首位是 4，第 2
位小于 6的组合的个数；前 2位是 46，第 3
位小于 7的组合的个数；前 3位是 467，第
4位小于 9的组合的个数之和。
反之，也可以由序号求组合。
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}
求并的有序集
__
×
__
×
__ __
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-r
r-1
1.6组合的生成
②以 0结尾,r个 10
与 n-2r个 0的排列 r+n-2r =
n-r
这样的排列有 ( )个
( )+( ) = ( )
f(a1a2…a r) = b1b2…b r
n-rr
n-r n-r n-r+1r-1 r r
1.6组合的生成
解法２
任给 a1a2…a r? C’(n,r),a1 ＜ a2 ＜ … ＜ ar
令 f,a1a2…a r→b1b2…b r
bi = ai-i+1,i= 1,2,…,r.
1≤b1 ＜ b2 ＜ … ＜ br ≤ n-r+1,
b1b2…b r? C(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,r)+C(n,r-1)
不含“１” 至少含一个“１”
(n-1+r)!————
r!(n-1)!n+r-1
r
r个相同的球 /\
——————— ————————／ \0…010…01…10…0
\ /———— ————\/
n-1个相同的盒壁
1.7可重组合
另证 设 a1a2…a r? C(n,r)
1≤a1≤a2 ≤… ≤ar≤n,
令 C(n,r)上的 f,使得 bi=ai+i-1,i=1,2,…,r.
则 b1b2…b r满足 1≤b1＜ b2＜ … ＜ br≤n+r-1
b1b2…b r? C(n+r-1,r)
f,a1a2…a r→b1b2…b r
显然 f是单射,f,b1b2…b r→a1a2…a r
－
－
-1
1.7可重组合
ai=bi-i+1,i=1,2,…,r.
a1a2…a r? C(n,r)
f是单射 C(n,r)≤C(n+r-1,r)
f 是单射 C(n,r)≥C(n+r-1,r)
∴ C(n,r)=C(n+r-1,r)
第二个证明可说一种“拉伸压缩”技巧。
不可谓不巧妙。但仍不如第一证明来的明快，由此可见 组合证明 的功效。
—
—
—-1
—
1.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]取 a1,a2,…,a r.设 1≤a1＜ a2＜ … ＜ ar≤n,对取法分类,a1=1,有 C(n-1,r-1)种方案
a1>1,有 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)点，都满足此递推式
0<r≤n,n<0<r
C(n,r)= 1,r = 0
0,0≤n<r,r<0≤n
n<0且 r<0
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
[n]r——
r!
1.8若干等式及其组合意义
3.( )+( )+( )+…+( )=( ) (1.7.3)
[1]可从 (7.2)推论，也可做一下组合证明从 [1,n+r+1]取 a1a2…a nan+1，
设 a1＜ a2＜ … ＜ an ＜ an+1，
可按 a1的取值分类,a1=1,2,3,…r,r+1.
a1=1,a2…a n+1取自 [2,n+r+1] 有 ( )种取法
n n+1 n+2 n+r n+r+1
n n n n n
n+r
n2 取自 3 有 种取法
n+r-1
n… … …r,a2…a n+1取自 [r+1,n+r+1] 有 ( )种取法
n+1
n+1,a2…a n+1取自 [r 2,n+r+1] 有 ( )种取法nn
也可看做按含 1不含 1，含 2不含 2,…,
含 r不含 r的不断分类
1.8若干等式及其组合意义
[2]从 (0,0)到 (n+1,r),过且仅过一条带箭头的边,而过这些边的路径有 (从下到上 )
( ),( ),…,( )
故有,( )+( )+( )+…+( )=( )
n n+1 n+rn n n
n n+1 n+2 n+r n+r+1
n n n n n
r (n+1,r)
..
.
(0,0) n n+1
1.8若干等式及其组合意义
[3] 可重组合,
[1,n+2]的 C(n+2,r)模型 ( )
不含 1,含 1个 1,含 2个 1,…,含 r个 1
C( ),C( ),C( ),…,C( )
( ),( ),( ),…,( )
n+r+1r
n+1 n+1 n+1 n+1r r-1 r-2 0
n+r n+r-1 n+r-2 nr r-1 r-2 0
1.8若干等式及其组合意义
4,( )( )=( )( ) (1.7.4)
①选政治局,再选常委,n个中央委员选出 l
名政治局委员,再从其中选出 r名常委
②选常委,再选非常委政治局委员
两种选法都 无遗漏,无重复 地给出可能的方案，应该相等。
n l n n-r
l r r l-r
1.8若干等式及其组合意义
5,( )+( )+…+( )=2,m≤0,(1.7.5)
证 1(x+y)=∑ ( )x y,令 x=y=1,得 (1.7.5)
组合证 1 [1,m]的所有方案,每一子集都可取 k[1,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 m
0 1 m
m k m-km m
kk=0
m
m
m m m m m m
0 1 2 m-2 m-1 m
1.8若干等式及其组合意义
6,( )-( )+( )-… ± ( )=0 (1.7.6)
证 1
在 (x+y)=∑ ( )x y 中令 x=1,y=-1即得,
n n n n
0 1 2 n
n n-k knkn
k=0
1.8若干等式及其组合意义
证 2 在 [1,n]的所有组合中,
含 1的组合 ←→ 不含 1的组合,有 1— 1对应关系。在任一含 1组合及与之对应的不含
1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数阁元的组合做成另一集。
此二集的元数相等。
∑ ( )=∑( )n ni i
i奇 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
r 0 r 1 r-1 r 0
m n
r-l l
m+n m n
r r-l l
P(m-r,r) (m+n-r,r)
(m-r+l,r-l) l=0,1,2,…,r
Q(m,0)
r
l=0
1.8若干等式及其组合意义
李善兰 (1811— 1882），清代数学家
李善兰恒等式：
∑( )( )( )=( )( )k l n+k+l-j n+k n+lj j k+l k l
j≥0
证,利用 Vandermonde恒等式及
( )( )=( )( )=( )( )
(接下页 )
n v n n-p n n-p
v p p n-v p v-p
1.8若干等式及其组合意义有 ∑( )( )( )
=∑( )( )(∑( )( ) )
=∑( )∑( )( )( )
=∑( )∑( )( )( )
=∑( )( )( )
=∑( )( )( )
=( )∑( )( )
=( )( )
k l n+k+l-j
j j k+l
k l n+k l-j
j j k+v l-v
n+k k l l-j
k+v j j l-v
n+k k l v
k+v j v l
n+k l k+v
k+v v kn+k n l
k n-v v
n+k n l
k n-v v
n+k n+l
k l
j≥0
j≥0 v≥j
v≥0 j≥0
v≥0 j≥0
v≥0
v≥0
v≥0
1.8若干等式及其组合意义
8,在 7.中令 r=m≤n,再将 ( )换成 ( )
得 ( )=( )( )+( )( )+…+( )( )
m m
k m-k
m+n m n m n m n
m 0 0 1 1 m m
1.9应用举例
例 某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干钥匙。须４人到场，所备钥匙才能开锁。问①至少有多少把不同的钥匙？②
每人至少持几把钥匙？
解 ①每３人至少缺１把钥匙，且每３人所缺钥匙不同。故至少共有 ( )=35把不同的钥匙。
73
1.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种状态，
而且服从 Bose-Einstein分布，即同能级的质点可以处于相同的状态，问系统有几种不同的状态？（或图像）
B)若能级为 kE0的质点可有 2(k +1)种状态，
而且服从 Fermi-Dirac分布，即不允许同能级的两个质点有相同状态，问系统有几种不同状态？（或图像）
2
2
1.9应用举例
解 能级 k 0 1 2 3 4
A) k +1 1 2 5 10 17 状
B)2(k +1) 2 4 10 20 34 态
2
2
能量分布 0,0,0,4 0,0,1,3 0,0,2,2
A) 1·1·1·17 1·1·2·10 1·1·C(5,2)
B) C(2,3)·34 C(2,2)·4·20 C(2,2)·C(10,2)
能量分布 0,1,1,2 1,1,1,1
A) 1·C(2,2)·5 C(2,4) 72
B) 2C(4,2)·10 C(4,4) 246
—
— —
1.9应用举例
例
3个相同的质点分布在 2个相同的势阱里，这 3个质点的总能量为 3E0,每个质点的能级为 kE0,k=0,1,2,3,能级为 kE0的质点有 2(k +1)种状态，服从 Fermi-Dirac
分布即同一势阱中的质点不可处于同一状态，问系统有几种状态？
2
1.9应用举例
0,0|3 0|0,3 0,1|2 0|1,2 1|0,2
1·1·20 2·2·20 2·4·10 80 80
=20 =80 =80
1,1|1 111|φ 0,0,3|φ 0,1,2|φ
C(4,2)·4 ( ) 1·1·20 2·4·10
=24 =4 =20 =80
43
20·2+80·5+24+4=468
解,
1.9应用举例
例设 n位长能纠 r个错的码字的个数为 M，
则 2 /∑( )≤M≤2 /∑( )
n位长的 0-1字符串共有 2 个。但不能每个串都设为码字，否则市区纠错能力。
n n
k nk
n2r
k=0
r
k=0
1.9应用举例
Hamming距离 设 a=a1a2…a n,b=b1b2…b n是
n位串。则 a,b的 Hamming距离为
d(a,b)=∑|ai-bi|
即对应位不同的位的个数。
d(a,b)+d(b,c)≥d(a,c)
d(a,b)=∑|ai-bi|,d(b,c)=∑|bi-ci|
d(a,b)+d(b,c)=∑|ai-bi|+∑|bi-ci|
≥∑|(ai-bi)+(bi-ci)|=d(a,c)
n
i=1
a
r
上图表示以 a为球心,r位半径的球体中的串都作为 a处理
1.9应用举例
若规定 a是码字，收到 a’有 d(a,a’)≤r即将 a’
当作 a发生最多 r个错误
此时两个码字 a,b应满足 d(a,b)≥2r+1当作
a处理的串有 ( )+( )+…+( ) 个
故 M∑( )≤2
另一方面任一串与最近的码字的距离不大于 2r,否则此串本身可作为一新的码字，即以 2r位半径的各码字为球心，应当使任一串落入某球内，故 M∑( )≥2
n n n0 1 r
nk
nk
n
n
r
k=0
2r
k=0
1.9应用举例
例 脱氧核糖核酸 (DNA)的分子由 A(腺嘌呤 ),G(鸟嘌呤 ),C(胞嘧啶 )和 T(胸腺嘧啶 )4种碱基核糖核苷酸，以不同数目和种类排列成两条多核苷酸单链，这两条单链之间通过氢键把配对的碱基连接起来，形成双螺旋结构。连接过程总是 A和 T配对,G和 C
配对。显然长度为 n的核苷酸链共有 4 种不同方式。
n
1.9应用举例
生物遗传信息是由 DNA分子中 4个碱基核苷酸象电报密码似的以不同的排列顺序记录下来，它载着人类的全部基因或全部遗传信息。所谓基因就是 DNA上一小段,平均长度为 900-1500个碱基对。人的 DNA约有 3× 10 碱基对。
核糖核酸 (RNA)也是一种遗传物质，它是由 A,G,C,U(尿嘧啶 )4种碱基核苷酸排列而成的多核苷酸单链。
9
1.9应用举例
通过基因将它的遗传信息传递给 RNA,然后再传给蛋白质来表现其功能。
(1)蛋白质分子中有 20种氨基酸，在 RNA
中以一定顺序相连的 3个核苷酸决定 1种氨基酸，三联体遗传密码有 4 =64个排列方式。它保证了 20种氨基酸密码的需要。
(2)例如 RNA链,CCGGUCCGAAAG
酶将它分解成为 G片断 (即利用 G将
RNA分解 )。 CCG,G,UCCG,AAAG.
3
1.9应用举例
显然有 4!=24种不同的 RNA链有与此相同的 G片段。
若利用 U,C酶将上述的 RNA链分解成 U,C
片段,C,C,GGU,C,C,GAAAG
由于 GAAAG片段只能在最后出现，而且
C出现 4次，故有 C(5,4)=5种不同的核苷酸链，它的 U,C片段是上述的 C,C,C,C,GGU,
GAAAG,它们是
1.9应用举例
CCCCGGUGAAAG
CCCGGUCGAAAG
CCGGUCCGAAAG
CGGUCCCGAAAG
GGUCCCCGAAAG
(接上页 )
