第一章排列与组合.ppt

《第一章排列与组合.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、徐宁计算机科学与技术学院2010年12月组合数学Combinatorics2004深研1组合数学第1章组合数学的发展组合数学是一个古老而又年轻的数学分支。据传说，大禹观察到神龟背上的幻方（纵横图）3阶方阵，填入1到9，每行、每列以及两条对角线的和都相等。5193724862004深研2组合数学第1章洛书杨辉：纵横图九子斜排，上下对易，左右相更，四维挺进。裁九履—，左三右七，二四为肩，六八为足．2004深研3组合数学第1章组合数学的发展贾宪——北宋数学家（约11世纪）著有《黄帝九章细草》、《算法斅古集》都已失传。杨辉著《详

2、解九章算法》（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）比帕斯卡三角形早600年；和“增乘开方法”（求高次幂的正根法）。比霍纳的方法（1819年）早770年。霍纳（WilliamGeogeHorner，1786—1837）2004深研4组合数学第1章组合数学的发展1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著，书中首次使用了组合论（Combinatorics）一词。18世纪：欧拉，哈密尔顿等2004深研5组合数学第1章组合数学的发展组合数学的

3、蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。主要研究的问题：存在性问题、计数问题、构造问题、最优化问题2004深研6组合数学第1章组合数学研究的问题存在问题计算问题或分类问题构造问题（组合设计）优化问题2004深研7组合数学第1章组合数学与计算机科学研究算法的理论基础组合分析，组合算法。组合分析是组合算法的基础编码理论图论密码学算法复杂性分析NP_Complete问题与NP_Hard问题搜索问题，组合最优问题，多

4、约束最优问题近似解法及其复杂度2004深研8组合数学第1章如何学好组合数学组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。2004深研9组合数学第1章本课程章节安排本学期主要讲组合分析（计数和枚举）以及组合优化的一部分（线性规划的单纯形解法）。组合分析是组合算法的基础。第1章排列与组合第2章母函数第3章鸽巢原理第4章Polya定理第5章线性规划第6章组合优化及其在VLSI领域的应用2004深研10组合数学第1章第1

5、章排列与组合排列与组合加法法则与乘法法则模型转换全排列生成算法组合的生成可重组合与不相邻组合若干等式及其组合意义应用举例Stirling近似公式算法复杂性计算举例2004深研11组合数学第1章1.1排列与组合排列：P(n,r)=n(n-1)······(n-r+1)=[n]r=Pn=P(n,n)=n!组合：C(n,r)=P(n,r)/r！=()=nrn!———r!(n-r)!n!——(n-r)!2004深研12组合数学第1章1.1排列与组合——圆排列从n个中取r个的圆排列的排列数Q(n,r)=P(n,r)/r,2≤r≤n

6、以4个元素为例124312341243234112433412124341232004深研13组合数学第1章1.1排列与组合——项链排列项链排列:排列的方法和项链一样,在圆排列的基础上，顺时针和反时针是同一个排列。从n个中取r个的项链排列的排列数R(n,r)=Q(n,r)/2=P(n,r)/2r,3≤r≤n1123322004深研14组合数学第1章1.1排列与组合——可重排列求r1个1，r2个2，…，rt个t的排列设r1+r2+…+rt=n,设此排列数为P(n;r1,r2,…,rt),对1，2，…，t分别加下标，得到P(

7、n；r1,r2,…,rt)·r1!·r2!·…·rt!=n!∴P(n；r1,r2,…,rt)=————=()思考：n个数中取r个的可重排列的排列数？n!r1!r2!…rt!nr1r2…rt2004深研15组合数学第1章1.2加法法则和乘法法则[加法法则]设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若

8、A

9、=m,

10、B

11、=n,AB=,则

12、AB

13、=m+n。2004深研16组合数学第1章1.2加法法则和乘法法则例：某课程A系学生16人选，B系学生7人选，其他系学生5人选，共

14、有多少人选？解：根据加法法则，选课人数共有16+7+5=28人2004深研17组合数学第1章1.2加法法则和乘法法则例：1组学生7人，2组学生6人，要派3名同组学生参加比赛，有几种可能？若两组学生任选3人，有几种可能？解：3名学生或者都是1组的：C(7,3);或者都是2组的：C(6,3)。可能组合总数为：C(7,3)