组合数学复习总结

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

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

3、。nn个元素集合的循环r排列个数为： 特别地，n元素的循环排列个数=(n1)! )!(!),(rnrnrrnP3.4 多重集的排列n无限重元素的排列计数：令S是多重集，它有k个不同的元素，每个元素都有无限重复次数，那么，S的r-排列个数为kr。n多重集的（全）排列计数：令S是多重集，它有k个不同的元素，每个元素的重复数分别为n1，n2，nk，那么，S的排列数等于!21knnnn3.5 多重集组合n无限重数多重集组合：令S是多重集，它有k个不同的元素，每个元素都有无限重复次数，那么，S的r-组合个数为nS的r-组合个数等于方程x1+x2+xk=r的非负整数解的个数。 r1-kr= 1-k1-kr

4、3.5 多重集组合（续）n多重集S=n1a1, n2a2, , nkak，n= n1+n2+nk ，求S的r-组合数，其中0rn。容斥原理方法生成函数方法第4章：生成排列和组合n主要算法相关问题n排列生成算法递归方法邻位替换逆序生成算法第4章：生成排列和组合（续）n生成组合算法字典序组合压缩序反射Gray序n生成r-组合算法字典序r-组合生成算法第5章 二项式系数111knknknPASCAL公式：0)(kkkyxkyx牛顿二项式：nnkxnknx01)1 (1第6章 容斥原理及应用n主要内容容斥原理：集合交、并的计数容斥原理的应用（1）多重集组合计数（2）特殊问题排列计数：错位排列、禁位排列

5、等6.1 容斥原理n集合S不具有性质P1,P2,Pm的物体的个数：|21mAAA|S|Ai|+|Ai Aj| |Ai Aj Ak |+(1)m|A1A2Am|容斥原理在多重集组合计数应用n求多重集的求多重集的r-组合数的一般方法组合数的一般方法利用容斥原理归为求无限重数元素的多重集计利用容斥原理归为求无限重数元素的多重集计数问题。数问题。将计数问题转化为较为简单的集合的交（或者将计数问题转化为较为简单的集合的交（或者并）；并）；应用容斥原理求出这些集合的交（或并）。应用容斥原理求出这些集合的交（或并）。容斥原理应用于排列计数n错位排列计数：错位排列计数： Dn=n! Dn满足如下递推关系: (

6、1) Dn=(n1)( Dn2+Dn1), (n=3,4,) (2) Dn=nDn1+(1)n (n=2,3,)!1)1(! 31!21! 111 (nn容斥原理应用于排列计数n禁位排列应用禁位排列应用绝对禁止位置排列绝对禁止位置排列相对禁止位置排列相对禁止位置排列 11)!(1) 1(!nkknknknnQ第7章 递推关系和生成函数n主要内容（重点递推关系求解）n递推关系：特殊问题递推关系线性齐次递推关系求解：特征多项式方法非齐次递推关系求解。生成函数n生成函数利用生成函数求解递推关系特殊序列的生成函数利用生成函数计数：如多重集组合和排列。常系数线性齐次递推关系求解n常系数线性齐次递推关系：

7、 hn=a1hn-1+a2hn-2+akhn-k (ak0, nk)（1）方法1：求特征方程 xka1xk1a2xk2ak=0 的特征根；分互异根及重根两种情形。（2）方法2：求生成函数形如p(x)/q(x)；生成函数的展开式，通常化为代数分式和形式：c/(1rx)t, 利用牛顿二项式展开。 非齐次线性递推关系求解n非齐次线性递推关系： hn=a1hn-1+a2hn-2+akhn-k+bn方法：方法：(1)求齐次关系的一般解(2)求非齐次关系的一个特解(3)将一般解和特解结合,通过初始条件确定一般解中出现的常系数值。第九章n知识要点：二分图的问题模型：车-二分图、多米若二分图等二分图、匹配、覆

8、盖及M-交错路径等概念求最大匹配的M-交错路径搜索算法互异代表系统，成婚条件运用延迟认可算法解决稳定的完备婚姻问题。匹配、覆盖及交错路径的关系（1）是最大匹配不存在M-交错路径； M-交错路径可以构造边数多于M的匹配。（2）|M|S|, M是匹配，S是覆盖； (G)=c(G).两个重要算法nM-交错路径搜索算法：判定并构造最大匹配。n延迟认可算法：构造稳定完备婚姻配对。例题选讲及解答要求1、构造1,2,8的排列，使其逆序列是2, 5, 5, 0, 2, 1, 1, 0。（10分）解答解法解法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。解答解法解法2：根据逆序列2, 5, 5, 0, 2, 1, 1, 0，执行逆序构造排列算法II得到： （缺构造过程-扣5分） 因此，对应该逆序的排列为48165723。1:12:123:1234:41235:415236:41