组合数学：排列与组合省公开课一等奖全国示范课微课金奖课件

组合数学课时：36课时成绩分配：平时成绩30分，期末考试成绩70分。平时成绩取得方式：安排5次课堂测验，每次6分。课件邮箱:hjh0826@163.com密码:08261第1页组合数学应用范围从广义上讲组合数学就是离散数学组合数学研究满足一定条件组合模型情况:(1)存在性：(2)计数：(3)有哪些？(4)哪些最优？组合数学与算法、密码学、编码理论、数据压缩等计算机方向密不可分。****2第2页选取教材组合数学(第四版)卢开澄卢华明著清华大学出版社3第3页组合数学应用范围第一章:排列与组合第二章:递推关系与母函数第三章:容斥原理与鸽巢原理第四章:Burnside引理与Polya定理第五章:区组设计第六章:线性规划第七章:编码介绍第八章:组合算法介绍4第4页参考教材组合数学RichardA.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第7页1.1基本计数法则1、加法法则:假如含有性质A事件有m个，性质B事件有n个，则含有性质A或B事件有m+n个。A和B是性质无关两个事件。8第8页2、乘法法则:若含有性质A事件有m个，含有性质B事件有n个，则含有性质A及B事件有mn个1.1基本计数法则9第9页例1.1若从合肥到南京有2条路可走，从南京到上海有3条路可走，从上海到杭州有2条路可走，问从合肥经南京、上海到杭州有多少路可走？1.1基本计数法则10第10页例1.2：用乘法法则解释8卦及64卦。解：1、太极生两仪

3、四象生八卦

000，001，010,011100，101，110,111

2、两仪生四象

00，01，10，11；1.1基本计数法则11第11页例1.3：长度为n0,1符号串数目?例1.4人类DNA链长度为2.1×1010,链上每一位由T,C,A,G四种化合物组成,求人类DNA链可组成数目。1.1基本计数法则12第12页例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;乘法：2^22自变量数为n个时：2^2n1.1基本计数法则*13第13页1、从n个数中找出最大值问题2、n个人参加单淘汰赛，最终产生冠军过程。1.2一一对应14第14页例1.6：求n2个人站成一排和站成n排（方阵）方案数，并比较两种方案数大小？解：9个人站成一排方案数是9!，设a1a2a3a4a5a6a7a8a9是9个人一排，可组成一个方阵a1a2a3a4a5a6a7a8a9给定一个方阵b1b2b3b4b5b6b7b8b9也唯一确定一排b1b2b3b4b5b6b7b8b9所以这两种站位方式方案数一样多，都是9!1.2一一对应15第15页例1.6：求n2个人站成一排和站成n排（方阵）方案数，并比较两种方案数大小？9个人站成方阵方案数为：C(9,3)3!C(6,3)3!C(3,3)3!1.2一一对应16第16页定理1.1n个有标号1,2,…,n顶点树数目等于nn-2。（n>=2）12534设一棵树顶点集为A1、从中找到编号最小叶子结点，去掉该叶子结点a1及其邻接边(a1,b1)。2、重复以上过程。只到剩一条边为止。(1,2),(4,3),(3,2)这棵树对应序列（2，3，2）一个棵对应序列B=b1b2b3…bn-2而且是唯一1.2一一对应17第17页12534树顶点集合为12345这棵树对应序列（2，3，2）任给一个序列B{b1,b2,b3,…,bn-2}1、从A找到最小不属于B元素,设为a1,与b1连接，从A中去掉a1，从B中去掉b1.2、重复以上过程只到B为空，A中剩下两个3、连接剩下两个顶点。1.2一一对应*18第18页1.3：排列与组合1、排列定义：设A={a1,a2,…,an}是n个不一样元素集合，任取A中r个元素按次序排成一列，称为从A中取r个一个排列，r满足0≤r≤n。从n个不一样球中取一个球放在第一个盒子中，从余下n-1个球中取一个球放在第二个盒子中，…………………从余下n-(r-1)个球中取一个放在第r个盒子中。(1)(2)(3)(…)(r)依据乘法法则：P(n,r)=n(n-1)…(n-r+1)=n!／(n-r)!19第19页全排列:P(n,n)=n(n-1)…2×1=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第20页第一章：排列与组合排列能够看作n个不一样元素取r个放进r个不一样盒子放法.组合能够看作n个不一样元素取r个放进r个相同盒子放法.公式1：C(n,r)=C(n,n-r)21第21页从5个元素中取3个进行排列算法：inta[5]={1,2,3,4,5},b[3]；

for(i=0;i<5;i++){b[0]=a[i];for(j=0;j<5;j++){if(j==i)continue;elseb[1]=a[j];for(k=0;k<5;k++){if(k==i||k==j)continue;elseb[2]=a[k];打印b[]}}}1.3：排列与组合22第22页例1.7:由5种颜色星状物,20种不一样花共25个元素中任取5个排成以下列图案：两边是星状物,中间是3朵花，问共有多少种这么图案？解1：5×20×19×18×4=13680020种不一样花取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第23页1.8随机地选择n个人，求n个人最少有两人生日相同概率(不考虑润年)解:n个人生日不一样方案数是:365*364*…*(365-n+1)=P(365,n)n个人生日总方案数是:365n最少有两人生日相同概率:1-P(365,n)/365n1.3：排列与组合24第24页1.8随机地选择n个人，求n个人最少有两人生日相同概率(不考虑润年)解:思绪：任选两人，使其生日相同，其它任选。最少有两人生日相同概率:C(365,1)×C(n,2)×365n-2/365n1.3：排列与组合*对还是错？25第25页1.4：圆周排列定义：在排列中，假如我们不横排而是将各元素排列在一个圆周上，那么我们称这种排列方式为圆周排列。在排列中1234,2341,3412,4123为四个不一样排列，而在圆排列中这些排列是一个.要求相对位置不变算一个排列。26第26页将从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第27页例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!×5×4×31.4：圆周排列****28第28页例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种方式。依据乘法法则：若夫妻相邻而坐，共有24×25=24×32=768种方式。1.4：圆周排列*29第29页第一章：排列与组合多重集排列设S是一个多重集，有K个不一样类型元素，各元素重复分别为n1,n2,…,nk,n=n1+n2+…+nk,则S排列数为:30第30页第一章：排列与组合证实：给定多重集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元素,共有31第31页第一章：排列与组合依据剩法法则:S排列总数32第32页练习题1、求1040和2030公因数数目。解：1040=240540，2030=260530C(41,1)*C(31,1)33第33页2、试证n2整除数数目是奇数。练习题34第34页1.13、有n个不一样整数，从中取出两组来，要求第1组最小数大于另一组最大数。设取第一组数有a个,第二组有b个,要求第一组数中最小数大于第二组中最大，即只要取出一组m个数(设m=a+b),从大到小取a个作为第一组,剩下为第二组。此时方案数为C(n,m)。从m个数中取第一组数共有m-1中取法。(m-1)C(n,m)练习题35第35页练习题****36第36页第1章：游戏中碰到题目：1、中国象棋将帅问题2、一摞烙饼排序3、买书问题4、快速找出故障机器5、饮料供货6、光影切割问题7、小飞电梯调度算法8、高效率地安排见面会9、双线程高效下载..................《编程之美--微软技术面试心得》37第37页《编程之美--微软技术面试心得》第2章：数字之魅1、求二进制数中1个数2、不要被阶乘吓倒3、寻找发帖“水王”4、1数目5、寻找最大K个数6、最大条约数问题7、找符合条件整数8、斐