第一章排列与组合.ppt

2004深研 组合数学第1章 1 徐宁计算机科学与技术学院2010年12月 组合数学Combinatorics 2004深研 组合数学第1章 2 组合数学的发展 组合数学是一个古老而又年轻的数学分支 据传说 大禹观察到神龟背上的幻方 纵横图 3阶方阵 填入1到9 每行 每列以及两条对角线的和都相等 2004深研 组合数学第1章 3 洛书 杨辉 纵横图九子斜排 上下对易 左右相更 四维挺进 裁九履 左三右七 二四为肩 六八为足 2004深研 组合数学第1章 4 组合数学的发展 贾宪 北宋数学家 约11世纪 著有 黄帝九章细草 算法斅古集 都已失传 杨辉著 详解九章算法 1261年 中曾引贾宪的 开方作法本源 图 即指数为正整数的二项式展开系数表 现称 杨辉三角形 比帕斯卡三角形早600年 和 增乘开方法 求高次幂的正根法 比霍纳的方法 1819年 早770年 霍纳 WilliamGeogeHorner 1786 1837 2004深研 组合数学第1章 5 组合数学的发展 1666年莱布尼兹所著 组合学论文 一书问世 这是组合数学的第一部专著 书中首次使用了组合论 Combinatorics 一词 18世纪 欧拉 哈密尔顿等 2004深研 组合数学第1章 6 组合数学的发展 组合数学的蓬勃发展则是在计算机问世和普遍应用之后 由于组合数学涉及面广 内容庞杂 并且仍在很快地发展着 因而还没有一个统一而有效的理论体系 这与数学分析形成了对照 主要研究的问题 存在性问题 计数问题 构造问题 最优化问题 2004深研 组合数学第1章 7 组合数学研究的问题 存在问题计算问题或分类问题构造问题 组合设计 优化问题 2004深研 组合数学第1章 8 组合数学与计算机科学 研究算法的理论基础组合分析 组合算法 组合分析是组合算法的基础编码理论图论密码学算法复杂性分析NP Complete问题与NP Hard问题搜索问题 组合最优问题 多约束最优问题近似解法及其复杂度 2004深研 组合数学第1章 9 如何学好组合数学 组合数学经常使用的方法并不高深复杂 最主要的方法是计数时的合理分类和组合模型的转换 但是 要学好组合数学并非易事 既需要一定的数学修养 也要进行相当的训练 2004深研 组合数学第1章 10 本课程章节安排 本学期主要讲组合分析 计数和枚举 以及组合优化的一部分 线性规划的单纯形解法 组合分析是组合算法的基础 第1章排列与组合第2章母函数第3章鸽巢原理第4章Polya定理第5章线性规划第6章组合优化及其在VLSI领域的应用 2004深研 组合数学第1章 11 第1章排列与组合 排列与组合加法法则与乘法法则模型转换全排列生成算法组合的生成可重组合与不相邻组合若干等式及其组合意义应用举例Stirling近似公式算法复杂性计算举例 2004深研 组合数学第1章 12 1 1排列与组合 排列 P n r n n 1 n r 1 n r Pn P n n n 组合 C n r P n r r nr n r n r n n r 2004深研 组合数学第1章 13 1 1排列与组合 圆排列 从n个中取r个的圆排列的排列数Q n r P n r r 2 r n以4个元素为例 2004深研 组合数学第1章 14 1 1排列与组合 项链排列 项链排列 排列的方法和项链一样 在圆排列的基础上 顺时针和反时针是同一个排列 从n个中取r个的项链排列的排列数R n r Q n r 2 P n r 2r 3 r n 112332 2004深研 组合数学第1章 15 1 1排列与组合 可重排列 求r1个1 r2个2 rt个t的排列设r1 r2 rt n 设此排列数为P n r1 r2 rt 对1 2 t分别加下标 得到P n r1 r2 rt r1 r2 rt n P n r1 r2 rt 思考 n个数中取r个的可重排列的排列数 n r1 r2 rt nr1r2 rt 2004深研 组合数学第1章 16 1 2加法法则和乘法法则 加法法则 设事件A有m种产生方式 事件B有n种产生方式 则事件A或B之一有m n种产生方式 集合论语言 若 A m B n A B 则 A B m n 2004深研 组合数学第1章 17 1 2加法法则和乘法法则 例 某课程A系学生16人选 B系学生7人选 其他系学生5人选 共有多少人选 解 根据加法法则 选课人数共有16 7 5 28人 2004深研 组合数学第1章 18 1 2加法法则和乘法法则 例 1组学生7人 2组学生6人 要派3名同组学生参加比赛 有几种可能 若两组学生任选3人 有几种可能 解 3名学生或者都是1组的 C 7 3 或者都是2组的 C 6 3 可能组合总数为 C 7 3 C 6 3 7 3 4 6 3 3 35 20 55若任选3人 可能组合为 C 7 6 3 13 3 10 286 2004深研 组合数学第1章 19 1 2加法法则和乘法法则 乘法法则 设事件A有m种产生式 事件B有n种产生方式 则事件A与B有m n种产生方式 集合论语言 若 A m B n A B a b a A b B 则 A B m n 2004深研 组合数学第1章 20 1 2加法法则和乘法法则 例 从A到B有三条道路 从B到C有两条道路 则从A经B到C有3 2 6条道路 例 某种样式的运动服的着色由底色和装饰条纹的颜色配成 底色可选红 蓝 橙 黄 条纹色可选黑 白 则共有4 2 8种着色方案 若此例改成底色和条纹都用红 蓝 橙 黄四种颜色的话 则 方案数就不是4 4 16 而只有4 3 12种 注意事件A和事件B的相互独立性 用加法法则和乘法法则重新考察排列组合公式 2004深研 组合数学第1章 21 1 2加法法则和乘法法则 1组学生7人 2组学生6人 问1组选2人2组选3人 或1组选3人2组选2人 共有几种组合 解 1组选2人 2组选3人 可能组合为 C 7 2 C 6 3 7 2 5 6 3 3 21 20 4201组选3人 2组选2人 可能组合为 C 7 3 C 6 2 7 3 4 6 2 4 35 15 525两种方案的总和 420 525 945 2004深研 组合数学第1章 22 1 2加法法则和乘法法则 例 某语言的标识符限定不超过4个字符 第1个字符必须是字母 大小写不分 第2 4个字符可以是字母和数字 可以有多少种组合 解 1个字符 C 26 1 26 有26种选择 2个字符 乘法法则 C 26 1 C 36 1 26 36 9363个字符 C 26 1 C 36 1 2 26 362 336964个字符 C 26 1 C 36 1 3 26 363 1213056总计可能组合 加法法则 各式相加 得1247714 2004深研 组合数学第1章 23 1 2加法法则和乘法法则 例 求小于10000的含1的正整数的个数解1 先求不含1的个数 4位数 0000除外 9 9 9 9 1 6560个 含1的有 9999 6560 3439个解2 全部4位数有104个 不含1的四位数有94个 含1的4位数为两个的差 104 94 3439个 2004深研 组合数学第1章 24 1 2加法法则和乘法法则 例 求小于10000的含0的正整数的个数注意 含0 和 含1 不可直接套用 0019含1但不含0 有许多类似的隐含的规定 要特别留神 解 不含0的1位数有9个 2位数有92个 3位数有93个 4位数有94个不含0小于10000的正整数有9 92 93 94 95 1 9 1 7380个含0小于10000的正整数有 9999 7380 2619个 2004深研 组合数学第1章 25 1 3模型转换 一一对应 一一对应 概念是一个在计数中极为基本的概念 一一对应既是单射又是满射 在组合计数时往往借助于一一对应实现模型转换 比如要对A集合计数 但直接计数有困难 于是可设法构造一易于计数的B 使得A与B一一对应 2004深研 组合数学第1章 26 1 3模型转换 一一对应 例在8名选手之间进行淘汰赛 最后产生一名冠军 问要举行几场比赛 9名选手 100名选手 解一种常见的思路是按轮计场 费事 另一种思路是淘汰的选手与比赛 按场计 集一一对应 100名选手99场比赛 2004深研 组合数学第1章 27 1 3模型转换例1 格路问题 简单格路问题 0 0 m n 从 0 0 点出发沿x轴或y轴的正方向每步走一个单位 最终走到 m n 点 有多少条路径 m nm y m n 0 x 2004深研 组合数学第1章 28 1 3模型转换例1 格路问题 无论怎样走法 在x方向上总共走m步 在y方向上总共走n步 若用一个x表示x方向上的一步 一个字母y表示y方向上的一步 则 0 0 m n 的每一条路径可表示为m个x与n个y的一个有重排列P m n m n 路径和x与y有重排列一一对应 2004深研 组合数学第1章 29 1 3模型转换例1 格路问题 所求方案数为P m n m n P m n m n C m n m C m n n 是否能直接推出该组合公式 可以先用组合分析得出两个公式P和C 从而证明P C 即组合证明 设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 2004深研 组合数学第1章 30 1 3模型转换例2 Cayley定理 例 Cayley定理 n个有标号的顶点的树的数目等于nn 2 分析 如果能找到一个序列 每一个排列与所形成的树一一对应 该序列的排列个数即为树的数目 2004深研 组合数学第1章 31 1 3模型转换例2 Cayley定理 41253 逐个摘去标号最小的叶子 叶子的相邻顶点形成一个序列 长度为n 2 1 由树生成序列 给定一棵有标号的树 边上的标号表示摘去叶的顺序 摘去一个叶子相应去掉一条边 第一次摘掉 为 相邻的顶点 得到序列的第一个数3 以此类推 得到序列31551 长度为7 2 5 2004深研 组合数学第1章 32 1 3模型转换例2 Cayley定理 2 由序列生成树 由序列31551与序列1234567排在一起 315511234567 315511234567 2 3 1551134567 1 3 55114567 4 5 511567 5 6 1157 1 5 17 1 7 641253 2004深研 组合数学第1章 33 1 3模型转换例2 Cayley定理 证由一棵n个顶点的树可得到一个长度为n 2的序列 且不同的树对应的序列不同 因此 T nn 2 对n用归纳法可证反之 由一个长度为n 2的序列 每个元素为1 n的一个整数 可得到一棵树 且不同的序列对应的树是不同的 因此nn 2 T T nn 2 2004深研 组合数学第1章 34 1 4全排列的生成算法 对于给定的字符集 用有效的方法将所有可能的全排列无重复无遗漏地枚举出来 A 字典序法 B 递增进位制数法 C 递减进位制数法 D 邻位对换法 2004深研 组合数学第1章 35 1 5组合的生成 例 C 6 4 123456 1234 1235 1236 1245 1246 12561345 1346 1356 14562345 2346 2356 2456 3456规律 1 c4 6 c3 5 C2 4 C1 3 ck n r k 2 从后往前 如果存在ck n r k 则令ck增1 然后其后面的数按升序依次排列 如 1456 c1增1为2 其后的3位依次为345 2004深研 组合数学第1章 36 1 5组合的生成 设从 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 2004深研 组合数学第1章 37 1 5组合的生成 C n r 的元素建立了字典序 12 r的序号为0 n r 1 n r 2 n的序号为C n r 1求组合的序号 例 在C 10 4 中4679的序号是首位小于4的组合的个数 首位是4 第2位小于6的组合的个数 前2位是46 第3位小于7的组合的个数 前3位是467 第4位小于9的组合的个数之和 2004深研 组合数学第1章 38 1 6可重组合与不相邻组合 可重组合 在n个不同的元素中取r个进行组合 若允许重复 称为可重组合C n r 例 C 4 3 共20个组合 123 124 134 234 无重 111 112 113 114 重1 212 222 223 224 重2 313 323 333 334 重3 414 424 434 444 重4 r可小于 等于或大于n 如C 3 4 1123 1224 C n r C n r 1 r 2004深研 组合数学第1章 39 1 6 1可重组合 C n r 的计数问题相当于r相同的球放入n个互异的盒子 每盒球的数目不同的方案的计数 而后一问题又可转换为r个相同的球与n 1个相同的盒壁的排列的问题 易知所求计数为 C n r 1 r n 1 r r n 1 r个相同的球 0 010 01 10 0 n 1个相同的盒壁 2004深研 组合数学第1章 40 1 6 1可重组合 另证设a1a2 ar C n r 1 a1 a2 ar n 令C n r 上的f 使得bi ai i 1 i 1 2 r 则b1b2 br满足1 b1 b2 br n r 1b1b2 br C n r 1 r f a1a2 ar b1b2 br显然f是单射 f b1b2 br a1a2 ar 1 2004深研 组合数学第1章 41 1 6 1可重组合 ai bi i 1 i 1 2 r a1a2 ar C n r f是单射C n r C n r 1 r f 1是单射C n r C n r 1 r C n r C n r 1 r 第一证明为组合证明方法 第二个证明为一一对应方法 是一种 拉伸压缩 技巧 后者非常巧妙 但仍不如第一证明来的明快 2004深研 组合数学第1章 42 1 6 2不相邻组合 不相邻组合 有序序列A 1 2 3 4 5 6 取r 3个的不相邻组合C 6 3 135 136 146 246C n r C n r 1 r 2004深研 组合数学第1章 43 1 6 2不相邻组合 例用两种方法计算 1 n 的无重不相邻组合C n r 的计数问题解法10 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 2004深研 组合数学第1章 44 1 6 2不相邻组合 以0结尾 r个10与n 2r个0的排列r n 2r n r这样的排列有 个 f a1a2 ar b1b2 br n rr n rn rn r 1r 1rr 2004深研 组合数学第1章 45 1 6 2不相邻组合 解法 任给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 2004深研 组合数学第1章 46 1 7若干等式及其组合意义 组合意义或组合证明 组合证明是一种有效的证明方法 2004深研 组合数学第1章 47 1 7 1等式1及其组合意义 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 2004深研 组合数学第1章 48 1 7 2等式2及其组合意义1 2 C n r C n 1 r C n 1 r 1 1 7 2 从 1 n 取a1 a2 ar 设1 a1 a2 ar n 对取法分类 a1 1 有C n 1 r 1 种方案 取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 2004深研 组合数学第1章 49 1 7 2等式2及其组合意义1 杨辉三角除了 0 0 点 都满足此递推式0 r n n 0 rC n r 1 r 00 0 n r r 0 nn 0且r 0 1 r 1 n 1 n r n r r 2004深研 组合数学第1章 50 1 7 2等式2及其组合意义2 另一种形式 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 y m 1 n m n 1 0 x m n 2004深研 组合数学第1章 51 1 7 3等式3及其组合意义 3 1 7 3 另一种形式 1 可从 1 7 2 推论C n r C n 1 r C n 1 r 1 C n r 1 n 1 C n r n 1 C n r n C n r 1 n 1 C n r 1 n C n r n C n 2 n 1 C n 2 n C n r 1 n C n r n C n 1 n 1 C n 1 n C n 2 n C n r n C n n C n 1 n C n 2 n C n r n nn 1n 2n rn r 1nnnnn 1 nn 1n 2n rn r 1012rr 2004深研 组合数学第1章 52 1 7 3等式3及其组合意义1 3 1 7 3 2 组合证明1 从 1 n r 1 取a1a2 anan 1 设a1 a2 an an 1可按a1的取值分类 a1 1 2 3 r r 1 a1 1 a2 an 1取自 2 n r 1 有 种取法 nn 1n 2n rn r 1nnnnn 1 n rn a1 r a2 an 1取自 r 1 n r 1 有 种取法 a1 r 1 a2 an 1取自 r 2 n r 1 有 种取法 nn a1 2 a2 an 1取自 3 n r 1 有 种取法 也可看作按是否含1 是否含2 是否含r的不断分类 n r 1n n 1n 2004深研 组合数学第1章 53 1 7 3等式3及其组合意义2 3 格路问题 从 0 0 到 n 1 r 过且仅过每条带箭头的边 而过这些边的路径有 从下到上 故有 nn 1n rnnn nn 1n 2n rn r 1nnnnn 1 r n 1 r 0 0 nn 1 2004深研 组合数学第1章 54 1 7 3等式3及其组合意义3 4 可重组合 1 n 2 的C n 2 r 模型 不含1 含1个1 含2个1 含r个1C C C C n r 1r n 1n 1n 1n 1rr 1r 20 n rn r 1n r 2nrr 1r 20 2004深研 组合数学第1章 55 1 7 4等式4及其组合意义 4 1 7 4 选政治局 再选常委 n个中央委员选出m名政治局委员 再从其中选出r名常委 选r名常委 再从其余n r名中央委员中选m r名非常委政治局委员两种选法都无遗漏 无重复地给出可能的方案 应该相等 nmnn rmrrm r 2004深研 组合数学第1章 56 1 7 5等式5及其组合意义1 5 2m 1 7 5 证1 x y m xkym k 令x y 1 得 1 7 5 组合证1 1 m 的所有方案 每一元素都可取或不取2种可能 有乘法法则有2m个方案 另可有0 子集 空集 1 子集 m 子集 即从m个元素中分别取0个 1个 m个的组合的总和 mmm01m mmkk 0 2004深研 组合数学第1章 57 1 7 5等式5及其组合意义2 续5 2组合证2从 0 0 走m步有2m种走法 都落在直线x y m上 而到 m 0 m 1 1 m 2 2 2 m 2 1 m 1 0 m 各点的走法各有 种 mmmm01m mmmmmm012m 2m 1m 2004深研 组合数学第1章 58 1 7 6等式6及其组合意义1 6 0 1 7 6 证1在 x y n xn kyk中令x 1 y 1即得 nnnn012n nk nk 0 2004深研 组合数学第1章 59 1 7 6等式6及其组合意义2 证2在 1 n 的所有组合中 含1的组合 不含1的组合 有1 1对应关系 在任一含1组合及与之对应的不含1组合中 必有一奇数个元的组合与一偶数个元的组合 将含奇数个元的组合做成集 将含偶数个元的组合做成另一集 此二集的元数相等 nnii i奇i偶 2004深研 组合数学第1章 60 1 7 7等式7及其组合意义1 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 nmnmnmnr0r1r 1r0 mnr ll m nmnrr ll P m r r m n r r m r l r l l 0 1 2 rQ m 0 rl 0 2004深研 组合数学第1章 61 1 7 8等式7及其组合意义 7 在1 7 7 中令r m n 再将 换成 得 mmkm k m nmnmnmnm0011mm m nmnmnmnm0011mm 2004深研 组合数学第1章 62 1 8应用举例 排列和组合的应用 2004深研 组合数学第1章 63 1 8 1应用举例 1 例1某保密装置须同时使用若干把不同的钥匙才能打开 现有 人 每人持若干钥匙 须 人到场 所备钥匙才能开锁 问 至少有多少把不同的钥匙 每人至少持几把钥匙 解 每 人至少缺 把钥匙 且每 人所缺钥匙不同 故至少共有 35把不同的钥匙 73 2004深研 组合数学第1章 64 1 8 1应用举例 1 任一人对于其他 人中的每 人 都至少有 把钥匙与之相配才能开锁 故每人至少持 20把不同的钥匙 为加深理解 举一个较简单的例子 人中 人到场 所求如上 共有 6把不同的钥匙 每人有 3把钥匙 见下页图 2004深研 组合数学第1章 65 1 8 1应用举例 1 钥匙 A 人B C D 2004深研 组合数学第1章 66 1 8 2应用举例 2 例2从 0 0 点到达 m n 点 m 0 1 m n a b 2 求 0 1 m n 且接触或穿过y x的路径与 1 0 m n 一一对应 后者必过y x yy x m n 0 1 0 x 0 1 2004深研 组合数学第1章 67 1 8 2应用举例 2 3 N 0 1 m n 1 0 m n C m n 1 m C m n 1 m 1 m n 1 1 m n 1 1 m 1 n m n 1 n m m n C m n 1 m n m n 2004深研 组合数学第1章 68 1 8 2应用举例 2 若条件改为可接触但不可穿过 则限制线要向下或向右移一格 得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 1 m nm 2004深研 组合数学第1章 69 1 8 3应用举例 3 例3 纠错码Hamming不等式 设n位长能纠r个错的码字的个数为M 则2n M 2n n位长的0 1字符串共有2n个 但不能每个串都设为码字 否则失去纠错能力 nk nk 2rk 0 rk 0 2004深研 组合数学第1章 70 1 8 3应用举例 3 Hamming距离设a a1a2 an b b1b2 bn是n位串 则a b的Hamming距离为d a b ai bi 即对应位不同的位的个数 Hamming三角不等式 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 ni 1 a r 2004深研 组合数学第1章 71 1 8 3应用举例 3 若规定a是码字 收到a 有d a a r 即将a 当作a发生最多r个错误此时两个码字a b应满足d a b 2r 1 否则不能判断正确的码是a还是b 当作a处理的串有 个 故M 2n另一方面任一串与最近的码字的距离不大于2r 否则此串本身可作为一新的码字 即以2r为半径的各码字为球心 应当使任一串落入某球内 故M 2n nnn01r nk nk rk 0 2rk 0 2004深研 组合数学第1章 72 1 8 3应用举例 3 例 n 3 r 1 M 23 1 C 3 1 8 4 2 即 000 111对码字000 有001 010 100都作为000传输出错予以纠正 对码字111 有011 101 110都作为111传输出错予以纠正 a r 2004深研 组合数学第1章 73 1 8 4应用举例 4 例有4个相同质点 总能量为4E0 E0是常数 每个质点所具能量为kE0 k 0 1 2 3 4 A 若能级为kE0的质点可有k 1种状态 而且服从Bose Einstein分布 即同能级的质点可以处于相同的状态 问系统有几种不同的状态 或图像 B 若能级为kE0的质点可有2 k 1 种状态 而且服从Fermi Dirac分布 即不允许同能级的两个质点有相同状态 问系统有几种不同状态 或图像 2004深研 组合数学第1章 74 1 8 4应用举例 4 解 能级k01234A k2 11251017状B 2 k2 1 24102034态 4个质点 能量分布0 0 0 40 0 1 30 0 2 2A 1 1 1 17 171 1 2 10 201 1 C 5 2 15B C 2 3 34 0C 2 2 4 20 80C 2 2 C 10 2 45能量分布0 1 1 21 1 1 1总状态数A 1 C 2 2 5 15C 2 4 572B 2C 4 2 10 120C 4 4 1246 2004深研 组合数学第1章 75 1 8 5应用举例 5 例5 DNA脱氧核糖核酸 DNA 的分子由A 腺嘌呤 G 鸟嘌呤 C 胞嘧啶 和T 胸腺嘧啶 4种碱基核糖核苷酸 以不同数目和种类排列成两条多核苷酸单链 这两条单链之间通过氢键把配对的碱基连接起来 形成双螺旋结构 连接过程总是A和T配对 G和C配对 显然长度为n的核苷酸链共有4种不同方式 2004深研 组合数学第1章 76 1 8 5应用举例 5 生物遗传信息是由DNA分子中4个碱基核苷酸象电报密码似的以不同的排列顺序记录下来 它载着人类的全部基因或全部遗传信息 所谓基因就是DNA上一小段 平均长度为900 1500个碱基对 人的DNA约有3 10碱基对 核糖核酸 RNA 也是一种遗传物质 它是由A G C U 尿嘧啶 4种碱基核苷酸排列而成的多核苷酸单链 2004深研 组合数学第1章 77 1 8 5应用举例 5 通过基因将遗传信息传递给RNA 然后再传给蛋白质来表现其功能 1 蛋白质分子中有20种氨基酸 在RNA中以一定顺序相连的3个核苷酸决定1种氨基酸 三联体遗传密码有4 64个排列方式 它保证了20种氨基酸密码的需要 2 例如RNA链 CCGGUCCGAAAG酶将它分解成为G片断 即利用G将RNA分解 CCG G UCCG AAAG 2004深研 组合数学第1章 78 1 8 5应用举例 5 显然有4 24种不同的RNA链有与此相同的G片段 若利用U C酶将上述的RNA链分解成U C片段 C C GGU C C GAAAG CCCCGGUGAAAGCCCGGUCGAAAGCCGGUCCGAAAGCGGUCCCGAAAGGGUCCCCGAAAG 由于GAAAG片段只能在最后出现 而且C出现4次 故有C 5 4 5种不同的核苷酸链 它的U C片段是上述的C C C C GGU GAAAG 2004深研 组合数学第1章 79 1 9Stirling近似公式 组合计数的渐进值问题是组合论的一个研究方向 Stirling公式n 2 n 它给出一个求n 的近似公式 它对从事计算和理论分析都是有意义的 ne n 2004深研 组合数学第1章 80 1 9Stirling近似公式 Stirling公式表明 其相对误差随着n趋于 而趋于0而其绝对误差可能很大 lim n 2n 证明从略 nne n 2004深研 组合数学第1章 81 1 10算法复杂性计算举例 算法复杂性分析是计算机科学技术领域最重要的内容 组合数学是算法复杂性分析最重要的基础 算法复杂性包括时间复杂性和空间复杂性 时间复杂性包括不同操作的运算次数 空间复杂性指占用存储空间的大小 这里只是举几个简单例子 参看教材第6章 有专门研究算法与算法复杂性的课程和教材 2004深研 组合数学第1章 82 1 10 1排序算法 1 归并排序算法 S1 2分 S2 各自归并排序 S3 两个序列归并 例 5 9 3 11 2 8 0 4 1 5 10 7S1 2分 5 9 3 11 2 8 0 4 1 5 10 7S2 排序 2 3 5 8 9 11 0 1 4 5 7 10 分别递归 S3 归并 0 1 2 3 4 5 5 7 8 9 10 11复杂性分析 比较次数设长度N 2n Tn 最好情况比较次数 Cn 最坏情况比较次数 2004深研 组合数学第1章 83 1 10 1排序算法 1 最好情况复杂性最好情况出现在对下面两个序列的归并 a1 a2 a2n 1b1 b2 b2n 1比较次数 2n 1 Tn 2Tn 1 2n 1 T1 1 Tn 2 2Tn 2 2n 2 2n 1 22Tn 2 22n 1 22 2Tn 3 2n 3 22n 1 23Tn 3 32n 1 2n 1T1 n 1 2n 1 2n 1 n 1 2n 1 n2n 1 n2n或 Tn NlogN 12 12 2004深研 组合数学第1章 84 1 10 1排序算法 最坏情况复杂性 需要所有的元素比较Cn 2Cn 1 2n C1 1 1 1 1C1 2C0 1 则C0 0 n Cn n2n NlogN CnCn 1Cn 2C02n2n 12n 120 Cn2n 2004深研 组合数学第1章 85 1 10 2判决树 1 银币问题 1 银币问题n个银币 其中有一个假银币重量不同 或轻或重 问最少用天平称几次 可以找出假币 n 4 另给1块标准硬币0 最多称2次 判决树 0 4 2 3 2 3 0 1 2 3 3 1 2 4 全好4 2 1 3 2004深研 组合数学第1章 86 1 10 2判决树 1 银币问题 n 3h 1 的情况 可用h次称出 h 1 n 2 1次称出h 2 n 4 2次称出 前例 h 3 n 13 3次称出 见教材467页 h 2nh 1 3h 2nh 1 1 3h 1 2nh 1 3 2nh 1 1 6nh 1 3 nh 3nh 1 1 12 2004深研 组合数学第1章 87 1 10 2判决树 1 银币问题 步骤 S1 取nh 1枚银币 真币1枚 nh 1 1枚S2 1 若左右 左边nh 2 真币 右边nh 2 1 比较 转S2 3 若左 右 对未参与比较的nh 1枚判决 转S1 2004深研 组合数学第1章 88 1 10 2判决树 1 银币问题 n 3h 1 的情况 不能判断称h次是否足够 N个银币应有2n 1种可能 判决树应有2n 1个叶子 称h次则树的叶子最多为3h 应有2n 1 3h 即n 3h 1 12 12 2004深研 组合数学第1章 89 1 10 2判决树 2 2 字母组合 由26个英文字母构成长度为5的字符串 求符合下列要求的字符串个数 6个元音AEIOUY不相邻 不存在3个辅音相邻 相邻的辅音必不同 2004深研 组合数学第1章 90 1 10 2判决树 2 A 元音集合 AEIOUY B 辅音集合 判决树 ABABBBBAABBABABBABABABBAABABBBABBABABABBABBABABABAABABBBBABABBABBBABABBABBA 2004深研 组合数学第1章 91 1 10 2判决树 2 各组合数目 ABBAB n1 62 20 20 19 ABABA n2 63 202ABABB n3 62 20 20 19 BBABA n4 62 20 20 19 BBABB n5 6 20 19 2BABAB n6 62 203BABBA n7 62 20 2