组合数学教学大纲(72学时)

《组合数学教学大纲(72学时)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《组合数学》课程教学大纲【课程名称】组合数学（Combinatorics）【课程代码108012004【适应专业】数学与应用数学【授课对象】普通本科【课程简介】组合数学是计算机出现以后迅速发展起来的一门数学分支。组合数学不仅在基础数学研究屮具有极其重要的地位，在其它的学科屮也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。本课程主要介绍组合数学涉及的基本计数问题、鸽巢原理、容斥原理、递推关系与母函数、生成函数、Polya计数理论等基本内容。【教学目标】通过组合数学的学习，使学生了解和掌握组合数学的基本内容和基

2、本方法，培养学生的应用意识，为学生在今后的教学或科研活动屮可能的应用做好准备。【参考学时】72学时【参考书目】1.卢开澄，卢华明编著：《组合数学（第4版），北京：清华大学出版社，2006年2.姜建国，岳建国编著：《组合数学》（第2版），西安：西安电子科技大学出版社，2007年3.李乔编著：《组合学讲义》，北京：高等教育出版社，2008年4.布鲁迪（BrualdiR.A.）编著：《组合数学》（原书第4版）,北京：机械工业出版社,2005年【教学内容】•第一单元基本计数问题•§1加法原理与乘法原理§2排列与组合§3多重集合的排列与组合§4二项式

3、系数§5集合的分划与第二类Stirling数§6正整数的分拆§7分配问题综述•基本要求：1.理解并掌握多重集合的排列与组合问题中一些结论及其证明过程，第二类Stirling数及正整数分拆数的递推公式及其证明方法；2.掌握儿种组合恒等式的证明方法，理解Ferrers图的含义及其应用于正整数的无序分拆的意义；3.理解并熟练掌握八种分配问题的计数方法；4.熟练利用组合分析的方法证明组合恒等式及某些计数问题。•重点、难点：八种基本的计数问题的求解方法；第二类Stirling数及正整数分拆数的递推公式及其证明方法，以及用组合分析的方法证明组合恒等式及

4、某些计数问题。•教学方法提示：讲授法参考学时：12学时•第二单元鸽巢原理•§1鸽巢原理的简单形式§2鸽巢原理的加强形式§3Ramsey问题与Ramsey数§4Ramsey数的推广•基本要求：1.了解组合数学的基本问题；2.理解鸽巢原理及其加强形式的内容和Ramsey数及推广的Ramsey数的含义；3.掌握用鸽巢原理证明一些组合问题的存在性的方法，掌握Ramsey数及推广的Ramsey数的性质。•重点、难点：鸽巢原理及其加强形式、Ramsey数的定义；用鸽巢原理证明问题的方法。•教学方法提示：讲授法•参考学时：10学吋•第三单元容斥原理•§1

5、容斥原理§2容斥原理的应用§3麦比乌斯反演及可重复的圆排列•基本要求：1.记住容斥原理的内容，理解其证明方法；2.能运用容斥原理解决具有有限重复数的多重集合的r组合数问题、错排问题、有禁止模式的排列问题和实际依赖于所有变量的函数个数的确定问题：3.记住麦比乌斯反演公式的形式，理解其证明过程，能运用它解决可重复的圆排列问题。•重点、难点：容斥原理的内容及其证明方法;有禁止模式的排列问题和实际依赖于所有变量的函数个数的确定问题和可重复的圆排列问题。•教学方法提示：讲授法•参考学时：10学时•第四单元递推关系与母函数•§1递推关系§2母函数及其性

6、质§3常系数线性齐次递推关系的求解§4常系数线性非齐次递推关系的求解§5Fibonacci数和Catalan数•基本要求：1.理解并掌握母函数及其性质；2.掌握儿种递推关系的建立方法；3.理解并掌握常系数线性齐次及非齐次递推关系的求解方法；能运用迭代归纳法求解递推关系；4.记住并理解Fibonacci数和Catalan数的定义及递推公式，会推导Fibonacci数和Catalan数的一些性质，能运用它们解决一些组合计数问题。•重点、难点：递推关系的建立方法、常系数线性齐次及非齐次递推关系的求解方法、Fibonacci数和Catalan数的定

7、义、递推公式及性质；Catalan数的定义、递推公式及性质。•教学方法提示：讲授法•参考学时：12学吋•第五单元生成函数•§1形式帚级数§2形式幕级数的性质§3用生成函数求解递推关系§4生成函数在计数问题中的应用§5有限制位置的排列及棋子多项式•基本要求：1.理解形式幕级数的來历及其性质；能运用牛成函数求解递推关系；2.握组合数的生成函数、排列数的指数型生成函数、分拆数的生成函数、组合型及排列型分配问题的生成函数的形式，能运用它们解决这些计数问题；3.掌握棋子多项式的形式，能运用它解决有限制位置的排列问题。•重点、难点：生成函数的来历、性质

8、，以及用生成函数解决各类问题的方法；各类组合计数问题的生成函数的确定方法，棋子多项式的应用。•教学方法提示：讲授法•参考学时：14学时•第六单元Polya计数理论•§1置换群的基