课 程 教 学 大 纲
(理论课)
课 程 名 称： 组合数学 适 用 专 业： 数学与应用数学 课 程 类 别： 学科基础课程 制 订 时 间： 2006年9月
数学与计算机科学学院 制
《组合数学》课程教学大纲
（2002年制定，2006年修订）
一、课程代码：0501122002
二、课程类别：学科基础课程（选修） 三、预修课程：数学分析、高等代数 四、学 分：3学分 五、学 时：54学时 六、课程概述：
组合数学也叫组合学，它源远流长，起源于古代的数学游戏和美学消遣，以无穷的魅力激发人们的聪明才智和数学兴趣。随着近代科学技术的发展，组合数学已经成为很多前沿学科的基础。特别是计算机科学的长足进步，给组合数学注入了新的生机和活力，组合数学的离散性及其算法与计算机的结合已在现代科学技术中发挥出极为重要的作用。它在在自然科学的众多学科，管理科学的很多分支，以及数学中涉及有限多个对象的每个专题中的作用，尤其是因为它在计算机的理论和应用上举足轻重的地位，人们越来越认识到这个数学分支的重要性。
本课程作为大学数学专业选修课系统地介绍了组合数学的基本原理与算法。主要内容有组合数学的研究对象、排列与组合、容斥原理及其应用、递推关系、生成函数、鸽巢原理和Ramsey定理、Polya定理。 七、教学目的：
通过组合数学的学习，锻炼学生的论证能力，用组合学的思想和方
法培养学生分析问题和解决问题的能力。使学生能得到严格的逻辑推理与抽象思维能力的训练，了解数学中的抽象思维、建立数学模型与计算机科学实践之间的内在联系，不仅提高专业开发能力，而且为其它课程的学习打好数学基础。具体来说，通过本课程的学习，应达到知识和能力两方面的目标，知识方面：系统地学习组合数学中的排列与组合、容斥原理及其应用、递推关系、生成函数、鸽巢原理和Ramsey定理、Polya定理。为解决实际问题打好知识基础。能力方面：使学生能得到组合数学的思想、方法和理论严格的逻辑推理与抽象思维能力的训练，了解数学中的抽象思维与实践之间的内在联系，提高分析问题和解决问题的能力。
八、学时分配表
教学内容(章) 第一章 引言 第二章 鸽巢原理和Ramsey定理 第三章 排列和组合 第四章 二项式系数 第五章 容斥原理 第六章 递推关系 第七章 生成函数 第八章 Polya定理 理论学时 1 4 4 5 13 6 7 4 实验学时 习题课 1 1 1 2 2 2 1 其它 备注 九、教学基本内容： 第一章 引言 1学时 教学要求：
本章的目的要求是：了解组合数学的起源与发展状况；弄清组合数学的研究对象及要解决的问题。
本章的重点是组合数学的研究对象及要解决的问题。 教学内容：
一、 组合数学的起源
二、 组合数学的研究对象及目的 鸽巢原理和Ramsey定理 5学时 教学要求：
本章的目的要求是：掌握鸽巢原理的简单形式与加强形式；会用鸽巢原理解决实际问题；理解Ramsey定理；了解Ramsey定理的发展状况。
本章的重点是鸽巢原理及其应用。难点是鸽巢原理的加强形式；Ramsey定理。 教学内容：
一、 鸽巢原理的简单形式及其应用 1． 鸽巢原理的一般形式 2． 具体实例 二、 鸽巢原理的加强形式 1． 鸽巢原理的加强形式定理 2． 实例 三、 Ramsey定理
第二章 排列与组合 5学时 教学要求：
本章的目的要求是：理解加法法则与乘法法则；掌握集合的排列与组合；掌握多重集的排列与组合。
本章的重点是集合的排列与组合；多重集的排列与组合。难点是多重集的排列与组合。 教学内容：
一、 加法法则与乘法法则 1． 加法法则 2． 乘法法则 二、 集合的排列与组合 1． 不允许重复的排列问题 2． 不允许重复的组合问题 三、 多重集的排列与组合 1． 多重集的定义 2． 多重集的排列问题 3． 多重集的组合问题 第三章 二项式系数 6学时 教学要求：
本章的目的要求是：会用二项式定理；知道基本的组合恒等式并且会证明；掌握牛顿二项式定理；弄清多项式定理并且会应用。
本章的重点是二项式定理；组合恒等式。难点是组合恒等式的证明及应用。 教学内容： 一、 二项式定理 1． 二项式定理
2． 二项式系数的基本性质 二、 组合恒等式 三、 牛顿二项式定理 四、 多项式定理
第四章 容斥原理 15学时 教学要求：
本章的目的要求是：掌握容斥原理的基本形式，并且会用该原理解决实际问题；理解容斥原理的一般形式并且会用；知道多重集的r-组合数用容斥原理的计算方法；会求错位排列；了解有限制条件的排列问题；掌握有禁区的排列问题。
本章的重点是容斥原理的基本形式；容斥原理的一般形式；多重集的r-组合数的计算方法；有禁区的排列问题。难点是容斥原理的一般形式；有禁区的排列问题。 教学内容： 一、 容斥原理 1． 基本容斥原理 2． 容斥原理的一般形式 二、 多重集的r-组合数 三、 错位排列
四、 有限制条件的排列问题 五、 有禁区的排列问题 1． 车问题
2． 有禁区的排列问题 第五章 递推关系 8学时 教学要求：
本章的目的要求是：能够建立基本的递推关系；了解Fibonacci数列及其基本性质；掌握常系数线性齐次递推关系与常系数线性非齐次递推关系的求解。
本章的重点是常系数线性齐次递推关系与常系数线性非齐次递推关系的求解。这也是本章的难点。 教学内容：
一、 递推关系的建立 二、 Fibonacci数列
1． Fibonacci数列的定义 2． Fibonacci数列的性质 三、 常系数线性齐次递推关系的求解 1． 定义及其性质 2． 解法
四、 常系数线性非齐次递推关系的求解 1． 定义 2． 通解的结构 3． 求特解的方法 第六章 生成函数 9学时 教学要求：
本章的目的要求是：掌握形式幂级数的定义及性质；理解生成函数的定义；掌握普通生成函数的应用；掌握指数型生成函数的应用；了解斯特林数的定义与性质。
本章的重点是普通生成函数的应用；指数型生成函数的应用。这也是本章的难点。 教学内容： 一、 形式幂级数 二、 生成函数的定义 1． 定义 2． 性质
三、 多重集的r-组合数 四、 用生成函数解递推关系
五、 指数型生成函数与多重集的排列问题 1． 指数型生成函数的定义及运算法则 2． 用指数型生成函数解决排列问题 六、 斯特林数 1．第一类斯特林数 2．第二类斯特林数 第八章 Polya定理 5学时 教学要求：
本章的目的要求是：理解置换群中的共轭类与轨道的定义及其性质；掌握Polya定理的特殊形式及其应用；了解带权的Polya定理。
本章的重点是Polya定理的特殊形式及其应用。也是本章的难点。 教学内容：
一、置换群中的共轭类与轨道 1．置换群中的共轭类的定义 2．置换群中的共轭类的性质 3．轨道的定义 4．轨道的性质
二、Polya定理的特殊形式及其应用
1．Polya定理的特殊形式 2．Polya定理的应用 三、带权的Polya定理 十、实验部分：（无）
十一、主要教材及教学参考书：
教材：屈婉玲，组合数学，北京大学出版社出版，1989年11月出版 教学参考书：
1． 曹汝成，组合数学，华南理工大学出版社，2000年出版 2． 卢开澄，组合数学，清华大学出版社，1983年出版 3． 李乔，组合数学基础，高等教育出版社，1993年出版
执笔人：汪定国审定人：李忠碧院（系）负责人：李世宏2006年8月2006年8月2006年8月
因篇幅问题不能全部显示，请点此查看更多更全内容