《组合数学》教学大纲
一、课程基本信息
1、课程中文名称：组合数学 2、课程类别：专业选修课
3、适用专业：数学与应用数学、计算机专业 4、课程地位：专业选修课 5、总学时：30学时 6、总学分：2
7、先修课程：数学分析、微分方程、高等代数
二、课程目标
1、组合数学是计算机应用领域中十分重要的基础理论课程，是计算机应用技术研究生的学位专业基础课。学习该课程的主要目的是使学生掌握组合数学的理论、技术和方法。应用组合数学方法解决实际工作中的计算机应用问题。组合数学是一门提高思维分析能力和自我构造算法本领的必修课程。
2、通过组合数学这门课程的学习，可以有效地锻炼学生的论证能力，培养学生用组合学的思想和方法分析问题和解决问题的能力。使学生能得到严格的逻辑推理与抽象思维能力的训练，建立数学模型与计算机科学实践之间的内在联系，不仅可以提高专业开发能力，而且为计算机教育打好数学基础。通过本课程的学习，应达到知识和能力两方面的目标：(1)知识方面：系统地学习组合数学中的排列与组合、容斥原理及其应用、递归关系、生成函数、整数的分拆、鸽巢原理和 定理、二分图问题和组合设计。为解决实际问题，提高计算机专业开发能力打好知识基础。 (2)能力方面：使学生能得到组合数学的思想、方法和理论严格的逻辑推理与抽象思维能力的训练，了解数学中的抽象思维与计算机科学实践之间的内在联系，提高分析问题和解决问题的能力
3、本课程开设时间比较灵活，总学时数为30学时。
三、课程内容
第一章 排列与组合（8学时）
[教学目的与要求]
本部分集中介绍排列和组合。使学生认识到排列和组合是组合数学研究的最简单、最基本的课题。通过三个基本计数原理及排列、组合公式的研究，进一步讨论了几个计数问题，能体会要想完满地解决一个排列和组合问题，往往需要较强的组合思维、巧妙的组合方法、熟练的组合技巧。本章内容初步展示了组合数学的迷人魅力，有利于激发学生学习后续内容的兴趣。
§1.1 加法规则和乘法规则
§1.2 排列 §1.3 组合 §1.4二项式定理 §1.5组合恒等式
第二章 鸽笼原理（4学时）
[教学目的与要求]
本部分集中介绍鸽笼原理和定理，所谓的鸽巢原理也叫抽屉原理，是Ramsey定理的特例。它的简单形式是：把n?1个物体放入n个盒子里，则至少有一个盒子里含有两个或两个以上的物体。Ramsey定理的简单形式：设p,q是正整数，p,q?2,则存在最小的正整数R(p,q),使得当n?R(p,q)时，用红蓝两色涂色Kn的边，则或者存在一个蓝色的完全p边形，或者存在一个红色的完全q边形 。通过本章内容的学习可以使学生掌握鸽笼原理和 定理以及它们在解决有关存在性的组
合问题中的一些应用。
§2.1 鸽笼原理的简单形式
§2.2 一般形式 §2.3 ramsey原理
第三章 容斥原理（8学时）
[教学目的与要求]
所谓容斥原理是指在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。本部分介绍了容斥原理和容斥原理的若干应用。容斥原理是解决组合计数问题的一个重要工具，它研究的是有限个集合的并集形成的集合的计数的方法。本章内容包括容斥原理一般公式、有重组合计数问题、错位排列问题、带禁止位、相对禁止位排列等复杂问题的计数。了解容斥原理的符号形式和一般形式，能熟练地把一些问题的计数转化为应用容斥原理来计数。
§3.1 容斥原理 §3.2 集合的R组合 §3.3错排问题
§3.4相对位置上有限制的错排问题
第四章 母函数（10学时）