组合数学复习总结(课堂PPT).ppt

《组合数学复习总结(课堂PPT).ppt》由会员分享，可在线阅读，更多相关《组合数学复习总结(课堂PPT).ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 组合数学 复习总结1内容1.课程知识结构2.各章知识点2知识结构什么是组合数学什么是组合数学鸽巢原理鸽巢原理排列与组合排列与组合生成排列和组合生成排列和组合二项式系数二项式系数容斥原理及应用容斥原理及应用递推关系和生成函数递推关系和生成函数计数技巧计数技巧构造算法构造算法排列存在性排列存在性二分图的匹配二分图的匹配3各章要求和重点各章要求和重点4第1章 什么是组合数学n组合数学的研究内容组合数学是研究离散结构的存在、计数、分析和优化等问题的学科。n一些重要例子棋盘覆盖问题5第2章 鸽巢原理及应用n鸽巢原理简单形式及鸽巢原理简单形式及加强形式加强形式若将q1+q2+qnn+1个物体被放进n个盒

2、子内，那么，或者第一个盒子至少含有个q1物体，或者第二个盒子至少含有个q2物体，或者第n个盒子至少含有个qn物体nRamsey定理至少掌握Ramsey定理的简单形式及应用。6第2章 鸽巢原理及应用(续)n用于证明某种排列的存在性，不用于构造排列和计数。n运用鸽巢原理通常需要将问题转化。7第3章 排列与组合n主要内容主要内容两个基本计数原理：加法原理、乘法原理集合排列和组合多重集的排列多重集的排列（重点掌握重点掌握）多重集的组合多重集的组合（重点掌握重点掌握）83.2 集合的排列n难点n循环排列:把元素排成首尾相连的一个圈，只考虑元素间的相把元素排成首尾相连的一个圈，只考虑元素间的相对顺序的排列

3、。对顺序的排列。nn个元素集合的循环r排列个数为：特别地，n元素的循环排列个数=(n1)!93.4 多重集的排列n无限重元素的排列计数：令S是多重集，它有k个不同的元素，每个元素都有无限重复次数，那么，S的r-排列个数为kr。n多重集的（全）排列计数：令S是多重集，它有k个不同的元素，每个元素的重复数分别为n1，n2，nk，那么，S的排列数等于103.5 多重集组合n无限重数多重集组合：令S是多重集，它有k个不同的元素，每个元素都有无限重复次数，那么，S的r-组合个数为nS的r-组合个数等于方程x1+x2+xk=r的非负整数解的个数。=113.5 多重集组合（续）n多重集S=n1a1,n2a2

4、,nkak，n=n1+n2+nk，求S的r-组合数，其中0rn。容斥原理方法生成函数方法12第4章：生成排列和组合n主要算法相关问题n排列生成算法递归方法邻位替换逆序生成算法13第4章：生成排列和组合（续）n生成组合算法字典序组合压缩序反射Gray序n生成r-组合算法字典序r-组合生成算法14第5章 二项式系数PASCAL公式：牛顿二项式：15第6章 容斥原理及应用n主要内容容斥原理：集合交、并的计数容斥原理的应用（1）多重集组合计数（2）特殊问题排列计数：错位排列、禁位排列等166.1 容斥原理n集合S不具有性质P1,P2,Pm的物体的个数：|S|Ai|+|Ai Aj|Ai Aj Ak|+(

5、1)m|A1A2Am|17容斥原理在多重集组合计数应用n求多重集的求多重集的r-组合数的一般方法组合数的一般方法利用容斥原理归为求无限重数元素的多重集计利用容斥原理归为求无限重数元素的多重集计数问题。数问题。将计数问题转化为较为简单的集合的交（或者将计数问题转化为较为简单的集合的交（或者并）；并）；应用容斥原理求出这些集合的交（或并）。应用容斥原理求出这些集合的交（或并）。18容斥原理应用于排列计数n错位排列计数：错位排列计数：Dn=n!Dn满足如下递推关系:(1)Dn=(n1)(Dn2+Dn1),(n=3,4,)(2)Dn=nDn1+(1)n (n=2,3,)19容斥原理应用于排列计数n禁位

6、排列应用禁位排列应用绝对禁止位置排列绝对禁止位置排列相对禁止位置排列相对禁止位置排列20第7章 递推关系和生成函数n主要内容（重点递推关系求解）n递推关系：特殊问题递推关系线性齐次递推关系求解：特征多项式方法非齐次递推关系求解。21生成函数n生成函数利用生成函数求解递推关系特殊序列的生成函数利用生成函数计数：如多重集组合和排列。22常系数线性齐次递推关系求解n常系数线性齐次递推关系：hn=a1hn-1+a2hn-2+akhn-k (ak0,nk)（1）方法1：求特征方程 xka1xk1a2xk2ak=0 的特征根；分互异根及重根两种情形。（2）方法2：求生成函数形如p(x)/q(x)；生成函数

7、的展开式，通常化为代数分式和形式：c/(1rx)t,利用牛顿二项式展开。23非齐次线性递推关系求解n非齐次线性递推关系：hn=a1hn-1+a2hn-2+akhn-k+bn方法：方法：(1)求齐次关系的一般解(2)求非齐次关系的一个特解(3)将一般解和特解结合,通过初始条件确定一般解中出现的常系数值。24第九章n知识要点：二分图的问题模型：车-二分图、多米若二分图等二分图、匹配、覆盖及M-交错路径等概念求最大匹配的M-交错路径搜索算法互异代表系统，成婚条件运用延迟认可算法解决稳定的完备婚姻问题。25匹配、覆盖及交错路径的关系（1）是最大匹配不存在M-交错路径；M-交错路径可以构造边数多于M的匹

8、配。（2）|M|S|,M是匹配，S是覆盖；(G)=c(G).26两个重要算法nM-交错路径搜索算法：判定并构造最大匹配。n延迟认可算法：构造稳定完备婚姻配对。27例题选讲及解答要求1、构造1,2,8的排列，使其逆序列是2,5,5,0,2,1,1,0。（10分）28解答解法解法1：根据逆序列2,5,5,0,2,1,1,0，执行逆序构造排列算法I得到：8:8 7:87 6:867 5:8657 4:48657 3:486573 2:4865723 1:48165723 （缺构造过程-扣5分）因此，对应该逆序的排列为48165723。29解答解法解法2：根据逆序列2,5,5,0,2,1,1,0，执行逆序构造排列算法II得到：（缺构造过程-扣5分）因此，对应该逆序的排列为48165723。1:12:123:1234:41235:415236:4165237:41657238:4816572330考试安排n命题范围：主要27，9章。n考试方式：闭卷闭卷n题型组成填空题计算题证明题n时间：6月月18日（星期五）上午日（星期五）上午10:0012:00n地点：31预祝大家取得好的成绩预祝大家取得好的成绩！http:/ftp:/32