ch2-基本计数规则-czm(1).ppt

1、应用组合数学,曹霑懋 ,第1章 什么是组合数学 第一部分 组合数学的基本工具 第2章 基本计数规则 第3章 图论概述 第4章 关系 第二部分 计数问题 第5章 生成函数及其应用 第6章 递推关系 第7章 容斥定理 第8章 波利亚计数理论 第三部分 存在问题 第9章 组合设计 第10章 编码理论 第11章 图论中的存在问题 第四部分 组合优化 第12章 匹配与覆盖 第13章 图和网络的优化问题,章目录,应用组合数学第二章-节目录,节目录,第2章 基本计数规则 2.1 乘法规则 2.2 加法规则 2.3 排列 2.4 计算的复杂度 2.5 r排列 2.6 子集 2.7 r组合 2.8 概率,2.1

2、 乘法规则,乘法规则：独立的事件X，Y，完成它们的方法 数分别为x，y，则完成X和Y的方法数为xy （事件E1发生，发生，和都发生，）,完成某件事情需先后分成n个步骤,做第一步有m1种方法,第二步有 m2 种方法,依次类推,第n步有mn种方法,则完成这件事共有N=m1m2mn种不同的方法,特点是各个步骤连续完成. 乘法规则可以推广到多于两个事件的有限情况。,【例2.1 位串和二进制代码】位串定义为诸 如0001、1101、1010这样的位的序列。位串用于编码详细的指令。一个符合集合的二进制代码给每一个符号指定一个不同的位串。考虑如果正好有2位，那么字母表中的多少字母可以被编码？ 答：2位的位串

3、存在四种可能，如下表所示：,2.1 乘法规则,2.1 乘法规则,【例2.2 DNA】DNA是由称为核苷酸的构件的串组成的。DNA是一个双链结构，其中的两个链是由特定的基之间的配对组合到一起的。 核苷酸中的每一个基是四种可能的化学物质中的一个：胸腺嘧啶T,胞嘧啶C，腺嘌呤A，鸟嘌呤G。 它确定蛋白质的氨基酸长链。有20种基本的氨基酸，DNA分子中的基序列将编码一种这样的氨基酸。 问：DAN分子串必须有多长才有足够多可能的基来编码20种不同的氨基酸呢？（即多少个元素序列才有个以上可能不同的序列？）,2.1 乘法规则,答：先考虑2-元素的DNA序列能否编码20种不同的基本氨基酸？即我们先考虑:有多少

4、个2-元素的DNA序列? 如右表所示，存在16种可 能的2-元素DNA序列第一 个元素有4种选择,而对应 于其中每一种选择，第二 种元素同样是4种选择。 所以，所有可能的2-元素 DNA序列为44=16种。,2.1 乘法规则,因为1620，所以2-元素序列不足以编码所有20种不同的基本氨基酸。 再考虑3-元素的DNA序列能否编码20种不同的基本氨基酸？即我们先考虑:有多少个3-元素的DNA序列? 同理，3-元素DNA序列第一个元素有4种选择,而对应于其中每一种选择，第二、三种元素同样是4种选择。 所以，所有可能的2-元素DNA序列为 444= =64种。即3个元素序列才有个以上可能不同的序列？

5、,2.2 加法规则,加法规则：独立的事件X，Y，完成它们的方法 数分别为x，y，则完成X或Y的方法数为x+y。 事件E1发生，发生，或者之一发生的数量：,完成某件事情有n类方法,在第一类方法中有m1种方法,在第二类方法中有m2种方法,依次类推,在第n类方法中有mn种方法, 则完成这件事共有N = m1+m2+mn种不同的方法,其中各类方法彼此独立. 加法规则可以推广到多于两个事件的有限情况。,2.2 加法规则,【例2.6 国会代表团】有100名参议员和435名众议员，要挑选一个代表团会见总统。如果这个代表团是由一名参议员和一名众议员组成的，那么有多少种不同的方法可以选出这样的代表团？ 答：根据

6、乘法规则，方案有：100435=43500 如果这个代表团是由一名参议员或者一名众议员组成的，那么答案又如何呢？ 答：100+435=535 种可能的代表团。这里用了加法规则,2.2 加法规则,【例2.8 BASIC和JAVA中的变量】程序设计语言BASIC的早期实现中的变量名是一个字母或者一个字母后面跟着一个字母或者一个字母后面跟着一个十进制数字，即数字09中的一个。有多少个可能的变量名呢？ 答：根据乘法规则，对后面两种情况的变量名分别有 2626=676和2610=260个 根据加法规则，总共存在26+676+260=962个,2.2 加法规则,JAVA程序设计语言的变量名长度从1到655

7、35个字符。每一个字符可以是一个字母（大写或小写字母）、一个下划线、一个美元符号或一个十进制数字，只是第一个字符不能是十进制数。有多少个可能的变量名呢？ 答：根据加法规则，可能的字符数量是26+26+1+10=64 因第一个字符不能是十进制数，所以有64-10=54 种可能。最后，通过加法和乘法规则，变量名数量是：,【练习1 】两批产品各50件,其中次品各5件,从这两批产品中各抽取1件 (1) 两件都不是次品的选法有多少种? (2) 只有一件次品的选法有多少种?,自己动手,解密,解: (1) 用乘法原理，结果为,(（2） 结合加法原理和乘法原理，得选法为:,【练习2 】六个引擎分列两排，要求引

8、擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。 解：第1步从特定引擎对面的3个中取1个有C(3,1)种取法，第2步从特定引擎一边的2个中取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。所以共有C(3,1)C(2,1)C(2,1)=12种方案。,自己动手,【练习3 】 S1,2,3,4, 1) 计算从S中取出两个不同元素的排列数 2）计算取可以重复的2个元素的排列数,自己动手,2.3 排列 permutation,n集合(n-net)：n个不同元素组成的集合 一个n集合的排列：是集合中元素按序排列 n-net的排列数

9、量：n! 例.9：如果有5个人参加面试，那么这5人接受面试的出场的可能次序的排列数量是多少？ 答：5!=54321=120 大,不便枚举 数n!可用 (n/e) 的计算来近似。使用S 近似n!称为斯特林近似(stirlingsapproximation),2.4 计算的复杂度,计算的复杂度：在运行程序之前，我们希望知道程序是否能在合理的时间内运行，且使用合理的存储量或内存量。为了衡量一个程序的运行成本，我们尝试计算一个成本函数或复杂度函数。 cost function, complexity 例如，我们也许要问处理两个n行、n列方阵的 乘积需要多少个操作？这个操作数量就是f(n)。 这里的通常

10、是输入实例的规模或者尺度,2.4 计算的复杂度,【例2.10 卖货郎问题】这是一个典型的组合优化问题。 一名卖货郎希望遍访n个不同的城市，在第一座城市开始他的工作旅程并到这里结束。他不关心到访城市的顺序，而是关心最小化旅程的总成本。假设从城市i到城市j的旅程成本为 。问题是要寻找一个计算最便宜路程的算法.一条路线的成本是该路线中的连接成本Cij的和,2.4 计算的复杂度,答：对于卖货郎问题，我们将牵涉到枚举算法：枚举所有可能的路线并计算每一条路线的成本，我们将尝试计算这一算法的复杂度，其中n是输入的大小，即城市的数量。假设对每一条路线，识别该路线及计算其成本都是可比较的，且要花费一个时间单位。

11、 现在，开始且结束于城市1的任意路线对应于余下的n-1个城市的一个排列。因此，存在 (n-1)! 条这样的路线，所以f(n)=(n-1)！个时间单位。我们已经证明这个数字非常大，当n=26，n-1=25时，我们已经证明f(n)非常大以至于通过计算机执行这一算法都是不可能的。 我们将在11.5节回到卖货郎问题。有趣的是，很多猜测问题中都出现卖货郎问题。 例子2.112.16给出实际应用中这一问题的若干变形。,2.4 计算的复杂度,【例2.11 ATM问题】银行有很多ATM，每一天信使都会逐台机器收集汇总计算机信息等。为了最小化所花费的时间，以什么样的顺序遍历这些机器呢？在实际中很多银行都会发生这

12、一问题。 ATM初期，第一批使用卖货郎算法解决这一问题的一家银行是波士顿的Shawmut Bank.,2.4 计算的复杂度,【例2.12 电话亭问题】每周一次，要遍历一个地区的每一个电话亭，收集硬币，为了最小化所花费的时间，应该以什么样的顺序遍历这些电话亭呢？这一问题亦可使用卖货郎算法解决。,2.4 计算的复杂度,【课堂练习】通过枚举法解决卖货郎问题。其中n=4,而且成本 是由下面的方阵给出：,等价与的问题,自己阅读的例子 例2.17 调度计算机系统城市配置 例.18 在文件中搜索搜索个关键字的列表来寻找某个人关键字以便存取该人文件。Worst-case complexity average-

13、case complexity,2.5 r排列,(1). r排列 (R-permutation of the n-set) -非重复排列（要求顺序）: 从 n个不同元素中,每次取出r个不同的元素C(n,r),按一定的顺序排成一列称为选排列, 所有排列的种数记作 P(n,r)=n!/(n-r)! 所以，当正整数r,n满足rn时，有：,r排列,【例2.19 CD播放器】CD 播放机有5个CD槽口，可按此顺序播放CD，现有24张CD，那么有多少种放入播放器插口的不同安排法？ 答：根据r排列公式：,引申,(2).非重复圆周排列（要求顺序） 从n个中取出m个 m个全不相同 m个元素放置在圆周上，（无头无

14、尾） 排列的个数为：,【练习】六个男子六个女子相间坐在圆桌一圈，坐法多少？,练习,引申,(3).相异元素可重排列： 从n个中每次取出m个 m个未必不同，可以相同 所有排列的个数：nm。 说明：m个位置，每次选n个中的一个放入该位置 换言之，当每元有n个选择时，m个元的排列取法数为nm。,2.6 子集,【例2.20 比萨问题】比萨店做广告称可提供500多种不同比萨，消费者怀疑。店内的任意下列9种配料的任意组合都有可能成为一种新比萨：香肠，蘑菇，胡椒粉，橄榄，意大利辣肠，凤尾鱼，腊肠，洋葱，咸肉。 问：这家比萨店在广告中说实话了吗？ (提示：通过简单地运用乘法规则来解答),2.6 子集,为了回答比

15、萨问题，我们先考虑集合a,b,c.我们问这个集合有多少个子集？ 方法一：枚举法。枚举所有可能的组合，我们发现存在8个这样的子集： ，a，b，c，a,b，a,c，b,c，a,b,c. 方法二：乘法规则。我们按步构建子集.首先，考虑包含或不包含元素a的情况.这存在2种选择.然后，考虑包含b或不包含b的情况.这也存在2种选择.最后，是包含c或不包含c的情况.仍有2种选择.根据乘法规则，3集合构建子集的总的方法数量为：,2.6 子集,类似地，4集合的子集的数量是： 所以，n集合的子集数量是： 这些考虑对比萨问题的解决有帮助吗？你联想到了什么？ 让我们来动手解决比萨问题吧(*_*) ,2.6 子集,解答

16、：我们可以把一个特定的比萨考虑成比萨配料组合集合的一个子集。另外，对于每一种配料，我们可以考虑包含它或不包含它。总之，我们看到存在总共 种可能的比萨。所以512500， 因此，这家比萨店没有做虚假广告。,2.7 r组合-combination,-组合：集合A中取出若干元素，不计顺序。 一个r-组合是某个元素的子集。 n元集合S的一个r组合：是指从S中取出r个元素的一种无序选择，其组合数记为 C(n,r)或 P(n,r) = C(n,r) P(r,r)。(Th. 2.1) C(n,r)将表示n集合的r组合的数量。,2.7 r组合,例如：从4个人中选出3个人组成一个委员会的方法数记为C(4,3),

17、假设这4个人分别是a、b、c、d 那么可能的委员会是： a,b,c，a,b,d，a,c,d，b,c,d 因此，C(4,3)=4 我们将证明有关C(n,r)的一些简单定理。 注意：如果nr,则C(n,r)=0.在这种情况下，不存 在n集合的r组合。因此，通常认为nr。 所以，本节中所以定理都假设nr。,2.7 r组合,你会证明了吗？,2.7 r组合,【例2.20 比萨问题】比萨店做广告称可提供500多种不同比萨，消费者怀疑。店内的任意下列9种配料的任意组合都有可能成为一种新比萨：香肠，蘑菇，胡椒粉，橄榄，意大利辣肠，凤尾鱼，腊肠，洋葱，咸肉。 问：求正好种不同配料的比萨数 求至多种不同浇头的比萨

18、数,2.7 r组合,答：正好种不同浇头的比萨数： C(9,3)84 至多种不同浇头的比萨数： C(9,) C(9,) C(9,) C(9,3)130,2.7 r组合,练习2： n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？ 解：把n个男、n个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘2,即方案数为2(n!)2个. 围成一个圆桌坐下，根据圆排列法则，方案数为2(n!)2/(2n)个.,2.7 r组合,练习3： 从n个人中选r个围成一圆圈，问有多少种不同的方案？ 解：圆排列:共有P(n,r)/r种不同的方案。,2.7 r

19、组合,(2)相异元素可重复的组合,从n个不相同的元素里，每次取出m个元素（可以重复）的组合。 此类组合的个数： S1,2,3,4时，尝试直接罗列此类组合 证明上述组合个数成立。 构造了一个一一映射。,2.7 r组合,求出根据已知条件所能作出的不同组合的种数。 组合计数的渐进值计算问题研究方向 基本，重要，简单等式：,2.7 r组合,练习：,2.8 概率,拉普拉斯在1812年出版的概率的理论一书中定义了概率(probability) 一个事件的概率：是表明该事件发生的可能的结果的数量除以可能结果的总数。 注意：只适合于事件发生所有结果均等的情形,2.8 概率,例2.8.1：概率应用于博弈，掷一个骰子，计算结