版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第20讲 组合计数n主要内容:n1. n2.n3. n我们知道,离散数学研究离散对象. 组合计数,简称计数(counting)就是计算满足一定条件的离散对象的安置方式的数目. n对于给定离散对象的安置方式,要考虑其存在性问题、计数问题、构造方法、最优化问题,这些是组合数学研究的全部内容(参见文献6). 组合数学发源于数学消遣和数学游戏,其研究历史可追溯到公元前2200年中国的大禹治水时代,从洛河中浮出的神龟背部上出现的三阶幻方开始,该方阵的每一行、每一列以及两条对角线的三个数字之和都等于15,其研究方兴未艾. n计算机科学是研究算法的一门科学,组合计数是算法分析与设计的基础,它对于分析算法的时
2、间复杂度和空间复杂度是至关重要的. 当然,组合计数在诸多领域的很多问题的讨论中也经常用到. 从儿时的数“数”也略知组合计数的重要性. n本章主要讨论组合计数的基本计数技巧和方法,包括计数的基本原理、排列组合、二项式定理、生成函数与递归关系等内容,它们都与集合、映射、运算和关系密切联系. n1. 个元素的 -排列n从 个不同的元素中,取 个出来按rnpn注意到n随着 的增大, !呈指数增长. nstirling给出的近似公式为: 123) 1(!nnn.e2!nnnnn利用乘法原理有下述结论. 对于任意 , 有n显然 , 个元素的全排列个数为 !. n约定)!(!) 1() 1(rnnrnnnp
3、rn. 10npn2. 个元素的 -圆排列n实际上, 个元素的 -排列是线排列. 如果从个不同的元素中, 取 个出来按顺序排列成一个圆, 就是 个元素的(circular permutation), 这样的排列个数记为 或( , ). rnp11223344中国传统(上下左右)?n上面的圆排列可以得到1234,2341,3412和4123四个线排列. n一般地, 一个 -圆排列可以得到 个 -排列,于是 rpprnrnn3. 个元素的 -可重排列n 前面所讨论的排列中要求没有重复元素. 如果从 个不同的元素中,可重复取 个元素按顺序排列,就是 个元素的(permutation with rep
4、etition),这样的排列个数记为 或 ( , ).rnun可以这样理解 -可重排列: 先从 个元素中任取一个元素出来排在第一位置, 有 种选取方式. 将其放回后, 再任意取一个元素出来排在第二位置, 也有 种选取方式. 这样一直进行下去, 直到有 个元素排列为止. 因此, 根据乘法原理有rrnnu n4. 有重复元素的全排列设1, 2, , 是 个不同元素,现有 个 元素( = 1, 2, , , 1 +2 + + = ), 即n(,2211kkananana!21knnnnnproof 记这 个可重元素的全排列个数为 . 将 个 元素看作不同的元素n于是得到1 +2 + + = 个不同元
5、素,其全排列个数为 !. 由于 个不同的元素的全排列个数为 ! ( = 1,2, ),于是所给 个可重元素的一个全排列可以得到1!2! !个 个不同元素的全排列, 根据乘法原理知.,.,2 , 1,21kiaaainiii!21knnnnnn1. 个元素的 -组合n从 个不同的元素中, 取 个出来放成一堆而不考虑其顺序, 就是 个元素的(combination), 其组合个数记为 或 或 ( , ). n上面的三个组合个数的记号都是标准的, 但n 和 容易混淆. rncrnrncrnn约定当 时, ;同时约定, n由于一个 -组合可以得到 !个 -排列,根据乘法原理有下述结论. 0rnc. 1
6、, 1000ccn!)!(!rrnnrpcrnrnn2. 个元素的 -可重组合n如果从 个不同的元素中, 可重复地取 个元素而不考虑其顺序, 就是 个元素的(combination with repetition),这样的组合个数记为 或 ( , ). rnfrrnrncf1(euler证法) 不妨设 个不同元素分别为1, 2, , . 可重复选取的 个元素为1, 2, , , 可设12 . 记1 = 1, 2 = 2+ 1, , = + ( - 1), 于是得到另外一个组合1, 2, , . 显然, n是1, 2, , 到1, 2, , 的一一对应, 于是组合1, 2, , 的个数与组合1,
7、 2, , 的个数相同. 而组合1, 2, , 是在1, 2, , , + 1, , + ( - 1)这 + 1个不同的元素的 -组合, 其个数为.,.,2 , 1,:ridcfii.1rrncn容易证明, 个元素的 -可重组合个数与不定方程n的非负整数解的个数相同. 利用这一点, 可以证明:若 个元素的 -可重组合中每个元素至少出现一次, 则 且这样的组合个数为 8-1 从为数众多的一元币、五元币、十元币、五十元币和一百元币中选取6张出来,有多少种选取方式? rxxxn21.11nrcnsolution n根据题意, 就是从5个不同的元素中, 可重复地取6个元素而不考虑其顺序的6-可重组合,
8、 其组合个数为610616565ccf.2101234565678910n与组合有关的恒等式有近1000个,下面是常用的三个组合恒等式,可采用组合的计算公式定理8-3加以证明,也可以根据组合的意义进行“组合证明”. n(1) n(2) n(3) .rnnrncc.111rnrnrnccc.11rnrncrncn与组合密切相关的是下述二项式定理.() 设 为正整数, 则对于任意 和 , 有 .)(0rnrnrrnnyxcyxn正因为这样,组合数又称为. 根据二项式定理,有 将所有 个元素的 -排列和 -组合列举出来的方法. .1)1 (2210nnnnnrnrrnnxcxcxcxcx.1) 11
9、 (2210nnnnrnrrnnncccxcn前面从计数的加法原理和乘法原理出发,介绍了排列组合的概念以及一些计算其个数的公式. (generating function)又称为母函数,它是解决满足一定要求的排列组合计数问题的一种重要工具, 也是求解递归关系的一种工具. n利用生成函数解决计数问题的基本思想就是将要计算的个数 = ( ) 转化为一个关于 的函数,通过对 或 的系数的讨论得出结论( = 0, 1, 2, ). ! rxr对于数列0,1, ,其(ordinary generating function)为n(形式)幂级数?02210)(rrrrrxaxaxaxaaxgn(1) 设
10、个元素的 -组合个数为 , = 0, 1, 2, . 显然, 有 n其组合计数生成函数为nrnrcrarnr, 0,0, 1nnnnnnxxcxcxc)1 (1221nxxx)1 ()1)(1 (n于是, 就是其组合计数生成函数 中的系数且 n实际上, 中第 个(1 + )可理解为 个元素中的第 个元素,其中的“1”表示在组合中不取第 个元素,“ ”表示在组合中选取了第 元素( = 1, 2, , ). 0rrrxa.)1 ()1 ()1)(1 (0nnrrrxxxxxanxxx)1 ()1)(1 (n(2) 设 个元素的 -可重组合个数为 , = 0, 1, 2, . 显然,有n特别地0 =
11、 1. 现考虑 n其展开式中 来源于第一个括号(1 + + 2)中的 , 第二个括号(1 + + 2)中的 , , 第 个括号(1 + + 2)中的 的乘积,即.1rrnrcanxxxxxx)1 ()1)(1 (2221mx2mxnmxrmmmxxxxn21n这时, n该不定方程的非负整数解的个数即为 换句话说,有 n因此, 上式右边展开式中 的系数就是 .实际上, ., 2 , 1, 0,21nimrmmmin.1rrncnnrrrxxxxxxxa)1 ()1 ()1 (2220n中的第 个(1 + + 2) 可理解为 个元素中的第 个元素, 其中的“1”表示在组合中不取第 个元素, “ ”
12、表示在组合中第 个元素取一次, “2”表示在组合中第 个元素取了两次, “3”表示在组合中第 个元素取了三次, , ( = 1, 2, , ). n上述思想还可以推广, 例如在组合计数生成函数中出现乘积项(24),则表示对应的元素可取两次或四次. nxxxxxx)1 ()1)(1 (222n(1)n(2)n( 为实数). n(3)2111xxx2! 2) 1(1)1 (xmmmxxm32! 31! 211exxxxn下面通过例子说明如何利用组合计数生成函数解决一般的组合计数问题. 8-2 一口袋中有5个红球, 3个黄球, 绿、白、黑球可任意多提供. 现从中取3个球, 有多少种选取方式? 设取
13、个球的方法有 种( = 0, 1, 2, ), 则组合计数生成函数 rrxaxaxaaxg2210)(32325432)1)(1)(1 (xxxxxxxxxx353a8-3 现有2 个 , 2 个 , 2 个 , 求从它们中选出3 个字母的方式数. 设取 个球的方法有 种( = 0, 1, 2, ), 则组合计数生成函数rrxaxaxaaxg2210)(322)1 (nxxx2122333nnncca对于数列0, 1, , , , 其(exponential generating function)为n这时, 排列个数 是 的系数. ! rxr! 2)(2210rxaxaxaaxerrn可以证
14、明下述定理.8-6 设1 ,2 , , 是 个不同元素, 现有 个 元素( = 1, 2, , , 1 +2 + + = ), 则在这 个元素中任取 个元素的排列个数为 , 则其排列计数生成函数为! 2)(2210rxaxaxaaxerr! 21! 21! 212221221knnnnxxxnxxxnxxxkn实际上, 上式右边的第 个括号表示第 个元素, 其中的“1”表示不取第 个元素, “ ”表示第 个元素取了一次用来排列, “ 2/2!”表示第个元素取了两次用来排列, , “ ”表示第个元素取了 次用来排列, 当然第 个元素最多取 次( = 1, 2, , ). n若一个元素在排列中至少
15、取两次, 至多取五次, 则在排列计数生成函数中应出现 n乘积项. !innxi! 5! 4! 3! 25432xxxxn利用该思想可以解决很多的排列计数问题.8-4 用0, 1, 2, 3, 4五个数字, 求可组成六位数的个数, 其中0恰出现一次, 1出现两次或三次, 2不出现或出现一次, 3没有限制, 4出现奇数次. 先计算不出现0的满足其余条件的五位数个数. n设不出现0的满足其余条件的 位数个数为 ,则排列计数生成函数n由于在满足要求的六位数中, 0恰出现一次, 而由所求出的每个五位数可得到5个不同的六位数, 如由12134可得到121340, 121034, 121304, 12013
16、4, 102134, 故满足要求的六位数有140 5 = 700. ! 5! 3! 3! 21)1 (! 3! 2)(533232xxxxxxxxxxe1405a8-5 将 个点排成一条直线, 用红、白、黑三种颜色对其任意涂色, 要求同色点为偶数(包括0), 有多少种涂法?这是一个排列问题, 设排成一行的个点满足要求的涂法有 种, = 0, 1, 2, , 则排列计数生成函数n作业 习题8.2 15.342! 4! 21)(xxxennnna)3() 1(3381n还有一些计数问题可以归结到建立和求解递归关系. 在学习数列时,有时会出现数列的后项是由前项或前几项确定的,这实际上就是递归关系,又
17、称为递推关系.n利用递归关系解决计数问题是很重要的方法之一,在其他数学分支中都会用到此技巧. 就计算机科学来说,大多数算法的执行都表现为按某种条件重复地执行一些循环,而这些循环经常可以用递归关系来表达. 因此,递归关系的建立和求解对算法分析来讲就变得至关重要.n本节先举例说明如何建立递归关系,再给出常用的求解递归关系的方法. 部分内容讨论涉及到高等数学中幂级数及其运算等有关内容. n如果一个问题可以归结到其前面一个问题或前面一些问题, 这就是递归问题, (recurrence)又称为递推. n在知道0 = 1时, 对于任意正整数 ,定义 = -1,这实际上是阶乘函数的递归定义或者说借助于递归给
18、出集合0, 1, ,的定义, 的计算归结到其前面的一个-1的计算,这时 = -1就是一个递归关系,或称为递归方程,或递归函数,其中0 = 1称为初始条件或边界条件. n给定数列0, 1, , , , 该数列中除有限项以外的任何项与其前面一项或前面一些项的一个方程称为n对于数列0, 1, , , ,需要一定的技巧才能得出其递归关系, 要知道是 的一个解析表达式 ( )有时也是比较困难的, 它通常由其初始条件和递归关系来确定. n我们现在感兴趣的是得出是 的解析表达式, 虽然一般情况下很难办到这一点. n下面是根据具体问题建立递归关系的两个例子. , hanoi tower) n(1) 一次只能移
19、动一个金盘;n(2) 金盘只能在三根宝石针上存放;n(3) 不允许将大金盘放在小金盘上. n假设 是金盘的数目(如 = 64), 按规则需要移动的次数,求的初始条件及递归关系. 显然, 初始条件为1 = 1. n当有 个金盘时, 可以先将宝石针 最上面的 - 1个金盘按规则移动另外一根宝石针上, 可设为 , 需要移动 1次. 再将 上最大的金盘移动到 , 移动一次. 最后将宝石针 上的 - 1个金盘按规则移动到 , 要移动 1次. n根据加法原理, 有递归关系121nnhh(,fibonacci sequence) 显然,初始条件为1 = 1, 2 = 1. = 第 个月大兔子的对数 + 第
20、个月小兔子的对数, n而第 个月大兔子的对数 = 第 - 1个月兔子的对数-1, n第 个月小兔子的对数 = 第 1大兔子的对数 = 第 2兔子的对数-2, n见图8-3, 其中实心点表示大兔子对, 空心点表示小兔子对. 21nnnfff12345n1. n递归法又称为递推法, 是将对数列第 项的计算转化为对其前面的一个项或一些项的计算, 直到最后归结到初始条件. 在1 = 1时, 求解递归关系 . 121nnhh121nnhh1221) 12(2222nnhh. 1212.22.211nnnh 由于1 = 1且 = 2 1 + 1,于是2= 21 + 1 = 3 = 22 1. 进而有3=
21、22 + 1 = 7 = 23 1, , = 2 - 1. n迭代法与递归法是不同的. n当 = 64时, 64 = 264 - 1 = 18,446,744,073,709,551,615.n若移动一次只需用1s,约需5845亿年. n2. n(1) 根据所给数列构造其生成函数;n(2) 利用递归关系以及已知函数的形式幂级数求出该生成函数;n(3) 想办法得出生成函数中 或 / !的系数即为所求. 在初始条件1 =1, 2 = 1下, 求解递归关系n由数列1, 2, , , , 构造组合计数生成函数 11nkknknaaa122113133aaaaaaakkkaaa
22、aaaaakkkrrxaxaxaaxg2210)(xxgxg)()(2,2411)(xxg2411)(xxgnnnnxcn112211221nnncna 在初始条件0 =1下, 求解递归关系( 1)由数列0, 1, , , , 构造排列计数生成函数nnnndd) 1(1! 2)(2210rxaxaxaaxerrxxex1e)(!1) 1(! 31! 2111nndnnn3. n对于常系数线性递归关系, 可以考虑用特征方程法求解. 分两种情况分别进行讨论.n(1) n设 为正整数, 在初始条件0, 1, , -1下,递归关系n称为(linear homogeneous recurrence re
23、lation of order with constant coefficient), 其中1, 2, , 为常数且 0. )(2211knacacacaknknnn阶常系数线性齐次递归关系的(characteristic equation)定义为02211kkkkcccnna若递归关系n的特征方程有 个不同的根n则其通解为n给定初始条件0, 1, , -1可唯一确定出其中的待定常数1, 2, , .)(2211knacacacaknknnn,21k.2211nkknnnccca 在初始条件1 = 1, 2 = 1下, 求解递归关系 = 1 + 2 ( 3). 递归关系 = 1 + 2的特征方程为n其根为 012251,25121.2211nnncca若递归关系n的特征方程有 个不同的根n其重数分别为n则其通解为n给定初始条件0, 1, , -1可唯一确定出其中的待定常数1, 2, , .)(2211knacacacaknknnn,21t),(,2121krrrrrrtt)()()(21nananaatn., 2 , 1,)(121tincnc
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二五年度网络安全风险评估与解决方案合同范本3篇
- 二零二五版股权激励合同:某上市公司对高级管理人员股权激励计划3篇
- 2025年度时尚服饰店开业活动承包合同3篇
- 2025年度高端不锈钢医疗器械制造委托合同3篇
- 二零二五版智能穿戴设备代加工合同范本2篇
- 二零二五年度环保型车间生产承包服务合同范本3篇
- 二零二五年高管子女教育援助与扶持合同3篇
- 2025年草场租赁与牧区基础设施建设合同3篇
- 二零二五版涵洞工程劳务分包单价及工期延误赔偿合同3篇
- 二零二五版财务报表编制会计劳动合同范本3篇
- GB/T 34241-2017卷式聚酰胺复合反渗透膜元件
- GB/T 12494-1990食品机械专用白油
- 运输供应商年度评价表
- 成熙高级英语听力脚本
- 北京语言大学保卫处管理岗位工作人员招考聘用【共500题附答案解析】模拟试卷
- 肺癌的诊治指南课件
- 人教版七年级下册数学全册完整版课件
- 商场装修改造施工组织设计
- 统编版一年级语文上册 第5单元教材解读 PPT
- 加减乘除混合运算600题直接打印
- ASCO7000系列GROUP5控制盘使用手册
评论
0/150
提交评论