《组合数学》课程教学大纲
课程名称： 课程代码: 学 分: 开课单位: 制 订 人： 审 定 人:
组合数学 ZS1051001 3
理学院
英文名称： Combinatorial Mathematics 课程类别: 专业选修 学 时: 48
适用专业: 数学与应用数学（师范教育方向） 审 核 人：
一、课程性质与目的
（一）课程的性质
组合数学是高等师范院校数学与应用数学专业的专业选修课。组合数学起源于古代的数学游戏和美学消遣，它以无穷的魅力激发人们的聪明才智和数学兴趣。组合数学的离散性及其算法与计算机的结合已在现代科学技术中发挥出极为重要的作用。它的一个重要组成部分——试验设计有着重大的应用价值，它的数学原理就是组合设计。用组合设计的方法解决实际应用中的试验设计问题在西方发达国家已经得到了广泛的重视，并投入了大量的人力物力进行相关的研究与产品的开发。所以说，组合数学是一门提高思维分析能力和自我构造算法本领的课程。
（二）课程的目的
通过本课程的学习要求学生理解组合数学的基本概念与基本原理，掌握组合理论的基本方法和技巧，提高学生综合应用排列与组合、代数与编码、优化与规划的能力，为深入研究组合数学打好基础。 二、与相关课程的联系与分工
本课程是数学与应用数学专业的专业选修课，它以数学分析、高等代数、概率论为基础，培养学生逻辑推理能力，科学计算能力，解决实际问题的能力，对离散问题的分析能力，为编程与编码作准备。组合数学不仅在计算机软件科学技术中有着重要的应用价值，在企业管理，交通规划，战争指挥，金融分析，电子工程、数字通讯等诸多领域中也具有广泛而重要的应用。 三、教学内容及要求
第一章 排列与组合
【教学要求】掌握加法法则与乘法法则，会利用排列与组合解决具体的实际问题。
【教学重点】加法法则与乘法法则；一一对应；排列与组合；组合意义的灵活运用；
【教学难点】排列的生成算法；允许重复的组合与不相邻的组合；
1
【教学内容】
第一节 加法法则与乘法法则 第二节 一一对应 第三节 排列与组合 一、 排列与组合的模型 二、 排列与组合问题的举例 第四节 圆周排列 第五节 排列的生成算法 一、 序数法 二、 字典序法 三、 换位法
第六节 允许重复的组合与不相邻的组合 一、 允许重复的组合 二、 不相邻的组合
三、 线性方程的整数解的个数问题 四、 组合的生成 第七节 组合意义的解释 第八节 应用举例 第九节 Stirling公式 *一、 Wallis公式 *二、 Stirling公式的证明 第二章 递推关系与母函数
【教学要求】会利用递推关系与母函数解决实际问题。
【教学重点】递推关系；母函数；Fibonacci序列；优选法与Fibonacci序列的应用；线性常系数齐次递推关系；整数的拆分；
【教学难点】线性常系数非齐次递推关系；Ferrers图像；拆分数估计；指数型母函数；广义二项式定理； 【教学内容】 第一节 递推关系 第二节 母函数 第三节 Fibonacci序列
一、 Fibonacci序列的递推关系 二、 若干等式
第四节 优选法与Fibonacci序列的应用
2
一、 优选法 二、 优选法的步骤 三、 Fibonacci的应用 第五节 母函数的性质
第六节 线性常系数齐次递推关系 第七节 关于线性常系数非齐次递推关系 第八节 整数的拆分 第九节 Ferrers图像 第十节 拆分数估计 第十一节 指数型母函数 一、 问题的提出 二、 指数型母函数的定义 第十二节 广义二项式定理 第十三节 应用举例
第十四节 非线性递推关系举例 一、 Stirling数 二、 Catalan书 三、 举例
第十五节 递推关系解法的补充 第三章 容斥原理与鸽巢原理
【教学要求】能运用容斥原理和鸽巢原解决一些实际问题，并能熟练掌握容斥原理、鸽巢原理的一般形式，了解Ramsey定理。
【教学重点】De Morgan定理；容斥定理；广义的容斥原理；鸽巢原理； 【教学难点】欧拉函数；容斥定理；广义的容斥原理；鸽巢原理；Ramsey数； 【教学内容】
第一节 De Morgan定理 第二节 容斥定理 第三节 容斥原理举例
第四节 棋盘多项式与有限制条件的排列 第五节 有禁区的排列 第六节 广义的容斥原理 一、 容斥原理的推广 二、 一般公式
第七节 广义容斥原理的应用
3
第八节 第二类Stirling数的展开式 第九节 欧拉函数 第十节 n对夫妻问题 第十一节 Mobius反演定理 第十二节 鸽巢原理 第十三节 鸽巢原理举例 第十四节 鸽巢原理的推广 一、 推广形式之一 二、 应用举例 三、 推广形式之二 第十五节 Ramsey数 一、 Ramsey问题 二、 Ramsey数
第四章 Burnside引理与Pólya定理
【教学要求】理解群、置换群、循环、奇循环与偶循环的定义与基本性质；理解并掌握Burnside引理的内容及相关概念，会用Burnside引理解决计数问题；熟练掌握Pólya定理的内容，能运用其解决实际问题。
【教学重点】群、置换群；循环、奇循环与偶循环；Burnside引理；Pólya定理；
【教学难点】Pólya计数定理的推导过程及解决一些简单问题的方法； 【教学内容】 第一节 群的概念
一、 定义 二、 群的基本性质 第二节 置换群
第三节 循环、奇循环与偶循环 第四节 Burnside引理
一、 若干概念 二、 重要定理 三、 举例说明 第五节 Pólya定理 第六节 举例
第七节 母函数形式的Pólya定理 第八节 图的计数 第五章 区组设计
【教学要求】理解拉丁方与正交的拉丁方的定义及其性质；了解域、Galois域理论，理解均衡不完全区组设计（BIBD）的基本概念与定理；了解Steiner三
4
元素与Kirkman女生问题。
【教学重点】拉丁方与正交的拉丁方；域、Galois域；均衡不完全区组的设计；
【教学难点】均衡不完全区组设计（BIBD）相关定理的证明； 【教学内容】 第一节 问题的提出
第二节 拉丁方与正交的拉丁方
一、 问题的引入 二、 正交拉丁方及其性质 第三节 域的概念
第四节 Galois域GF（pm） 第五节 正交拉丁方的构造 第六节 正交拉丁方的应用举例 第七节 均衡不完全的区组设计
一、 基本概念 二、 （b,v,r,k,?）-设计 第八节 区组设计的构成方法 第九节 Steiner三元素 第十节 Kirkman女生问题 *第六章 线性规划 【教学内容】 第一节 问题的提出 第二节 线性规划的问题 第三节 凸集
第四节 线性规划的几何意义 第五节 单纯形法的理论基础
一、 松弛变量 二、 解的充要条件 第六节 单纯形法与单纯性表格 第七节 改善的单纯形法 第八节 对偶概念 第九节 对偶单纯形法 *第七章 编码简介 【教学内容】 第一节 基本概念 第二节 对称二元信道 第三节 纠错码
5