《组合数学》教学大纲

1、 组合数学教学大纲组合数学课程是数学与应用数学专业的专业选修课程，也是应用性很强的一门数学课。本课程主要研究一组离散对象满足一定条件的安排的存在性，以及这种安排的构造，枚举计数及优化问题，它是整个离散数学的一个重要组成部分。目前组合数学不仅成为数学中的一个重要分支，而且还成为计算机科学，管理科学及其它学科的数学基础。设置本课程的目的是：一方面使学生学好作为专业课程的组合数学课，为组合方向的后续研究打下基础；另一方面培养学生理论联系实际和分析问题、解决问题的能力，会用组合的想法解决实际问题。学习本课程的要求是：通过本课程的学习，要使学生具有现代数学的观点和方法，初步掌握常用组合计数的构造思想和计

2、算方法。要求掌握鸽巢原理、排列组合原理、容斥原理、递推关系与生成函数。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力。先修课程要求：数学分析，高等代数，概率论本课程计划72学时，3学分选用教材：孙淑玲 许胤龙编著，组合数学引论，中国科技大学出版社，2005教学手段：课堂讲授为主，习题课与讨论课为辅考核方法：闭卷书面考试教学进程安排表周次学时数教学主要内容教学环节备注12鸽巢原理的简单形式及其应用讲课12鸽巢原理的加强形式，相关推论讲课22Ramsey问题的提出及证明，Ramsey数及其相关结论讲课22Ramsey数的推广形

3、式，Ramsey定理讲课与习题课相结合32加法原则与乘法原则，排列与组合，多重集合的排列与组合讨论课32二项式定理与二项式系数的基本性质组合恒等式，多项式定理讲课42集合的分化与第二类Stirling数的相关定理讲课42正整数的分拆，有序分拆及其相关定理无序分拆及其相关定理讲课52分拆的Ferrers图，Ferrers图的共轭图讲课52分配问题的基本想法，分配问题的实例讲课与习题课相结合62容斥原理的引入背景，容斥原理的简单实例讲课62容斥原理的一般形式及其证明，容斥原理的几个推论，讲课72容斥原理的进一步讨论讲课72具有有限重复数的多重集合的r组合数问题，错排问题讲课82有禁止模式的的排列问

4、题，mnage问题与mnage数讲课82Mbius函数的定义，Mbius反演定理及其证明讲课92可重复排列问题讲课与习题课相结合92递推关系的概念，递推关系的建立讲课102常系数线性齐次递推关系的概念与解的结构讲课与习题课相结合102常系数线性齐次递推关系的求解过程与应用举例讲课112常系数线性非齐次递推关系的概念与解的结构讲课112常系数线性非齐次递推关系的求解过程与应用举例讲课122Fibonacci数的引入，组合意义，推倒过程与应用举例讲课122Catalan数的引入，组合意义，推倒过程与应用举例讲课与习题课相结合132生成函数的引入与举例，形式幂级数的概念讲课132形式幂级数的基本性质

5、，形式幂级数的形式导数讲课142生成函数的性质与证明讲课142几种常见的简单数列生成函数的求解讲课152用生成函数求解常系数线性齐次递推关系的具体方法讲课152用生成函数求解常系数线性非齐次递推关系的具体方法讲课162组合数的生成函数，排列数的指数型生成函数讲课162分拆数的生成函数，组合型分配问题的生成函数讲课172排列型分配问题的生成函数，有限制位置的排列讲课172有限制位置的排列的基本结论，棋子多项式讲课182复习习题课182复习习题课第一章预备知识一、学习目的通过本章的学习，要求学生掌握鸽巢原理与鸽巢原理的加强形式，并会用鸽巢原理与鸽巢原理的加强形式讨论和解决实际问题。理解Ramsey

6、问题，会讨论简单的Ramsey数，了解Ramsey的推广形式和Ramsey定理。本章计划8学时。二、课程内容11鸽巢原理的简单形式鸽巢原理的简单形式，利用鸽巢原理解决实际问题。12鸽巢原理的加强形式鸽巢原理的加强形式及推论，鸽巢原理加强形式的应用举例。13Ramsey问题与Ramsey数经典Ramsey问题的提出与证明，Ramsey问题的延伸，Ramsey数及其相关定理。14Ramsey数的推广Ramsey问题与Ramsey数的推广形式，Ramsey定理及其证明。三、教学基本要求了解：经典Ramsey问题的引入，Ramsey定理。理解：鸽巢原理与鸽巢原理的推广形式。鸽巢原理所体现的组合思想。掌

7、握：利用鸽巢原理解决实际问题，判断简单Ramsey数的方法。四、重点、难点提示和教学手段（一）本章重点鸽巢原理的应用，Ramsey数的判定。（二）本章难点Ramsey定理及其证明。（三）教学手段课堂讲授与习题课相结合五、思考与练习思考：如何将鸽巢原理和Ramsey定理有机的联系起来。练习由授课教师自行确定。第二章基本计数问题一、学习目的通过本章的学习，熟练掌握加法原则，乘法原则，排列组合及二项式定理及其相关结论，理解集合的分化和正整数分拆的思想。掌握第二类Stirling数的相关性质。能够给出分拆的Ferrers图，能够求解简单的分配问题，并能分析，解决实际问题。本章计划14学时。二、课程内容

8、21加法原则和乘法原则加法原则及其相关定理，乘法原理及其相关定理。22排列与组合排列的基本定义，排列数，组合的定义，组合数，排列数与组合数的应用举例。23多重集合的排列与组合多重集合的概念，多重集合排列的概念与基本定理，多重集合组合的概念与基本定理，增字。24二项式系数二项式定理，二项式定理的基本性质(对称关系，递推关系，单峰性)与组合意义。一些组合恒等式，多项式定理。25集合的分化与第二类Stirling数集合分化的定义，第二类Stirling数的定义及相关性质。26正整数的分拆正整数分拆的定义。有序分拆的定义及相关结论，无序分拆的定义及相关结论，正整数分拆的Ferrers图与共轭。利用分拆

9、的Ferrers图证明的关于分拆的基本结论。27分配问题分配问题的提出及分析。三、教学基本要求理解：多重集合的概念，集合的分化和正整数分拆的思想。掌握：加法原则，乘法原则，排列组合，多重集合的排列组合及二项式定理及其相关结论，第二类Stirling数的相关性质，实际应用的分配问题。四、重点、难点提示和教学手段（一）本章重点多重集合的概念及其排列组合，二项式定理及其基本性质，Stirling数的性质。（二）本章难点有序分拆，无序分拆的相关结论。（三）教学手段课堂讲授与讨论课、习题课相结合五、思考与练习思考：讨论几种分配问题之间的联系。练习由授课教师自行确定。第三章容斥原理一、学习目的通过本章的学

10、习，掌握一种重要的组合计数方法：容斥原理。了解容斥原理引入的背景，理解容斥原理原理的思想，会用容斥原理解决一些实际问题，了解Mbius反演及可重复圆排列的思想。本章计划16学时。二、课程内容31引论容斥原理引入的背景及重要意义，容斥原理在几个简单问题上的应用。32容斥原理容斥原理及其证明，容斥原理的推论及其证明。33容斥原理的应用具有有限重复数的多重集合的人r组合数问题，错排问题，有禁止模式的错排问题，mnage问题及既化的mnage问题，实际依赖于所有变量的函数个数的确定问题。34Mbius反演及可重复的圆排列Mbius函数的定义，Mbius反演定理及其证明，可重复排列问题。三、教学基本要求

11、理解：理解容斥原理原理的思想，Mbius函数的概念。了解：容斥原理引入的背景及重要意义，了解Mbius反演及可重复圆排列的思想。掌握：利用容斥原理解决组合计数问题。四、重点、难点提示和教学手段（一）本章重点容斥原理的思想及表达形式，具有有限重复数的多重集合的人r组合数问题，错排问题，可重复排列问题。（二）本章难点Mbius反演及可重复圆排列，容斥原理解决组合计数问题（三）教学手段课堂讲授与习题课相结合五、思考与练习思考与练习由授课教师自行确定。第四章递推关系一、学习目的通过本章的学习，理解递推关系内在的组合结构，掌握递推关系的建立方法，掌握几种特殊递推关系的求解方法。了解几种特殊的递推关系：F

12、ibonacci数列合Catalan数列。本章计划14学时。二、课程内容41递推关系的建立递推关系的概念，几个实例递推关系的建立。42常系数线性齐次递推关系的求解k阶常系数线性齐次递推关系的概念，递推关系特征根的定义，k阶常系数线性齐次递推关系解的结构，k阶常系数线性齐次递推关系求解的一般方法。43常系数线性非齐次递推关系的求解k阶常系数线性非齐次递推关系的概念，k阶常系数线性非齐次递推关系通解的结构，k阶常系数线性非齐次递推关系求解的一般方法，k阶常系数线性非齐次递推关系应用举例。44用迭代归纳法求解的递推关系用迭代归纳法求解的递推关系基本思想，用迭代归纳法求解的递推关系步骤，应用举例。45

13、 Fibonacci数与Catalan数Fibonacci数列的引入背景与组合意义，Fibonacci数的求解过程。Catalan数列的引入背景与组合意义，Catalan数列的求解过程，应用举例。三、教学基本要求理解：k阶常系数线性齐次递推关系求解的思想，k阶常系数线性非齐次递推关系求解的基本思想，迭代归纳法求解递推关系的基本思想。了解：Fibonacci数列与Catalan数列的引入背景及组合意义。掌握：递推关系的建立方法，k阶常系数线性(非)齐次递推关系通解的结构与一般解法。四、重点、难点提示和教学手段（一）本章重点递推关系的建立过程，k阶常系数线性齐次递推关系通解结构，k阶常系数线性齐次

14、递推关系求解的一般方法。（二）本章难点k阶常系数线性非齐次递推关系通解的结构。迭代归纳法求解的递推关系基本思想与具体步骤。（三）教学手段课堂讲授与习题课相结合。五、思考与练习思考与练习由授课教师自行确定。第五章生成函数一、学习目的通过本章的学习，了解生成函数引入的背景，理解形式幂级数的相关概念，了解形式幂级数的一些基本性质，掌握利用生成函数求解递推关系的方法，会利用生成函数讨论一些组合计数问题。本章计划20学时。二、课程内容51引论生成函数的引入与应用举例。52形式幂级数形式幂级数的概念，形式幂级数的相等，形式幂计数的数乘，加法，代数分析。形式幂级数的形式导数及相关性质。53生成函数的性质生成

15、函数的基本性质及其证明过程，几个常见的生成函数。54用生成函数求解递推关系用生成函数求解递推的基本想法与步骤，用生成函数求解常系数线性齐次递推关系的方法，通解形式。用生成函数求解常系数线性非齐次递推关系的方法，通解形式。55生成函数在计数问题中的应用几类特殊的生成函数，组合数的生成函数，排列数的指数型生成函数，分拆数的生成函数，组合型分配问题的生成函数，排列型分配问题的生成函数。56有限位置的排列及棋子多项式有限制位置的排列的理论推倒，棋盘问题与棋子多项式。三、教学基本要求理解：形式幂级数的相关概念，利用生成函数求解组合计数问题的想法。了解：生成函数引入的背景，有限制位置的排列与棋盘问题。掌握：用生成函数求解常系数线性齐次递推关系的方法，通解形式。用生成函数求解常系数线性非齐次递推关系的方法，通解形式。四、重点、难点提示和教学手段（一）本章重点形式幂级数的概念。用生成函数求解常系数线性齐