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

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