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