《组合数学》课程教学大纲
课程英文名Combinatorics
执笔人：晁福刚编写日期：2010.7.9
一、课程基本信息
1. 课程编号：07010132
2. 课程性质/类别：限选课/专业基础课
3. 学时/学分：48学时/ 2学分
4. 适用专业：数学与应用数学信息与计算科学专业
二、课程教学目标及学生应达到的能力
组合数学主要研究一组离散对象满足一定条件的安排的存在性，以及这种安排的构造、枚举计数及优化等问题，这是整个离散数学的一个重要组成部分。

《组合数学》课程的教学目标是通过本课程的学习，使学生初步掌握组合数学的基本原理和思想方法。

了解和掌握并会应用鸽巢原理、排列与组合、容斥原理、递推关系、生成函数等组合数学基本知识。

三、课程教学内容与基本要求
（一）鸽巢原理（8学时）
1．主要内容：
鸽巢原理的简单形式，鸽巢原理的加强形式，Ramsey问题与Ramsey数，Ramsey 数的推广。

2．基本要求
1．了解鸽巢原理的简单形式和加强形式，会用鸽巢原理解决简单的问题。

2．了解Ramsey问题的历史由来，会求简单的Ramsey数，Schur数。

3．自学内容：无
4．课外实践：无
（二）基本计数问题（10学时）
1．主要内容：
加法原则与乘法原则，排列与组合，多重集合的排列与组合，二项式系数，集合的分划与第二类Stirling数，正整数的分拆，分配问题。

2．基本要求
1．了解加法原则和乘法原则，会求简单的排列组合问题。

2．掌握多重集合的排列和组合技巧。

3．会证明组合恒等式。

4．了解集合的分划与第二类Stirling数，知道两类数之间的关系。

5．知道正整数分拆问题的递推关系及研究进展。

6．知道一些简单的分配问题的解法。

3．自学内容：
排列组合
4．课外实践：
无
（三）容斥原理（10学时）
1．主要内容：
容斥原理，容斥原理的就用，Mobius反演及可重复的圆排列。

2．基本要求
1．了解容斥原理的内容，并会简单应用。

2．掌握Mobius反演及可重复的圆排列。

3．自学内容：
集合论
4．课外实践：
无
（四）递推关系（10学时）
1．主要内容：
递推关系的建立，常系数线性齐次递推关系的求解，常系数线性非齐次递推关系的求解，用迭代归纳法求解递推关系，Fibonacci数和Catalan数。

2．基本要求
1．会建立递推关系。

2．会银常系数线性齐次递推关系和常系数线性非齐次递推关系。

3．会用迭代归纳法求解递推关系。

4．了解Fibonacci数和Catalan数及其相关性质。

3．自学内容：
常微分方程
4．课外实践：
无
（五）生成函数(10学时）
1．主要内容：
形式幂级数，生成函数的性质，用生成函数求解递推关系，生成函数在组合计数中的应用。

2．基本要求
1．了解形式幂级数，知道其相关的性质。

2．会用生成函数求解递推关系。

3．了解生成函数在组合计数中的应用。

3．自学内容：
数学分析
4．课外实践：
无
四、教学安排建议
1. 作业练习每次课后布置2-3题作业。

2. 案例分析无
3. 专题研讨无
4.实验安排无
五、课程考核
1. 考核形式及成绩评定办法
考核形式为闭卷考试，成绩评定方法为考试占80%，平时占20%。

2. 本课程考核的基本要求
掌握组合数学的基本理论；能比较熟练地应用各种组合计数方法对不太复杂的组态的计数; 培养学生应用组合数学的相关理论去解决比较简单的实际问题的能力。

六、本课程与其它课程的先行后续关系
本课程应先修完数学分析、高等代数、常微分方程等课程后再修。

七、建议教材及教学参考书
1. 教材：
组合数学引论，孙淑玲、许胤龙编著，合肥：中国科技大学出版社，1999。

2.参考书：
[1] 组合学讲义(第二版)，李乔编著，北京：高等教育出版社，2008。

[2] 组合数学(第五版)，Richard A Brualdi著，冯舜玺、罗平、裴伟东译，北京：机
械工业出版社，2009。

[3] 组合数学教程(第二版)，J H van Lint和R M Wilson著，刘振宏、赵振江译，北
京：机械工业出版社。