组合数学
课程编码：B0912003Y 英文名称：Combinatorics 课时：38 学分：2.00 课程属性：专业课 主讲教师：孙晓明
| 章 | 节 | 要求 |
| 第1章排列组合 | 课程介绍 | 了解课程内容、课程要求、与计算机科学的联系等。 |
| 排列组合1 | 掌握基本的排列组合知识、技巧，二项式定理，杨辉三角形、朱世杰恒等式与范德蒙恒等式。 | |
| 排列组合2 | 掌握斯特林公式及其应用，可重排列、圆排列，组合数（二项式系数）与多项式的联系。 | |
| 极值组合论 | 理解反链与Sperner引理。 | |
| 第2章递推关系 | 基本递推关系 | 掌握汉诺塔问题、平面划分问题、多米诺覆盖问题。 |
| 生成函数方法 | 掌握基本的生成函数求解，使用生成函数求解Catalan数问题，理解使用对称法求解Catalan数。 | |
| Catalan数与一维随机游走 | 掌握一维随机游走的模型与概念，借助Catalan数使用生成函数求解一维随机游走。了解二维、三维随机游走的常返性结论与推导。 | |
| 第3章容斥公式 | 容斥公式 | 掌握容斥公式证明过程及其使用，包括禁位全排列（装错信封问题）等。 |
| 第一类斯特林数 | 掌握第一类斯特林数的两种定义（组合定义、多项式定义）、递推公式、相关恒等式。 | |
| 第二类斯特林数 | 掌握第二类斯特林数的两种定义（组合定义、多项式定义）、递推公式、相关恒等式。 理解两类斯特林数之间的联系（恒等式）以及与组合数之间的联系。 | |
| 分拆数 | 掌握分拆数的定义、递推关系，理解分拆数相关的恒等式、不等式，了解分拆数上下界的估计。 | |
| 第6章素数分布 | 素数定理 | 理解如何从组合数出发证明伯兰特-切比雪夫定理，了解素数定理及其证明。 |
| 二次互反律 | 掌握二次剩余的概念、高斯取整符号的概念，理解高斯二次互反律，掌握使用二次互反律计算二次剩余，了解二次互反律的证明（使用格点计数）。 | |
| 第7章鸽笼原理 | 鸽笼原理 | 掌握基本的鸽笼原理及各种变形，能灵活运用鸽笼原理证明问题；了解使用鸽笼原理研究ax2+by2形式素数的存在性，了解Erdos-Ginzburg-Ziv问题及代数化方法。 |
| 第8章Ramsey理论 | Ramsey理论 | 掌握Ramsey数的定义和递推关系，R(3,3)=6的证明，理解高维的Ramsey理论，了解超图的Ramsey理论。 |
| 概率方法 | 掌握Ramsey数的上界证明，理解概率方法证明Ramsey数下界。 | |
| 范德瓦尔登定理 | 理解Shur定理及其证明，最基本形式的范德瓦尔登定理及其证明，了解Green-Tao定理。 | |
| Ramsey理论在理论计算机中的应用 | 了解Ramsey理论在数据结构、分布式一致性、矩阵乘法等问题中的应用。 |
第1章 排列组合
内容：排列组合基本知识；二项式定理；杨辉三角和朱世杰恒等式；斯特林公式及其应用；可重排列；圆排列；极值组合论。
要求：(1)掌握排列组合的基本知识，理解杨辉三角，掌握朱世杰恒等式。(2)掌握二项式定理及其应用，理解其与多项式定理的联系。(3)掌握斯特林公式及其应用。(4)掌握可重排列、圆排列的求解方法。(5)掌握极值组合论的基本知识，理解反链和Sperner引理的证明思路。
重点：排列数；组合数；二项式定理；斯特林公式。
难点：朱世杰恒等式；Sperner引理。
第2章 递推关系
内容：递推关系的定义以及递推通项求解；经典递推关系例子：汉诺塔问题、平面划分问题、多米诺骨牌覆盖问题等；生成函数方法；卡特兰数的定义、求解以及应用。
要求：(1)理解递推关系的概念，掌握求解递推通项的基本方法。(2)掌握求解递推关系在汉诺塔问题、平面划分、空间划分、字符串计数、多米诺骨牌覆盖等问题中的应用。(3)掌握利用生成函数的方法，求解递推关系通项。(4)理解卡特兰数的定义，掌握卡特兰数的求解方法，学会利用卡特兰数求解应用问题。
重点：递推关系；生成函数；卡特兰数。
难点：卡特兰数求解过程及应用。
第3章 容斥公式
内容：容斥公式及其证明过程、禁位全排列（装错信封问题）、莫比乌斯反演公式
要求：(1)掌握容斥公式，熟悉容斥公式的证明过程。(2)掌握容斥公式在素数个数、不定方程解的个数、欧拉公式证明、禁位全排列等例子中的应用。(3)理解容斥公式与莫比乌斯反演公式之间的关系。
重点：容斥公式及其证明过程；容斥公式的应用；禁位全排列。
难点：利用容斥公式进行计数。
第4章 斯特林数
内容：第一类斯特林数（定义、递推公式和相关恒等式），第二类斯特林数（定义、递推公式和相关恒等式）
要求：(1)掌握第一类斯特林数的两种定义（组合定义、多项式定义）、递推公式、相关恒等式。(2)掌握第二类斯特林数的两种定义（组合定义、多项式定义）、递推公式、相关恒等式。(3)理解两类斯特林数之间的联系（恒等式）以及与组合数之间的联系。
重点：第一类斯特林数的两种定义、递推公式；第二类斯特林数的两种定义、递推公式。
难点：两类斯特林数的相关恒等式。
第5章 分拆数
内容：分拆数的定义、递推关系、相关的恒等式和不等式、上下界的估计
要求：(1)掌握分拆数的定义、递推关系。(2)理解分拆数相关的恒等式、不等式。(3)了解分拆数上下界的估计。
重点：分拆数的定义和递推关系。
第6章 素数分布
内容：波兰特切比雪夫定理（内容，组合证明）素数定理（内容，几个经典的证明） 二次剩余(概念) 高斯取整符号（概念）勒让德符号（概念 计算） 二次互反律（概念，计算二次剩余，格点计数法证明）
要求：(1)理解波兰特切比雪夫定理，素数定理的概念了解这两个定理的组合证明。（2）掌握勒让德符号和高斯取整符号的含义，掌握计算勒让德符号和高斯取整符号的方法。（3）理解高斯二次互反律，掌握使用二次互反律计算二次剩余，理解使用格点计数法证明二次剩余。
重点：勒让德符号的含义，利用欧拉判别准则或二次互反律辅助计算勒让德符号。
难点：二次互反律的含义，二次互反律的格点计数法证明。
第7章 鸽笼原理
内容：鸽笼原理（含义，证明，变形），特殊形式的素数存在性问题，Erdos-Ginzburg-Ziv问题
要求：(1)掌握基本的鸽笼原理内涵及各类变形，能够灵活运用鸽笼原理证明不同背景的问题。(2)理解使用鸽笼原理解决ax^2+by^2形式的素数存在性问题。(3)了解Erdos-Ginzburg-Ziv问题及代数化方法。
重点：在不同的问题中灵活运用鸽笼原理，将问题合理变形转变为能够使用鸽笼原理的形式。Erdos-Ginzburg-Ziv问题的求解。
难点：将原问题进行合理的转化，利用鸽笼原理求解。
第8章 Ramsey 理论
内容：Ramsey数（定义，递推，特殊值，计算机中的应用），概率方法（Ramsey数上下界的证明） 舒尔定理（定义，证明） 范德瓦尔登定理（定义，证明） Green-Tao定理（定义）
要求：(1)掌握Ramsey数的定义和递推关系，R(3,3)=6的证明，理解高维的Ramsey理论，了解超图的Ramsey理论。(2)掌握Ramsey数的上界证明，理解概率方法证明Ramsey数下界。(3)理解Shur定理及其证明，最基本形式的范德瓦尔登定理及其证明，了解Green-Tao定理。
(4)了解Ramsey理论在数据结构、分布式一致性、矩阵乘法等问题中的应用。
重点：Ramsey数的含义，以及小规模情况下的计算。Ramsey数上下界的证明。范德瓦尔登定理、舒尔定理的运用。
难点：利用Ramsey数，范德瓦尔登定理以及舒尔定理解决具体问题。
规定出本课程的各种教学环节（习题课、实验、上机、讨论等）恰当学时。
| 章节/学时分配 | 讲课 | 习题课 | 实验课 | 上机课 | 讨论课 | 其它 |
| 1 | 5 | |||||
| 2 | 4 | |||||
| 3 | 2 | |||||
| 4 | 4 | |||||
| 5 | 4 | |||||
| 6 | 6 |
|
|
|
|
|
| 7 | 6 |
|
|
|
|
|
| 8 | 5 |
|
|
|
|
|