《组合数学》教学大纲

1、组合数学Combinatorial Mathematics一、课程基本情课程类别：专业任选课课程学分： 2学分课程总学时： 32学时，其中讲课：32 学时，实验（含上机）：0学时，课外0学时课程性质：选修开课学期：第5学期先修课程：离散数学，高等代数适用专业：信息与计算科学教 材：卢开澄，卢华明，组合数学(第4版)，清华大学出版社，2006。开课单位：数学与统计学院，信息与计算科学系二、课程性质、教学目标和任务组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。本课程主要通过组合数学的学习，锻炼学生的论

2、证能力，用组合学的思想和方法培养学生分析问题和解决问题的能力。使学生能得到严格的逻辑推理与抽象思维能力的训练，了解数学中的抽象思维、建立数学模型与计算机科学实践之间的内在联系，不仅提高专业开发能力，而且为其它课程的学习打好数学基础。具体来说，通过本课程的学习，应达到知识和能力两方面的目标，知识方面：系统地学习组合数学中的排列与组合、递推关系、生成函数、容斥原理及其应用、鸽巢原理和Ramsey定理、Plya定理。为解决实际问题打好知识基础。能力方面：使学生能得到组合数学的思想、方法和理论严格的逻辑推理与抽象思维能力的训练，了解数学中的抽象思维与实践之间的内在联系，提高分析问题和解决问题的能力。三

3、、教学内容和要求第1章 绪论（1学时）（1）理解组合数学的性质、研究对象、方法、特点与意义； （2）理解组合数学三问题：存在问题、计数问题、优化问题；（3）了解组合数学的历史和应用；（4）了解本课的学习内容、意义与目标；重点：组合数学的性质、研究对象，组合数学的三问题难点：组合数学的三问题第2章 排列与组合（7学时）（1）掌握加法法则与乘法法则；（2）理解一一对应概念；（3）理解排列与组合的概念：掌握组合的主要性质熟练掌握排列数与组合数的计算方法；（4）掌握圆周排列的求法；（5）了解全排列与组合的生成方法；（6）掌握允许重复的组合与不相邻的组合；（7）理解组合意义的解释；（8）了解Stir1i

4、ng公式和Stir1ing数；重点：排列与组合的概念、计算方法难点：允许重复的组合与不相邻组合，组合解释第3章 递推关系与母函数（12学时）（1）理解母函数与递推关系的基本概念；（2）掌握母函数的性质；（3）理解Fibonacci序列及其在优选法中的应用；（4）理解线性递推关系的概念，掌握常系数线性递推关系的解法；（5）掌握建立简单问题的递推关系式的方法；（6）理解整数拆分的意义和方法，掌握Ferrers图像的性质；（7）理解指数生成函数的概念，会用它解有关简单问题；（8）了解广义二项式定理和非线性递推关系的应用；重点：母函数的概念与性质，常系数线性递推关系的解法难点：母函数的用法，整数拆分的

5、方法第4章 容斥原理与鸽巢原理（7学时）（1）理解De Morgan定理；（2）理解容斥原理，掌握容斥原理的应用；（3）理解棋盘多项式的意义和应用，掌握利用棋盘多项式计算有禁区排列；（4）了解广义容斥原理和应用；（5）了解第二类Stir1ing数的展开式；（6）理解鸽巢原理的简单形式，掌握鸽巢原理应用；（7）理解鸽巢原理的一般形式；（8）了解Ramsey问题和Ramsey数的概念；重点：De Morgan定理，容斥原理，鸽巢原理难点：棋盘多项式、广义容斥原理、Ramsey数第5章 Burnside引理与Plya定理（5学时）（1）理解群的概念及性质，理解置换群的概念；（2）掌握Burnside引理的意义及应用；（3）掌握Plya定理的意义及应用；重点：群的概念，Burnside引理 ，Plya定理难点：Burnside引理 ，Plya定理四、课程考核（1）作业等：作业：6次，课程论文： 0篇；（2）考核方式：闭卷考试（3）总评成绩计算方式：平时成绩*20期末考试成绩*80五、参考书目（1）R. A. Brualdi著，冯舜玺，罗平，