《组合数学》课程教学大纲

1、组合数学课程教学大纲课程编码：171220020课程性质：专业方向任选课程适用专业： 信息与计算科学专业学时学分： 32学时、2学分所需先修课：高等代数、数学分析编写单位： 数学与信息科学系一、课程说明 1、课程简介组合数学是数学与信息科学系数学、统计、信计专业本科学生的专业选修课程。组合数学与图论、数论、线性代数、群论等有着密切联系，并有着广泛的应用性。主要介绍组合数学的基本内容和方法，其主要内容有：抽屉原理、排列与组合、容斥原理、递归关系、母函数以及各类应用问题。本课程不仅是专业提高课程，也是学生进入相关研究生课程学习的重要基础课，同时也是学生走向工作岗位，进行中学教学及数学竞赛辅导的必备

2、知识。各章节的内容基本是按照本专业学生的培养目标的需要予以安排，在内容的深浅阐释上，尽量考虑不同层次、不同专业的需要。2、教学目标要求 本课程的教学目标是使学生掌握组合数学的基本概念与理论、基本证题方法和基本解题技巧，进一步提高学生抽象思维和逻辑推理能力，提高他们的数学修养，初步了解现代数学研究的基本思想和方法，为学生将来进一步学习其它学科及从事中学数学教育打下坚实的基础。3、教学重点难点本课程的重点是：抽屉原理、容斥原理、递归关系、母函数、本课程的难点是：容斥原理、递归关系、母函数以及各类应用问题。4、考核方式 本课程是考查课；考试的形式：闭卷；成绩的合成及评分标准：平时占40、期末占：60

3、。5、学时分配表章次教学内容理论课学时数实验（实践）课学时数第一章抽屉原理3第二章排列与组合32第三章容斥原理62第四章递归关系62第五章母函数62小计208总计32二、各部分教学纲要第一章 抽屉原理（3学时）教学目标：1.熟练掌握复合集的概念及其运算；2.熟练掌握抽屉原理的各种形式及应用；3.熟练掌握抽屉原理的应用技巧。本章重点：抽屉原理的各种形式。本章难点：抽屉原理的应用技巧。教学内容第一节 集合的基本概念1.集合的基本概念1.1 集合；1.2 复合集。2.集合的基本运算2.1 集合的运算及运算律；2.2 复合集的运算及运算律。第二节 抽屉原理1.有限个元素的抽屉原理；2.无穷个元素的抽屉

4、原理。第三节 应用举例1.在几何中的应用举例；2.在代数中的应用举例；3.其它方面的应用举例。第二章 排列与组合（3学时）教学目标：1熟练掌握加法原理与乘法原理及其应用；2掌握线排列、圆周排列的计数公式；3掌握不重复组合、重复组合的计数公式；4掌握二项式定理的用法。本章重点：圆周排列及计数公式、重复组合及计数公式。本章难点：圆周排列及计数公式、重复组合及计数公式。教学内容第一节 加法原理与乘法原理1.加法原理及应用举例2.乘法原理及应用举例第二节 排列1.相异元素不允许重复的排列及应用举例；2.相异元素允许重复的排列及应用举例；3.圆周排列及应用举例。第三节 组合1.相异元素不允许重复的组合及

5、应用举例；2.相异元素允许重复的组合及应用举例；3.相异元素不允许重复的组合和允许重复的组合的关系；4.相异元组合数的性质；5.二项式定理及应用。第三章 容斥原理（8学时）教学目标：1熟练掌握容斥原理的各种形式；2掌握错排数的计算公式；3掌握容斥原理的用法。本章重点：容斥原理的各种形式、错排数的计算公式。本章难点：容斥原理的用法:构造集合，利用容斥原理解决计数问题。教学内容第一节 引言1.简单的计数问题举例。第二节 容斥原理1.容斥原理的各种形式；2.利用容斥原理推导数论中的欧拉函数表达式。第三节 应用举例1.利用容斥原理解决计数问题举例；2.错排数的计算公式。第四章 递归关系（8学时）教学目

6、标： 1.熟练掌握斐波那契数列的定义、通项公式、斐波那契数列的性质；2.熟练掌握常系数线性齐次递归关系在各种情况下的求通解的公式；3.掌握利用递归关系解决实际问题的方法；4.了解差分的概念和性质；5.了解利用迭代和归纳求某些递归关系方法。本章重点：斐波那契数列、常系数线性齐次递归关系、迭代和归纳。本章难点：常系数线性齐次递归关系、迭代和归纳、差分。教学内容第一节 斐波那契数列1.斐波那契数列1.1斐波那契数列的定义；1.2斐波那契数列的性质。2.斐波那契数列的应用。第二节 常系数线性齐次递归关系1. 常系数线性齐次递归关系1.1常系数线性齐次递归关系的定义；1.2 特征方程、特征根2.常系数线

7、性齐次递归的解法1.1特征根无重根时常系数线性齐次递归关系的解法；1.2特征根有重根时常系数线性齐次递归关系的解法；1.3应用举例。第三节 迭代和归纳1.利用迭代将递归关系化为常系数线性齐次递归关系；2.利用归纳法求递归关系的解。3.应用举例。第四节 差分表1.差分、差分表的定义；2.差分的的性质。3.应用举例。第五章 母函数（8学时）教学目标：1.掌握母函数的定义及应用；2.掌握一些非常系数线性齐次递归关系的求通解的方法；3.了解指数型母函数的定义及应用。本章重点：母函数的定义及应用、一些非常系数线性齐次递归关系的求通解的方法。本章难点：利用母函数求一些非常系数线性齐次递归关系的通解的方法。教学内容第一节 母函数1.母函数的定义；2.常系数线性齐次递归关系的母函数。第二节 其它递归关系1.利用母函数求一些非常系数线性齐次递归关系的通解；2.母函数的其它应用。第三节 指数型母函数1.指数型母函数的定义；2.利用指数型母函数求解一些计数问题。三、使用教材及参考书使用教材：陈景林、阎满富主编，组合数学与图论，中国铁道出版社