组合数学ppt课件--第一章排列与组合讲解

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,组合数学,课时：36学时,成绩分配：平时成绩30分，期末考试成绩70分。,平时成绩取得方式：安排5次课堂测验，每次6分。,课件邮箱:hjh20070826,密码:20070826,1,组合数学课时：36学时 成绩分配：平时成绩30,组合数学的应用范畴,从广义上讲组合数学就是离散数学,组合数学研究满足一定条件的组合模型的情况:,(1)存在性：,(2)计数：,(3)有哪些？,(4)哪些最优？,组合数学与,算法、密码学、编码理论、数据压缩等计算机方向密不可分。,*,2,组合数学的应用范畴从广义上讲组合数学就是离散数学,选用教材,组合数学,(第四版),卢开澄 卢华明 著,清华大学出版社,3,选用教材组合数学3,组合数学的应用范畴,第一章:排列与组合,第二章:递推关系与母函数,第三章:容斥原理与鸽巢原理,第四章:Burnside引理与Polya定理,第五章:区组设计,第六章:线性规划,第七章:编码简介,第八章:组合算法简介,4,组合数学的应用范畴 第一章:排列与组合4,参考教材,组合数学,R,ichard A. Brualdi 著,冯舜玺等译,机械工业出版社,5,参考教材组合数学5,参考教材,组合数学及其算法,杨振生,中国科学技术大学出版社,6,参考教材组合数学及其算法6,第一章：排列与组合,1.1 基本计数法则,1.2 一一对应:,1.3 排列与组合,1.4 圆周排列,1.5 排列的生成算法,1.6 允许重复的组合与不相邻的组合,1.7 组合意义的解释,1.8 应用举例,1.9 *Stirling公式,7,第一章：排列与组合1.1 基本计数法则7,1.1基本计数法则,1、加法法则:,如果具有性质A的事件有m个，性质B的事件有n个，则具有性质A或B的事件有m+n个。,A和B是性质无关的两个事件。,8,1.1基本计数法则1、加法法则:A和B是性质无关的两个事件。,2、乘法法则:,若具有性质A的事件有m个，具有性质B的事件有n个，则具有,性质A及B,的事件有mn个,1.1基本计数法则,9,2、乘法法则:1.1基本计数法则9,例1.1 若从合肥到南京有2条路可走，从南京到上海有3条路可走，从上海到杭州有2条路可走，问从合肥经南京、上海到杭州有多少路可走？,1.1基本计数法则,10,例1.1 若从合肥到南京有2条路可走，从南京到上海有3条路可,例1.2：用乘法法则解释8卦及64卦。,解：1、太极生两仪,3、四象生八卦,000，001,，010, 011,100,，101,，110, 111,2、两仪生四象,00，01,，10，11；,1.1基本计数法则,11,例1.2：用乘法法则解释8卦及64卦。 解：1、太极生,例1.3：长度为n的0,1符号串的数目?,例1.4 人类DNA链的长度为2.110,10,链上每一位由T,C,A,G四种化合物组成,求人类DNA链的可组成数目。,1.1基本计数法则,12,例1.3：长度为n的0,1符号串的数目? 例,例1.5：求布尔函数f(x,1,x,2,x,n,)的数目,以n=2为例：,f(x,1,x,2,)有四种方式：f(0,0),f(0,1),f(1,0),f(1,1)。,1、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=0。,2、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=1。,对应着长度为2,2,的字符串，每一位都可以取0或1;,乘法：2,2,2,自变量数为n个时：2,2,n,1.1基本计数法则,*,13,例1.5：求布尔函数f(x1,x2,xn)的数目以n=2,1、从n个数中找出最大值问题,2、n个人参加单淘汰赛，最后产生冠军的过程。,1.2 一一对应,14,1、从n个数中找出最大值问题1.2 一一对应14,例1.6：求n,2,个人站成一排和站成n排（方阵）的方案数，并比较两种方案数的大小？,解：9个人站成一排的方案数是9!，,设a,1,a,2,a,3,a,4,a,5,a,6,a,7,a,8,a,9,是9个人的一排，,可构成一个方阵,a,1,a,2,a,3,a,4,a,5,a,6,a,7,a,8,a,9,给定一个方阵,b,1,b,2,b,3,b,4,b,5,b,6,b,7,b,8,b,9,也唯一确定一排b,1,b,2,b,3,b,4,b,5,b,6,b,7,b,8,b,9,因此这两种站位方式的方案数一样多，都是9!,1.2 一一对应,15,例1.6：求n2个人站成一排和站成n排（方阵）的方案数，并比,例1.6：求n,2,个人站成一排和站成n排（方阵）的方案数，并比较两种方案数的大小？,9个人站成方阵的方案数为：,C(9,3)3!C(6,3)3!C(3,3)3!,1.2 一一对应,16,例1.6：求n2个人站成一排和站成n排（方阵）的方案数，并比,定理1.1 n个有标号1,2,n的顶点的树的数目等于n,n-2,。（n=2）,1,2,5,3,4,设一棵树的顶点集为A,1、从中找到编号最小的叶子结点，去掉该叶子结点a,1,及其邻接边(a,1,b,1,)。,2、重复以上过程。只到剩一条边为止。,(1,2),(4,3),(3,2),这棵树对应序列（2，3，2）,一个棵对应序列B=b,1,b,2,b,3,b,n-2,而且是唯一的,1.2 一一对应,17,定理1.1 n个有标号1,2,n的顶点的树的数目,1,2,5,3,4,树的顶点集合为12345,这棵树对应序列（2，3，2）,任给一个序列Bb,1,b,2,b,3,b,n-2,1、从A找到最小的不属于B的元素,设为a,1,与b,1,连接，从A中去掉a,1,，从B中去掉b,1,.,2、重复以上过程只到B为空，A中剩余两个,3、连接剩余的两个顶点。,1.2 一一对应,*,18,12534 树的顶点集合为12345 这棵树对应序列（2,1.3：排列与组合,1、排列的定义：设A=a,1,a,2,a,n,是n个不同的元素的集合，任取A中r个元素按顺序排成一列，称为从A中取r个的一个排列，r满足0rn。,从n个不同的球中取一个球放在第一个盒子中，,从余下的n-1个球中取一个球放在第二个盒子中，,从余下的n-(r-1)个球中取一个放在第r个盒子中。,(1),(2),(3),(),(r),根据乘法法则：,P(n,r)=n(n-1)(n-r+1)=n!(n-r)!,19,1.3：排列与组合 1、排列的定义：设A=a1,a2,全排列:P(n,n)=n(n-1)21=n!,1.3：排列与组合,2、组合的定义：当从n个不同元素中取出r个而不考虑它的顺序时,称为从n中取r个的组合,其数目记为C(n,r)。,公式：从n中取r的组合数记作C(n,r),从n中取r的排列数是P(n,r)。,C(n,r)=P(n,r)/r!,=n!/r!(n-r)!,二者之间的关系:,20,全排列:P(n,n)=n(n-1)21=n!1.3：排列,第一章：排列与组合,排列可以看作n个不同的元素取r个放进r个不同的盒子的放法.,组合可以看作n个不同的元素,取r个,放进r个相同的盒子的放法.,公式1：C(n,r)=C(n,n-r),21,第一章：排列与组合 排列可以看作n个不同的元素,从5个元素中取3个进行排列的算法：,int a5=1,2,3,4,5,b3；,for(i=0;i5;i+),b0=ai;,for(j=0;j5;j+),if (j=i) continue;,else b1=aj;,for(k=0;k5;k+),if(k=i|k=j) continue;,else b2=ak;,打印b,1.3：排列与组合,22,从5个元素中取3个进行排列的算法：1.3：排列与组合,例1.7:由5种颜色的星状物,20种不同的花共25个元素中任取5个排成如下图案：两边是星状物,中间是3朵花，问共有多少种这样的图案？,解1：52019184=136800,20种不同的花取3种排列的排列数为：,P(20,3)=20!/17!=20*19*18=6840,根据乘法法则，共有图案数为：,6840*20=136800,解2：5种颜色的星状物取两个排列的排列数为,P(5,2)=5!/3!=5*4=20,1.3：排列与组合,23,例1.7:由5种颜色的星状物,20种不同的花共2,1.8 随机地选择n个人，求n个人至少有两人生日相同的概率(不考虑润年),解:,n个人生日不同的方案数是:,365*364*(365-n+1)=P(365,n),n个人生日的总方案数是:,365,n,至少有两人生日相同的概率:,1-P(365,n)/365,n,1.3：排列与组合,24,1.8 随机地选择n个人，求n个人至少有两人生日,1.8 随机地选择n个人，求n个人至少有两人生日相同的概率(不考虑润年),解:,思路：任选两人，使其生日相同，其它任选。,至少有两人生日相同的概率:,C(365,1)C(n,2)365,n-2,/365,n,1.3：排列与组合,*,对还是错？,25,1.8 随机地选择n个人，求n个人至少有两人生日,1.4：圆周排列,定义：在排列中，如果我们不横排而是将各元素排列在一个圆周上，那么我们称这种排列方式为圆周排列。,在排列中1234,2341,3412,4123为四个不同的排列，而在圆排列中这些排列是一个.,规定相对位置不变算一个排列。,26,1.4：圆周排列 定义：在排列中，如果我们不横排而,将从n中取r个作圆排列的排列数记作Q(n,r)。,从n中取r个作排列，与圆排列相比，重复了r倍；,公式：Q(n,r)=P(n,r)/r，,Q(n,n)=P(n,n)/n=n!/n=(n-1)!,1.4：圆周排列,Q(n,r)=P(n,r)/r=n!/r(n-r)!,27,将从n中取r个作圆排列的排列数记作Q(n,r)。从n中取r个,例1.19：5颗不同的红色珠子，3颗不同的蓝色珠子装在圆板的四周,试问有多少种方案？若蓝色珠子不相邻又有多少种排列方案？蓝色珠子在一起又如何？,解：(1)Q(8,8)=P(8,8)/8=7!。,(3)蓝色珠子在一起,Q(6,6)3!=5!3!。,(2) 蓝色珠子不在一起。,首先5颗不同的红色珠子作圆排列，共有,Q(5,5)=4!，,3颗不同的蓝色珠子排在红色珠子中间,4!543,1.4：圆周排列,*,28,例1.19：5颗不同的红色珠子，3颗不同的蓝色珠子,例1.20：5对夫妇出席一宴会，围一圆桌而坐，试问有几种不同的方案？若要求每对夫妻相邻又有多少种方案?,解： 1）座位无限制,Q(10,10)=P(10,10)/10=10!/10=9!=362880,共有362880种方式。,2）夫妇相邻而坐,首先可以将一对夫妇作为一个元素来看待，共有Q(5,5)=P(5,5)/5=24。,但夫妇可以交换坐位，5对夫妇共有2,5,种方式。,根据乘法法则：若夫妻相邻而坐，共有,242,5,=2432=768种方式。,1.4：圆周排列,*,29,例1.20：5对夫妇出席一宴会，围一圆桌而坐，试,第一章：排列与组合,多重集的排列,设S是一个多重集，有K个不同类型的元素，各元素的重复分别为n,1,n,2,n,k,n=n,1,+n,2,+n,k,则S的排列数为:,30,第一章：排列与组合 多重集的排列 设S是一,第一章：排列与组合,证明：给定多重集S，有k种类型的元素，比如说a,1,a,2,a,3,a,k,且分别有重数n,1,n,2,n,k,元素的总个数n=n,1,+n,2,+n,k,现在存在n个位置,我们要在n个位置放S的一个元素,首先要确定哪些位置放a,1,的元素,共有,剩下n-n,1,个位置, a,2,的元素,共有,.,剩下n-n,1,-n,k-1,个位置, a,k,的元素,共有,31,第一章：排列与组合 证明：给定多重集S，有k种类型的元素，,第一章：排列与组合,根据剩法法则:,S的排列的总数,32,第一章：排列与组合 根据剩法法则: S的排列的总数32,练习题,1、求10,40,和20,30,的公因数的数目。,解：10,40,=2,40,5,40,，20,30,=2,60,5,30,C(41,1)*C(31,1),33,练习题 1、求1040和2030的公因数的数目。,2、试证n,2,的整除数的数目是奇数。,练习题,34,2、试证n2的整除数的数目是奇数。练习题34,1.13、有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一组的最大数。,设取的第一组数有a个,第二组有b个,要求第一组数中最小数大于第二组中最大的，,即只要取出一组m个数(设m=a+b),从大到小取a个作为第一组,剩余的为第二组。,此时方案数为C(n,m)。,从m个数中取第一组数共有m-1中取法。,(m-1)C(n,m),练习题,35,1.13、有n个不同的整数，从中取出两组来，要求第1组的,练习题,*,36,练习题*36,第1章：游戏中碰到的题目：,1、中国象棋将帅问题,2、一摞烙饼的排序,3、买书问题,4、快速找出故障机器,5、饮料供货,6、光影切割问题,7、小飞的电梯调度算法,8、高效率地安排见面会,9、双线程高效下载,.,编程之美-微软技术面试心得,37,第1章：游戏中碰到的题目：编程之美-微软技术面试心得3,编程之美-微软技术面试心得,第2章：数字之魅,1、求二进制数中1的个数,2、不要被阶乘吓倒,3、寻找发帖“水王”,4、1的数目,5、寻找最大的K个数,6、最大公约数问题,7、找符合条件的整数,8、斐波那契（Fibonacci）数列,.,38,编程之美-微软技术面试心得第2章：数字之魅38,编程之美-微软技术面试心得,第3章结构之法,1、字符串移位包含的问题,2、电话号码对应英语单词,3、计算字符串的相似度,4、从无头单链表中删除节点,5、最短摘要的生成,.,8、求二叉树中节点的最大距离,9、重建二叉树,10、分层遍历二叉树,39,编程之美-微软技术面试心得第3章结构之法39,编程之美-微软技术面试心得,第4章数学之趣,1、金刚坐飞机问题,2、瓷砖覆盖地板,3、买票找零,4、点是否在三角形内,5、桶中取黑白球,6、蚂蚁爬杆,.,*,40,编程之美-微软技术面试心得第4章数学之趣*40,