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

* * 组合数学 课时：36学时 成绩分配：平时成绩30分，期末考试成绩70分。 平时成绩取得方式：安排5次课堂测验，每次6分。 课件邮箱:hj163.com 密码组合数学的应用范畴 从广义上讲组合数学就是离散数学 组合数学研究满足一定条件的组合模型的情况: (1)存在性： (2)计数： (3)有哪些？ (4)哪些最优？ 组合数学与算法、密码学、编码理论、数据压缩等计算机方向密不可分。 **** 选用教材 组合数学 (第四版) 卢开澄 卢华明 著 清华大学出版社 组合数学的应用范畴 第一章:排列与组合 第二章:递推关系与母函数 第三章:容斥原理与鸽巢原理 第四章:Burnside引理与Polya定理 第五章:区组设计 第六章:线性规划 第七章:编码简介 第八章:组合算法简介 参考教材 组合数学 Richard A. Brualdi 著 冯舜玺等译 机械工业出版社 参考教材 组合数学及其算法 杨振生 中国科学技术大学出版社 第一章：排列与组合 1.1 基本计数法则 1.2 一一对应: 1.3 排列与组合 1.4 圆周排列 1.5 排列的生成算法 1.6 允许重复的组合与不相邻的组合 1.7 组合意义的解释 1.8 应用举例 1.9 *Stirling公式 1.1基本计数法则 1、加法法则: 如果具有性质A的事件有m个，性质B的事件有n个，则具有性质A或B的事件有m+n个。 A和B是性质无关的两个事件。 2、乘法法则: 若具有性质A的事件有m个，具有性质B的事件有n个，则具有性质A及B的事件有mn个 1.1基本计数法则 例1.1 若从合肥到南京有2条路可走，从南京到上海有3条路可走，从上海到杭州有2条路可走，问从合肥经南京、上海到杭州有多少路可走？ 1.1基本计数法则 例1.2：用乘法法则解释8卦及64卦。 解：1、太极生两仪? 3、四象生八卦? 000，001，010, 011 100，101，110, 111 2、两仪生四象? 00，01，10，11； 1.1基本计数法则 例1.3：长度为n的0,1符号串的数目? 例1.4 人类DNA链的长度为2.1×1010,链上每一位由T,C,A,G四种化合物组成,求人类DNA链的可组成数目。 1.1基本计数法则 例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^2n 1.1基本计数法则 * 1、从n个数中找出最大值问题 2、n个人参加单淘汰赛，最后产生冠军的过程。 1.2 一一对应 例1.6：求n2个人站成一排和站成n排（方阵）的方案数，并比较两种方案数的大小？ 解：9个人站成一排的方案数是9!， 设a1a2a3a4a5a6a7a8a9是9个人的一排， 可构成一个方阵 a1a2a3 a4a5a6 a7a8a9 给定一个方阵 b1b2b3 b4b5b6 b7b8b9 也唯一确定一排b1b2b3b4b5b6b7b8b9 因此这两种站位方式的方案数一样多，都是9! 1.2 一一对应 例1.6：求n2个人站成一排和站成n排（方阵）的方案数，并比较两种方案数的大小？ 9个人站成方阵的方案数为： C(9,3)3!C(6,3)3!C(3,3)3! 1.2 一一对应 定理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=b1b2b3…bn-2而且是唯一的 1.2 一一对应 1 2 5 3 4 树的顶点集合为12345 这棵树对应序列（2，3，2） 任给一个序列B{b1,b2,b3,