1、 组合数学复习总结内容n 课程知识结构n 各章知识点知识结构什么是组合数学鸽巢原理排列与组合生成排列和组合二项式系数容斥原理及应用递推关系和生成函数计数技巧构造算法排列存在性二分图的匹配各章要求和重点第 1章 什么是组合数学n 组合数学的研究内容组合数学是研究离散结构的存在、计数、分析和优化等问题的学科。n 一些重要例子棋盘覆盖问题第 2章 鸽巢原理及应用n 鸽巢原理简单形式及 加强形式若将 q1+q2+ +qnn+1个物体被放进 n个盒子内，那么，或者第一个盒子至少含有个 q1物体，或者第二个盒子至少含有个 q2物体， ， 或者第 n个盒子至少含有个 qn物体n Ramsey定理至少掌握 R
2、amsey定理的简单形式及应用。第 2章 鸽巢原理及应用 (续 )n 用于证明某种排列的存在性，不用于构造排列和计数。n 运用鸽巢原理通常需要将问题转化。第 3章 排列与组合n 主要内容两个基本计数原理： 加法原理、乘法原理集合排列和组合多重集的排列 （ 重点掌握 ）多重集的组合 （ 重点掌握 ）3.2 集合的排列n 难点n 循环排列 : 把元素排成首尾相连的一个圈，只考虑元素间的相对顺序的排列。n n个元素集合的循环 r排列个数为：特别地， n元素的循环排列个数 =(n1)! 3.4 多重集的排列n 无限重元素的排列计数 ： 令 S是多重集，它有 k个不同的元素，每个元素都有无限重复次数，那么， S的 r-排列个数为 kr。n 多重集的（全）排列计数 ： 令 S是多重集，它有 k个不同的元素，每个元素的重复数分别为n1， n2， ， nk，那么， S的排列数等于
