加入收藏  || English Version 
 
《组合数学》教学大纲

  发布日期:2015-03-11  浏览量:781


 

前 言

《组合数学》课程是数学与应用数学专业的专业选修课程,也是应用性很强的一门数学课。 本课程主要研究一组离散对象满足一定条件的安排的存在性,以及这种安排的构造,枚举计数及优化问题,它是整个离散数学的一个重要组成部分。目前组合数学不仅成为数学中的一个重要分支,而且还成为计算机科学,管理科学及其它学科的数学基础。

 

设置本课程的目的是:一方面使学生学好作为专业课程的组合数学课,为组合方向的后续研究打下基础;另一方面培养学生理论联系实际和分析问题、解决问题的能力,会用组合的想法解决实际问题。

 

学习本课程的要求是:通过本课程的学习,要使学生具有现代数学的观点和方法,初步掌握常用组合计数的构造思想和计算方法。要求掌握鸽巢原理、排列组合原理、容斥原理、递推关系与生成函数。同时,也要培养学生抽象思维和慎密概括的能力,使学生具有良好的开拓专业理论的素质和使用所学知识,分析和解决实际问题的能力。

先修课程要求数学分析,高等代数,概率论

本课程计划72学时,3学分

选用教材:孙淑玲 许胤龙编著,组合数学引论,中国科技大学出版社,

2005

教学手段课堂讲授为主,习题课与讨论课为辅

考核方法:闭卷书面考试

 

 

教学进程安排表

 

周次

 

学时数

 

 

 

 

教学环节

 

备注

1

2

鸽巢原理的简单形式及其应用

 

讲课

 

1

2

鸽巢原理的加强形式,相关推论

 

讲课

 

2

2

Ramsey问题的提出及证明,Ramsey数及其相关结论

讲课

 

2

2

Ramsey数的推广形式, Ramsey定理

 

讲课与习题课相结合

 

3

2

加法原则与乘法原则,排列与组合,

多重集合的排列与组合

讨论课

 

3

2

二项式定理与二项式系数的基本性质

组合恒等式,多项式定理

讲课

 

4

2

集合的分化与第二类Stirling数的相关定理

讲课

 

4

2

正整数的分拆,有序分拆及其相关定理

无序分拆及其相关定理

讲课

 

5

2

分拆的Ferrers图,Ferrers图的共轭图

讲课

 

5

2

分配问题的基本想法,分配问题的实例

 

讲课与习题课相结合

 

6

2

容斥原理的引入背景,容斥原理的简单实例

讲课

 

6

2

容斥原理的一般形式及其证明,容斥原理的几个推论,

讲课

 

7

2

容斥原理的进一步讨论

 

讲课

 

7

2

具有有限重复数的多重集合的r组合数问题,  错排问题

讲课

 

8

2

有禁止模式的的排列问题,ménage问题与ménage

讲课

 

8

2

Möbius函数的定义,Möbius反演定理及其证明

讲课

 

9

2

可重复排列问题

讲课与习题课相结合

 

9

2

递推关系的概念,递推关系的建立

 

讲课

 

10

2

常系数线性齐次递推关系的概念与解的结构

讲课与习题课相结合

 

10

2

常系数线性齐次递推关系的求解过程与应用举例

讲课

 

11

2

常系数线性非齐次递推关系的概念与解的结构

讲课

 

11

2

常系数线性非齐次递推关系的求解过程与应用举例

讲课

 

12

2

Fibonacci数的引入,组合意义,推倒过程与应用举例

讲课

 

12

2

Catalan数的引入,组合意义,推倒过程与应用举例

讲课与习题课相结合

 

13

2

生成函数的引入与举例,形式幂级数的概念

讲课

 

13

2

形式幂级数的基本性质,形式幂级数的形式导数

讲课

 

14

2

生成函数的性质与证明

 

讲课

 

14

2

几种常见的简单数列生成函数的求解

 

讲课

 

15

2

用生成函数求解常系数线性齐次递推关系的具体方法

讲课

 

15

2

用生成函数求解常系数线性非齐次递推关系的具体方法

讲课

 

16

2

组合数的生成函数,排列数的指数型生成函数

讲课

 

16

2

分拆数的生成函数, 组合型分配问题的生成函数

讲课

 

17

2

排列型分配问题的生成函数,有限制位置的排列

讲课

 

17

2

有限制位置的排列的基本结论,棋子多项式

讲课

 

18

2

复习

习题课

 

18

2

复习

习题课

 

 

 

 

 

 

 

第一章  预备知识

一、学习目的

通过本章的学习,要求学生掌握鸽巢原理与鸽巢原理的加强形式,并会用鸽巢原理与鸽巢原理的加强形式讨论和解决实际问题。理解Ramsey问题,会讨论简单的Ramsey数,了解Ramsey的推广形式和Ramsey定理。本章计划8学时。

二、课程内容

§11 鸽巢原理的简单形式

鸽巢原理的简单形式, 利用鸽巢原理解决实际问题。

§12 鸽巢原理的加强形式

鸽巢原理的加强形式及推论,鸽巢原理加强形式的应用举例。

§13  Ramsey问题与Ramsey

   经典Ramsey问题的提出与证明, Ramsey问题的延伸,Ramsey数及其相关定理。

§14  Ramsey数的推广

Ramsey问题与Ramsey数的推广形式, Ramsey定理及其证明。

 

三、教学基本要求

了解:经典Ramsey问题的引入,Ramsey定理。

理解:鸽巢原理与鸽巢原理的推广形式。鸽巢原理所体现的组合思想。

掌握:利用鸽巢原理解决实际问题,判断简单Ramsey数的方法。

 

四、重点、难点提示和教学手段

(一)本章重点

鸽巢原理的应用,Ramsey 数的判定。

(二)本章难点

Ramsey定理及其证明。

(三)教学手段

课堂讲授与习题课相结合

五、思考与练习

思考:如何将鸽巢原理和Ramsey定理有机的联系起来。

练习由授课教师自行确定。

 

第二章  基本计数问题

一、学习目的

通过本章的学习,熟练掌握加法原则,乘法原则,排列组合及二项式定理及其相关结论,理解集合的分化和正整数分拆的思想。掌握第二类Stirling数的相关性质。能够给出分拆的Ferrers图,能够求解简单的分配问题,并能分析,解决实际问题。本章计划14学时。

二、课程内容

§21 加法原则和乘法原则

加法原则及其相关定理, 乘法原理及其相关定理。

§22 排列与组合

排列的基本定义,排列数,组合的定义,组合数,排列数与组合数的应用举例。

§23 多重集合的排列与组合

多重集合的概念,多重集合排列的概念与基本定理,多重集合组合的概念与基本定理,增字。

§24 二项式系数

二项式定理,二项式定理的基本性质(对称关系,递推关系,单峰性)与组合意义。一些组合恒等式,多项式定理。

§25 集合的分化与第二类Stirling

集合分化的定义,第二类Stirling数的定义及相关性质。

§26 正整数的分拆

正整数分拆的定义 。有序分拆的定义及相关结论,无序分拆的定义及相关结论,正整数分拆的Ferrers图与共轭。利用分拆的Ferrers图证明的关于分拆的基本结论。

§27 分配问题

分配问题的提出及分析。

三、教学基本要求

理解:多重集合的概念,集合的分化和正整数分拆的思想。

掌握:加法原则,乘法原则,排列组合,多重集合的排列组合及二项式定理及其相关结论,第二类Stirling数的相关性质,实际应用的分配问题。

四、重点、难点提示和教学手段

(一)本章重点

多重集合的概念及其排列组合,二项式定理及其基本性质,Stirling数的性质。

(二)本章难点

有序分拆,无序分拆的相关结论。

(三)教学手段

课堂讲授与讨论课、习题课相结合                                         

五、思考与练习

思考:讨论几种分配问题之间的联系。

练习由授课教师自行确定。

第三章  容斥原理

一、学习目的

通过本章的学习,掌握一种重要的组合计数方法:容斥原理。了解容斥原理引入的背景,理解容斥原理原理的思想,会用容斥原理解决一些实际问题,了解Möbius反演及可重复圆排列的思想。本章计划16学时。

二、课程内容

§31 引论

容斥原理引入的背景及重要意义,容斥原理在几个简单问题上的应用。

§32 容斥原理

容斥原理及其证明,容斥原理的推论及其证明。

§33 容斥原理的应用

    具有有限重复数的多重集合的人r组合数问题,错排问题,有禁止模式的错排问题, ménage问题及既化的ménage问题,实际依赖于所有变量的函数个数的确定问题。

§34  Möbius反演及可重复的圆排列

Möbius函数的定义,Möbius反演定理及其证明,可重复排列问题。

三、教学基本要求

理解:理解容斥原理原理的思想,Möbius函数的概念。

了解:容斥原理引入的背景及重要意义,了解Möbius反演及可重复圆排列的思想。

掌握:利用容斥原理解决组合计数问题。

四、重点、难点提示和教学手段

(一)本章重点

容斥原理的思想及表达形式,具有有限重复数的多重集合的人r组合数问题,

错排问题,可重复排列问题。

(二)本章难点

Möbius反演及可重复圆排列,容斥原理解决组合计数问题

(三)教学手段

课堂讲授与习题课相结合

 

五、思考与练习

思考与练习由授课教师自行确定。

 

第四章  递推关系

一、学习目的

通过本章的学习,理解递推关系内在的组合结构,掌握递推关系的建立方法,掌握几种特殊递推关系的求解方法。了解几种特殊的递推关系:Fibonacci数列合Catalan数列。本章计划14学时。

二、课程内容

§41 递推关系的建立

递推关系的概念,几个实例递推关系的建立。

§42 常系数线性齐次递推关系的求解

k阶常系数线性齐次递推关系的概念,递推关系特征根的定义,k阶常系数线性齐次递推关系解的结构,k阶常系数线性齐次递推关系求解的一般方法。

§43常系数线性非齐次递推关系的求解

k阶常系数线性非齐次递推关系的概念, k阶常系数线性非齐次递推关系通解的结构,k阶常系数线性非齐次递推关系求解的一般方法,k阶常系数线性非齐次递推关系应用举例。

§44 用迭代归纳法求解的递推关系

用迭代归纳法求解的递推关系基本思想,用迭代归纳法求解的递推关系步骤,应用举例。

§45 Fibonacci数与Catalan

   Fibonacci数列的引入背景与组合意义,Fibonacci数的求解过程。Catalan数列的引入背景与组合意义,Catalan数列的求解过程,应用举例。

三、教学基本要求

理解:k阶常系数线性齐次递推关系求解的思想,k阶常系数线性非齐次递推关系求解的基本思想,迭代归纳法求解递推关系的基本思想。

了解:Fibonacci数列与Catalan数列的引入背景及组合意义。

掌握:递推关系的建立方法, k阶常系数线性()齐次递推关系通解的结构与一般解法。

四、重点、难点提示和教学手段

(一)本章重点

递推关系的建立过程,k阶常系数线性齐次递推关系通解结构,k阶常系数线性齐次递推关系求解的一般方法。

(二)本章难点

k阶常系数线性非齐次递推关系通解的结构。迭代归纳法求解的递推关系基本思想与具体步骤。

(三)教学手段

课堂讲授与习题课相结合。

五、思考与练习

思考与练习由授课教师自行确定。

 

第五章  生成函数

一、学习目的

通过本章的学习, 了解生成函数引入的背景,理解形式幂级数的相关概念,了解形式幂级数的一些基本性质,掌握利用生成函数求解递推关系的方法,会利用生成函数讨论一些组合计数问题。本章计划20学时。

二、课程内容

§51 引论

生成函数的引入与应用举例。

§52 形式幂级数

形式幂级数的概念,形式幂级数的相等,形式幂计数的数乘,加法,代数分析。形式幂级数的形式导数及相关性质。

§53 生成函数的性质

生成函数的基本性质及其证明过程,几个常见的生成函数。

§54 用生成函数求解递推关系

用生成函数求解递推的基本想法与步骤,用生成函数求解常系数线性齐次递推关系的方法,通解形式。用生成函数求解常系数线性非齐次递推关系的方法,通解形式。

§55  生成函数在计数问题中的应用

几类特殊的生成函数,组合数的生成函数,排列数的指数型生成函数,分拆数的生成函数,组合型分配问题的生成函数,排列型分配问题的生成函数。

§56 有限位置的排列及棋子多项式

有限制位置的排列的理论推倒,棋盘问题与棋子多项式。

三、教学基本要求

理解:形式幂级数的相关概念,利用生成函数求解组合计数问题的想法。

了解:生成函数引入的背景,有限制位置的排列与棋盘问题。

掌握:用生成函数求解常系数线性齐次递推关系的方法,通解形式。用生成函数求解常系数线性非齐次递推关系的方法,通解形式。

 

四、重点、难点提示和教学手段

(一)本章重点

形式幂级数的概念。用生成函数求解常系数线性齐次递推关系的方法,通解形式。

(二)本章难点

用生成函数求解常系数线性非齐次递推关系的方法,通解形式。棋子多项式。

(三)教学手段

课堂讲授与习题课相结合。

五、思考与练习

思考与练习由授课教师自行确定。

 

 

阅读书目(或参考文献)

1 卢开澄, 卢华明著, 组合数学(第3版),清华大学出版社,2002

2 (美)RICHARD A. BRUALDI INTRODUCTORY COMBINATORICS (THIRD EDITION),机械工业出版社,2002

3 潘永亮, 徐俊明著,组合数学,科学出版社,2006

 

打印此页】【顶部】【关闭
   
版权所有 © 2007-2017 安徽大学数学科学学院 All rights reserved 皖ICP备05018241号
地址:安徽省合肥市九龙路111号安徽大学磬苑校区理工楼H楼 邮编:230601 E-mail:math@ahu.edu.cn
访问统计:自2013年9月1日以来总访问:1000  后台管理