《排列与组合》PPT课件.ppt

1、2020/9/6,1,组合数学,郝聚涛 计算机系,2020/9/6,组合数学-上海理工大学,2,教材,组合数学 （第四版） ，卢开澄 卢华明 著， 清华大学出版社 ，2008 本书共分8章，内容包括: 排列与组合 递推关系与母函数 容斥原理与鸽巢原理 Burnside引理与Polya定理 区组设计 线性规划 编码简介 组合算法简介,考试,时间：第九周课内 形式：闭卷 内容：上课例题为主 成绩：平时+试卷成绩,2020/9/6,组合数学-上海理工大学,3,2020/9/6,组合数学-上海理工大学,4,1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Com

2、binatorics）一词。,1646.7.1.1716.11.14.）德国最重要的自然科学家、数学家、物理学家、历史学家和哲学家，一个举世罕见的科学天才，和牛顿同为微积分的创建人。 1664年1月，莱布尼茨完成了论文论法学之艰难，获哲学硕士学位。 1665年，莱布尼茨向莱比锡大学提交了博士论文论身份，1666年，审查委员会以他太年轻(年仅20岁)而拒绝授予他法学博士学位 ，1667年2月，阿尔特多夫大学授予他法学博士学位，还聘请他为法学教授。 1700年2月，他还被选为法国科学院院士。至此，当时全世界的四大科学院：英国皇家学会、法国科学院、罗马科学与数学科学院、柏林科学院都以莱布尼次作为核心

3、成员。,2020/9/6,组合数学-上海理工大学,5,始创微积分 高等数学上的众多成就 计算机科学贡献 1673年莱布尼茨特地到巴黎去制造了一个能进行加、减、乘、除及开方运算的计算机 率先为计算机的设计，系统提出了二进制的运算法则，为计算机的现代发展奠定了坚实的基础 丰硕的物理学成果 充分地证明了“永动机是不可能”的观点 哲学贡献单子论 多才多艺 1693年，莱布尼茨发表了一篇关于地球起源的文章，后来扩充为原始地球一书 1677年，他写成磷发现史，对磷元素的性质和提取作了论述 在气象学方面。他曾亲自组织人力进行过大气压和天气状况的观察 1691年，莱布尼茨致信巴本，提出了蒸汽机的基本思想。 1

4、677年，莱布尼茨发表通向一种普通文字，以后他长时期致力于普遍文字思想的研究，对逻辑学、语言学做出了一定贡献。今天，人们公认他是世界语的先驱 ,2020/9/6,组合数学-上海理工大学,6,组合数学概述,组合数学（combinatorial mathematics），又称为离散数学。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面问题。 组合数学主要内容有组合计数、组合设计、组合矩阵、组合优化等。 组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学即算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对

5、象的科学恰恰就是组合数学。,2020/9/6,组合数学-上海理工大学,7,典型问题,地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径

6、算法求解。这也是图论的问题。 任务分配问题（也称婚配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？这是线性规划的问题。,2020/9/6,组合数学-上海理工大学,8,第一章 排列与组合,主要内容： 一、排列与组合 二、排列组合的生成算法 三、组合意义的解释与应用举例,2020/9/6,组合数学-上海理工大学,9,一、排列与组合,加法法则和乘法法则 一一对应 排列、组合 圆周排列 可重排列 可重组合 不相邻的组合,2020/9/6,组合数学-上海理工大学,10,1. 加法法则与

7、乘法法则,加法法则：设具有性质A的事件有m个，具有性质B的事件有n个，则具有性质A或B的事件有m+n个。,若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。,集合论语言：,基本假设：性质A和性质B是无关的两类。,2020/9/6,组合数学-上海理工大学,11,例1 某班选修企业管理的有18人，不选的有10人，则该班共有 18 + 10 = 28 人。,例2 假设要从北京坐飞机或者火车或者客车到上海。北京每天到达上海的飞机有 5 个航班，火车有 7 趟，客车有 10 趟， 则每天由北京到达上海的旅行方式有 5 + 7 + 10 = 22 种。,2020/9

8、/6,组合数学-上海理工大学,12,乘法法则：设具有性质A的事件有m个，具有性质B的事件有n个，则具有性质A和B的事件有mn个。,若 |A| = m , |B| = n , AB = (a,b) | aA,bB , 则 | AB | = mn 。,集合论语言：,例3 从A到B有三条道路，从B到C有两条道路，则从A经B到C有 32 = 6 条道路。,加法法则：得到事件通过两种不同的方法。,乘法法则：得到事件通过两个步骤。,2020/9/6,组合数学-上海理工大学,13,例4 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有 42 = 8 种着色方

9、案。,若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是 4 4 = 16， 而只有 4 3 = 12 种。,2020/9/6,组合数学-上海理工大学,14,例5 (1) 求小于10000的含1的正整数的个数； (2) 求小于10000的含0的正整数的个数。,(1) 小于10000的不含1的正整数可看做4位数，但 0000除外. 故有999916560个。 含1的有：99996560=3439个，,另：全部4位数有104个，不含1的四位数有94个， 含1的4位数为两个的差：10494= 3439个。,2020/9/6,组合数学-上海理工大学,15,99997380=2619.,

10、(2)“含0”和“含1”不可直接套用。 0019含1但不含0。,不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个。,不含0小于10000的正整数有,含0小于10000的正整数有,2020/9/6,组合数学-上海理工大学,16,43560；,(2) 6318,个位数有5种取法，千位数有8种取法，百位，十位各有8，7种取法。58872240。,例6 (1) n=73*112*134，求除尽n的数的个数；,(2) n=73*142，求除尽n的数的个数；,例7 在1000和9999之间有多少每位上的数字均不同的奇数？,2020/9/6,组合数学-上海理工大学,17,例8 由a,b,

11、c,d,e这5个字符，从中取6个构成字符串，要求 (1) 第1，6个字符必为子音字符b，c，d；(2) 每个字符串必有两个母音字符a或e，且两个母音字符不相邻；(3) 相邻的两个子音字符必不相同。求满足这样的条件的字符串的个数。,由条件(1)，两个母音字符的位置不能在1，6， 又由条件(2)，位置只能是(2,4),(2,5)和(3,5)之一。 对每种格式，母音22，相邻子音32，其他两个 子音33。因此答案为 3（223233）=648。,课堂练习,2020/9/6,组合数学-上海理工大学,18,abcde,2020/9/6,组合数学-上海理工大学,19,如我们说A集合有n个元素 |A|=n，

12、无非是建立了将A中元与1,n元一一对应的关系。,在组合计数时往往借助于一一对应实现模型转换。,比如要对A集合计数，但直接计数有困难，于是可 设法构造一易于计数的B，使得A与B一一对应。,2. 一一对应,“一一对应”概念是一个在计数中极为基本的概 念。一一对应既是单射又是满射。,2020/9/6,组合数学-上海理工大学,20,一种常见的思路是按轮计场，费事。 另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。,例9 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？,2020/9/6,组合数学-上海理工大学,21,可以先计算对角线的

13、个数，然后计算交点，但是存在在多边形内无交点的情形，比较复杂。,可以考虑对应关系：多边形内交点to多边形四个顶点。,可以证明这是一一映射（映射，单且满）。,例10 设凸n边形的任意三条对角线不共点，求对角线在多边形内交点的个数。,2020/9/6,组合数学-上海理工大学,22,一一对应,例 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 丙烷,2020/9/6,组合数学-上海理工大学,23,一一对应,H | H C H

14、 | 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个顶点是叶子。 对于这样结构的每一棵树，就对应有一种特定的化合物。,构造化合物转化为图论问题，计算符合上述条件的树的数目，便可确定对应的不同化合物的数目,2020/9/6,组合数学-上海理工大学,24,1.2 一一对应,例 (Cayley定理) n个有标号的顶点的树的数目等于 。 两个顶点的树是唯一的。12 n3时，数的数目3。

15、123，132，213 思路：n点树一一对应长度n-2序列 n个字母的长度n-2序列的数目是,2020/9/6,组合数学-上海理工大学,25,一一对应, | | ,4 1 2 5 3,逐个摘去标号最小的叶子，叶子的相邻 顶点(不是叶子，是内点)形成一个序列， 序列的长度为n-2,例,给定一棵有标号的树,边上的标号表示摘去叶 的顺序。(摘去一个叶子 相应去掉一条边),第一次摘掉，为相邻的顶点， 得到序列的第一个数3 以此类推，消去23465，得到序列31551, 长度为72 = 5，这是由树形成序列的过程。,2020/9/6,组合数学-上海理工大学,26,一一对应 （复杂）,由序列形成树的过程：

16、,由序列31551得到一个新序列111233455567,生成的过程是首先将31551排序得到11355， 因为序列31551的长度为5， 得到按升序排序的序列1234567， 序列的长度为5+2(即n)， 然后将11355按照大小插入到序列1234567中， 得到111233455567,然后将两个序列排在一起,31551 111233455567,2020/9/6,组合数学-上海理工大学,27,一一对应,31551 111233455567,1551 1113455567,551 11455567,51 115567,1 1157,17,第一步推导：将上下两个序列同时去掉上 行序列的第一个

17、元素3(用蓝色表示)，去掉 下行序列的第一个无重复的元素2(用红色 表示)。生成一条边()。,由上序列确定3（蓝色）， 再确定2（红色），在下序列最小无重元， 于是生成边23。（并消除红蓝色点。） 依此类推，减到下面剩最后两个元素，这 两个元素形成最后一条边。最后形成树。 （生成边的序列23，13，45，56，15，17）,2020/9/6,组合数学-上海理工大学,28,1.2 一一对应,上述算法描述：,给定序列b=(b1b2bn-2) 设a=(123n-1 n)将b的 各位插入a,得a,对( )做操作。 a是2n-2个元的可重非减序列。,b a,操作是从a中去掉最小无重元，设为a1, 再从b

18、和a中各去掉一个b中的第一个元素，设为b1， 则无序对(a1,b1)是一条边。 重复这一操作，得n-2条边，最后a中还剩一条边， 共 n-1条边，正好构成一个树。 b中每去掉一个元，a中去掉2个元。,2020/9/6,组合数学-上海理工大学,29,1.2 一一对应,由算法知由树T得b=(b1b2bn-2) ， 反之，由b可得T。 即 f：Tb 是一一对应。 由序列确定的长边过程是不会形成回路的。 因任意长出的边 (u , v) 若属于某回路，此回路中必有一条最早生成的边，不妨就设为 (u , v) ，必须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成

19、与u有关的边了，故由( )得到的边必构成一个n个顶点的树。,b a,2020/9/6,组合数学-上海理工大学,30,证明 2,3 1 5 5 1 1 2 3 4 5 6 7 第一个不出现在上面的数 2-3 3-1 4-5 6-5 5-1 1-7, | | ,2020/9/6,组合数学-上海理工大学,31,1.2 一一对应,证 由一棵n个顶点的树可得到一个长度为n2的序列，且不同的树对应的序列 不同，因此 。 对n用归纳法可证 反之，由一个长度为n2的序列(每个元素为1 n 的一个整数)，可得到一棵树，且不同的序列对应的树是不同的，因此,2020/9/6,组合数学-上海理工大学,32,排列的典型

20、例子是取球模型：从n个不同的球中,取出r个,放入r个不同的盒子里，每盒1个。 第1个盒子有n种选择,第2个有n-1种选择，第r个有n-r+1种选择。故由乘法法则有,3. 排列、组合,定义：从 n 个不同的元素中，取 r 个不重复的元素，按次序排列，称为从 n 个中取 r 个的无重排列。排列的个数用 P(n,r) 表示。 当 r = n 时称为全排列。,P(n,r) = n(n-1)(n-r+1) = n!/(n-r)!,P(n,n)=n!,2020/9/6,组合数学-上海理工大学,33,例11 由5种颜色的星状物，20种不同的花排列成如下图案：两边是星状物，中间是3朵花，问共有多少种这样的图案

21、？,两边是星状物，从五种颜色的星状物中取两个的排列的排列数是 P(5,2)=20。,20种不同的花取3种排列的排列数是,根据乘法法则得图案数为,P(20,3)=20 19 18=6840。,20 6840=136800。,2020/9/6,组合数学-上海理工大学,34,接上例，若A单位的2人排在队伍两端，B单位的3人不能相邻，问有多少种不同的排列方案？(练习),B单位3人按一个元素参加排列，P(8,8)P(3,3)。,A单位的人排法固定后A*A*A*A*A*A*A，B单位第一人有6种选择，第二人有5种，第三人有4种，因此答案为P(7,7)654。,例12 A单位有7名代表，B单位有3位代表，排

22、成 一列合影要求B单位的3人排在一起，问有多少种 不同的排列方案。,2020/9/6,组合数学-上海理工大学,35,例13 试求由1,3,5,7组成的所有不重复出现的整数的总和。,这样的整数可以是1位数,2位数,3位数,4位数，若设,是 i 位数的总和，则,S=S1+S2+S3+S4,S1=1+3+5+7=16；,于是我们只需要计算Si即可。,2020/9/6,组合数学-上海理工大学,36,S4=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10 +6(1+3+5+7)=96000+9600+960+96=106656；,S=16+528+10656+10665

23、6=117856。,S2=3(1+3+5+7)10+3(1+3+5+7)= 480+48=528；,S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7) =9600+960+96=10656；,2020/9/6,组合数学-上海理工大学,37,组合的个数用 C(n,r) 表示。,或者用 表示。,定义： 从 n 个不同元素中取 r 个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从 n 个中取 r 个的无重组合。,C(n,r)=0，若n r。,2020/9/6,组合数学-上海理工大学,38,故有,C(n,r)r!=P(n,r)，,C(n,r)=P(n,r)/r!，

24、,从n个不同的球中,取出r个,放入r个相同的盒子里,每盒1个，这是从n个中取r个的组合的模型。 若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。,2020/9/6,组合数学-上海理工大学,39,(2) C(5,2)+C(7,2)+C(10,2)=10+21+45=76；,(1) 57+510+710=155;,(3) 155+76=231=C(5+7+10,2)。,例14 有5本不同的日文书，7本不同的英文书，10本不同的中文书。 (1) 取2本不同文字的书； (2) 取2本相同文字的书； (3) 任取两本书。,2020/9/6,组合数学-上海理工大学,40,例1

25、5 甲和乙两单位共11个成员，其中甲单位7人，乙单位4人，拟从中组成一个5人小组： (1) 要求包含乙单位恰好2人； (2) 要求至少包含乙单位2人； (3) 要求乙单位某一人与甲单位特定一人不能同时在这个小组。 试求各有多少种方案。,(1) C(4,2)C(7,3)；,(2) C(4,2)C(7,3)+C(4,3)C(7,2)+C(4,4)C(7,1)；,(3) C(10,5)+C(9,4)，或C (11,5)-C(9,3)。,2020/9/6,组合数学-上海理工大学,41,将1,300分成3类：,A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,29

26、9, C=i|i3(mod 3)=3,6,9,300。,例16 从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？（练习）,要满足条件，有四种情形：,1. 3个数同属于A; 2. 3个数同属于B; 3. 3个数同属于C; 4. A,B,C各取一数。,故共有,3C(100,3)+1003=485100+1000000=1485100。,2020/9/6,组合数学-上海理工大学,42,解1：a1选择其同伴有7种可能， 选定后,余下6人中某一人选择其同伴只有5种可能， 余下4人，其中某1人有3种选择可能， 在余下的2人只好配成一对，无法选择， 故共有,N=753=105。,例17

27、 假定有a1,a2,a3,a4,a5, a6, a7,a8这8位成员，两两配对分成4组，试问有多少种方案？（练习）,2020/9/6,组合数学-上海理工大学,43,解2：分成4组。第一组取法为C(8,2)， 余下6人，第二组取法为C(6,2)， 第三组取法为C(4,2)， 剩下为第四组。 但4组的顺序是重复的，因此答案为 C(8,2)C(6,2)C(4,2)/P(4,4)=105。,解3：8人全排列有P(8,8)。分成4组。 每组中2人交换是重复的，重复数为2222， 另外4组的顺序也是重复的，重复数为P(4,4)， 因此答案为 P(8,8)/(2222P(4,4)=105。,2020/9/6

28、,组合数学-上海理工大学,44,一个进站方案可以表示成：00011001010100， 其中“0”表示车，“1”表示间隔。 其中“0”是不同元，“1”是相同元。 给“1”这6个入口只用5个间隔。 任意进站方案可表示成上面14个元素的一个排列。,例18 某广场有6个入口，每个入口每次只能通过一辆汽车，现有9辆车要开进广场，有多少种入场方案？,2020/9/6,组合数学-上海理工大学,45,解2：在14个元的排列中先确定“1”的位置，有C(14,5)种选择， 再确定车的位置，有9！种选择。 故 C(14,5)9! 即为所求。,解3：实际上相当于14个位置中选取9辆汽车的排列，即为 P(14,9)。

29、,解1：标号可产生5!个14个元的全排列。 若设x为所求方案，则 x 5!=14!。 故 x=14!/5!=726485760。,2020/9/6,组合数学-上海理工大学,46,注意到，每个交点只有两个对角线通过，对应了4个 顶点所组成的一个组合，不同的交点对应的组合也 不相同。 故共有C(n,4)个交点。,例19 一个凸 n 边形，它的任何3条对角线都不交于同一点，问它的所有对角线在凸 n 边形内部有多少个交点。,2020/9/6,组合数学-上海理工大学,47,定义：从 n 个不同的数中不重复的取出取出 r 个沿一圆周排列，称为一个圆周排列。 所有的r-圆周排列数记为 Q(n,r)（计算公式

30、？）。,注意圆周排列与排列的不同之处在于圆周排列首尾相邻。 如a、b、c、d的4种不同排列 abcd, dabc, cdab, bcda, 在圆周排列中都是一个排列。,4. 圆周排列,2020/9/6,组合数学-上海理工大学,48,以4个元素为例,Q(n,r)=P(n,r)/r , 2rn Q(n,n)=(n-1)!,从 n 个中取 r 个的圆周排列的排列数为：,2020/9/6,组合数学-上海理工大学,49,若无要求，则为Q(8,8)；,若要求蓝色珠子一起，则为Q(6,6)P(3,3)；,若要求蓝色珠子不相邻，则为Q(5,5)543。,例20 5颗红珠子，3颗蓝珠子装在圆板的四周，试问有多少

31、种方案？若要求蓝色珠子不相邻，又有多少种排列方案？蓝色珠子在一起呢？,2020/9/6,组合数学-上海理工大学,50,例21 5对夫妇出席一个宴会，围一圆桌坐下，试问 有几种不同的坐法？要求每对夫妇相邻又如何？,若无限制，则为Q(10,10)；,若要求相邻，则为Q(5,5)22222。,2020/9/6,组合数学-上海理工大学,51,5. 可重排列,定义：多重集是指元素可以多次出现的集合，即元素可以重复。我们把某个元素 ai 出现的次数ni(ni=0,1,2,)叫做该元素的重复数。 通常把含有 k 种不同元素的多重集 S 记作,2020/9/6,组合数学-上海理工大学,52,定理：设多重集 则 S 的r-(可重)排列