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

1、组合数学课程教学大纲课程名称组合数学课程编码131510038课程类型（学院内）跨专业课程适用范围数学与应用数学学分数2先修课程高等数学、初等数学研究等课程学时数32其中实验学时其中实践学时考核方式考查制定单位数学与信息科学学院执笔者 审核者一、教学大纲说明（一）课程的性质、地位、作用和任务组合数学是高等师范院校数学及计算机专业的专业选修课之一，是专业主干课。随着计算机的广泛使用，对计算机的算法的研究变得日益重要。其中组合算法解决搜索、排序、组合优化等问题，而它的数学基础就是组合数学。本课程主要学习组合计数的各种方法和技巧，有包含排斥原理的应用，递推关系和生成函数法等。通过该课程的学习，使学生

2、正确理解组合数学的基本概念，深入掌握基本理论和主要方法，为学习组合优化、图论等后继课程打下基础。通过该课程的学习，可以训练学生提高分析问题和初步解决某些实际问题的能力。（二）课程教学的目的和要求通过本课程的学习，理解组合理论的基本概念，掌握组合理论的基本方法和技巧，了解一些简单算法，为深入研究组合数学打好基础。课程要求掌握排列组合原理、鸽巢原理和包含排斥原理、组合恒等式、生成函数与递推关系，并能应用这些方法解决某些实际问题。掌握：鸽巢原理、集合及多重集的排列和组合、二项式定理、组合恒等式、非降路径问题、牛顿二项式定理、多项式定理、包含排斥原理、多重集的组合数、错位排列、有限制条件及有禁区的排列

3、问题、Fibonacci数列、递推关系的求解、生成函数与多重集的组合数、指数生成函数与多重集的排列数。理解：鸽巢原理的加强形式、Ramsey定理、用生成函数求解递推关系、Catalan数和Stirling数。了解：Poly定理。（三）课程教学方法与手段根据学生的实际情况，因地制宜。讲授为主，占总课时80%，习题课占20%。尽量结合实际问题，激发学生学习的兴趣。（四）课程与其他课程的联系本课程与数学系的基础课程数学分析、线性代数有一定联系，是后继学科如组合优化、图论等的重要基础。（五）教材与教学参考书教材：曹汝成编，组合数学，华南理工大学出版社，2005年参考书: 1、卢开澄编，组合数学算法与分

4、析（上册），清华大学出版社2、刘振宏编著，应用组合论，高教出版社二、课程的教学内容、重点和难点第一章 引言组合数学背景、基本概念（组合数学、存在性问题、组合计数问题、优化问题）、通过实例介绍组合学特有的技巧和方法重点：背景与基本概念；难点：通过实例介绍组合学特有的技巧和方法。第二章 鸽巢原理和Ramsey定理鸽巢原理的简单形式及其应用、鸽巢原理的加强形式、Ramsey定理。重点：鸽巢原理的简单形式。难点：鸽巢原理的应用。第三章 排列和组合加法法则和乘法法则、集合的排列和组合、多重集的排列和组合。重点：排列和组合问题的计数。难点：多重集的排列和组合问题的计数。第四章 二项式系数二项式定理、组合恒

5、等式、非降路径问题、牛顿二项式定理、多项式定理。重点：二项式定理、组合恒等式、多项式定理。难点：组合恒等式的证明。第五章 包含排斥原理包含排斥原理、多重集的r-组合数、错位排列、有限制条件的排列问题、有禁区的排列问题。重点：包含排斥原理、多重集的r-组合数、错位排列。难点：有禁区的排列问题。第六章 递推关系Fibonacci数列及性质、常系数线性递推关系的求解、常系数非线性递推关系的求解、用迭代和归纳法求解递推关系。重点：Fibonacci数列的性质、常系数线性递推关系的求解、常系数非线性递推关系的求解。难点：用迭代和归纳法求解递推关系。第七章 生成函数生成函数的定义及性质、多重集的r-组合数、用生成函数来求解递推关系、正整数的剖分、指数生成函数与多重集的排列问题、Catalan数和Stirling 数。重点：用生成函数来计算多重集的组合数、用指数生成函数来计算多重集的排列数。难点：多重集的排列问题。三、学时分配教学内容各教学环节学时分配采用何种多媒体教学手段章节主要内容学时分配讲授实验讨论习题实践其它一引 言11多媒体二鸽巢原理和Ra