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

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

  1. 1、本文档共40页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
* * 组合数学 课时: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,

文档评论(0)

wuyoujun92 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档