组合数学课件--第一章：排列与组合

《组合数学课件--第一章：排列与组合》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合数学课时：36学时成绩分配：平时成绩30分，期末考试成绩70分。平时成绩取得方式：安排5次课堂测验，每次6分。课件邮箱:hjh20070826@163.com密码:200708261组合数学的应用范畴从广义上讲组合数学就是离散数学组合数学研究满足一定条件的组合模型的情况:(1)存在性：(2)计数：(3)有哪些？(4)哪些最优？组合数学与算法、密码学、编码理论、数据压缩等计算机方向密不可分。****2选用教材组合数学(第四版)卢开澄卢华明著清华大学出版社3组合数学的应用范畴第一章:排列与组合第二章:递推关系与母函数第三章:容斥原理与鸽巢

2、原理第四章:Burnside引理与Polya定理第五章:区组设计第六章:线性规划第七章:编码简介第八章:组合算法简介4参考教材组合数学RichardA.Brualdi著冯舜玺等译机械工业出版社5参考教材组合数学及其算法杨振生中国科学技术大学出版社6第一章：排列与组合1.1基本计数法则1.2一一对应:1.3排列与组合1.4圆周排列1.5排列的生成算法1.6允许重复的组合与不相邻的组合1.7组合意义的解释1.8应用举例1.9*Stirling公式71.1基本计数法则1、加法法则:如果具有性质A的事件有m个，性质B的事件有n个，则具有性质A或B

3、的事件有m+n个。A和B是性质无关的两个事件。82、乘法法则:若具有性质A的事件有m个，具有性质B的事件有n个，则具有性质A及B的事件有mn个1.1基本计数法则9例1.1若从合肥到南京有2条路可走，从南京到上海有3条路可走，从上海到杭州有2条路可走，问从合肥经南京、上海到杭州有多少路可走？1.1基本计数法则10例1.2：用乘法法则解释8卦及64卦。解：1、太极生两仪3、四象生八卦000，001，010,011100，101，110,1112、两仪生四象00，01，10，11；1.1基本计数法则11例1.3：长度为n的0,1符号串的数

4、目?例1.4人类DNA链的长度为2.1×1010,链上每一位由T,C,A,G四种化合物组成,求人类DNA链的可组成数目。1.1基本计数法则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.

5、1基本计数法则*131、从n个数中找出最大值问题2、n个人参加单淘汰赛，最后产生冠军的过程。1.2一一对应14例1.6：求n2个人站成一排和站成n排（方阵）的方案数，并比较两种方案数的大小？解：9个人站成一排的方案数是9!，设a1a2a3a4a5a6a7a8a9是9个人的一排，可构成一个方阵a1a2a3a4a5a6a7a8a9给定一个方阵b1b2b3b4b5b6b7b8b9也唯一确定一排b1b2b3b4b5b6b7b8b9因此这两种站位方式的方案数一样多，都是9!1.2一一对应15例1.6：求n2个人站成一排和站成n排（方阵）的方案数，并

6、比较两种方案数的大小？9个人站成方阵的方案数为：C(9,3)3!C(6,3)3!C(3,3)3!1.2一一对应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一一对应1712534树的顶点集合为12345这棵树对应序列（2，3，2）任给一个序列B{b

7、1,b2,b3,…,bn-2}1、从A找到最小的不属于B的元素,设为a1,与b1连接，从A中去掉a1，从B中去掉b1.2、重复以上过程只到B为空，A中剩余两个3、连接剩余的两个顶点。1.2一一对应*181.3：排列与组合1、排列的定义：设A={a1,a2,…,an}是n个不同的元素的集合，任取A中r个元素按顺序排成一列，称为从A中取r个的一个排列，r满足0≤r≤n。从n个不同的球中取一个球放在第一个盒子中，从余下的n-1个球中取一个球放在第二个盒子中，…………………………………从余下的n-(r-1)个球中取一个放在第r个盒子中。(1)(2

8、)(3)(…)(r)根据乘法法则：P(n,r)=n(n-1)…(n-r+1)=n!／(n-r)!19全排列:P(n,n)=n(n-1)…2×1=n!1.3：排列与组合2、组合的定义：当从n个不