组合数学(第四版)

第1章 排列与组合  
1. 1 基本计数法则  
1. 1. l 加法法则. 乘法法则及排列与组合  
1. 1. 2 应用举例  
1. 2 一一对应  
1. 3 排列  
1. 4 圆周排列  
1. 5 组合  
1. 6 排列的生成算法  
1. 6. 1 序数法  
1. 6. 2 字典序法  
1. 6. 3 换位法  
1. 7 组合的生成  
1. 8 允许重复的组合与不相邻的组合  
1. 8. 1 允许重复的组合  
1. 8. 2 不相邻的组合  
1. 9 组合的解释  
1. 10 应用举例  
1. 11 司特林(Stirling)公式  
1. 11. 1 瓦利斯(Wallis)公式  
1. 11. 2 司特林公式的证明  
习题  
第2章 母函数与递推关系  
2. 1 母函数的引入  
2. 2 母函数的性质  
2. 2. 1 苦于基本的母函数  
2. 2. 2 基本公式  
2. 3 整数的拆分  
2. 4 费勒斯(Ferrers)图像  
2. 5 关于拆分数p(n)的讨论  
2. 5. l 欧拉公式  
2. 5. 2 拆分数估计式  
2. 6 指数型母函数  
2. 6. 1 问题的提出  
2. 6. 2 指数型母函数的引入  
2. 7 递推关系举例  
2. 8 Fibona i(费卜拉契)数列  
2. 8. 1 问题的提出  
2. 8. 2 问题的解  
2. 8. 3 若干等式  
2. 8. 4 优选法  
2. 9 解线性常系数递推关系特征根法  
2. 9. l 二阶线性常系数齐次递推关系  
2. 9. 2 一阶. 二阶线性常系数非齐次递推关系  
2. 9. 3 叠加原理  
2. 10 任意阶齐次递推关系  
2. 11 一般线性常系数非齐次递推关系  
2. 12 应用举例  
2. 13 非线性递推关系举例  
2. 13. 1 司特林(Stirling)数  
2. 13. 2 卡特朗(Catalan)数  
2. 13. 3 举例  
2. 14 递推关系解法的补充  
习题  
第3章 容斥原理与鸽巢原理  
3. l 容斥原理  
3. 1. 1 引论  
3. 1. 2 容斥原理的两个基本公式  
3. 1. 3 例子  
3. 2 棋盘多项式和有限制条件的排列  
3. 2. 1 有限制的排列  
3. 2. 2 棋盘多项式  
3. 2. 3 有禁区的排列问题  
3. 3 广义的容斥原理  
3. 3. 1 问题的引入  
3. 3. 2 特殊情况  
3. 3. 3 一般公式  
3. 3. 4 广义容斥原理的证明  
3. 4 广义容斥原理的若干应用  
3. 5 第二类司特林数展开式  
3. 6 错排问题的推广  
3. 7 容斥原理在数论上的应用  
3. 7. l 埃拉托逊斯(Eratosthenes)筛法  
3. 7. 2 欧拉函数(n)  
3. 8 n对夫妻问题  
3. 9 反演公式  
3. 9. 1 反演定理  
3. 9. 2 若干应用  
3. 10 鸽巢原理  
3. 10. 1 问题的引入  
3. 10. 2 一般的鸽巢原理  
3. 11 鸽巢原理的推广  
3. 11. 1 推广形式之一  
3. 11. 2 例  
3. 11. 3 推广形式之二  
3. 12 拉蒙赛(Ramsey)数  
3. 12. 1 拉蒙赛问题  
3. 12. 2 拉蒙赛数  
习题  
第4章 贝恩塞特(surnside)引理与波利亚(Polya)定理  
4. 1 群的概念  
4. l. 1 定义  
4. 1. 2 群的基本性质  
4. 2 置换群  
4. 3 循环. 奇循环与偶循环  
4. 4 贝恩塞特(Burnside)引理  
4. 4. 1 若干概念  
4. 4. 2 重要定理  
4. 4. 3 例  
4. 5 波利亚(Polya)定理  
4. 6 举例  
4. 7 母函数形式的波利亚定理  
4. 8 图的计数  
4. 9 波利亚定理的若干推广  
习题  
第5章 区组设计与编码  
5. 1 问题的提出  
5. 2 拉丁方与正交的拉丁方  
5. 2. 1 问题的引入  
5. 2. 2 正交拉丁方及其性质  
5. 3 域的概念  
5. 4 Galois域GF(pn)  
5. 5 正交拉丁方的构造  
5. 6 正交拉丁方应用举例  
5. 7 均衡不完全的区组设计(BIBD)  
5. 7. l 基本概念  
5. 7. 2 (b,118v,118r,118k,118t)-设计  
5. 8 区组设计的构成方法  
5. 9 斯梯纳三元系  
5. 10 科克曼女生问题  
5. 11 有限射影空间  
5. 11. 1 二维的射影几何  
5. 11. 2 有限域上的射影空间  
5. 12 阿达玛(Hadamard)矩阵  
5. 13 编码理论的基本概念  
5. 14 对称二元信道  
5. 15 纠错码  
5. 15. 1 *近邻法则  
5. 15. 2 汉明不等式  
5. 16 苦于简单的编码  
5. 16. l 重复码  
5. 16. 2 奇偶校验码  
5. 17 线性码  
5. 17. 1 生成矩阵与校验矩阵  
5. 17. 2 关于生成矩阵和校验矩阵的定理  
5. 17. 3 译码步骤  
5. 18 汉明码  
5. 19 陪集译码法  
5. 20 BCH码  
5. 21 其他编码技术简介  
5. 21. 1 利用区组设计纠错码  
5. 21. 2 利用阿达玛矩阵进行编码  
习题  
第6章 组合算法与复杂性分析  
6. 1 归并排序算法  
6. 1. 1 归并排序  
6. 1. 2 举例  
6. 1. 3 复杂性分析  
6. 2 快速排序  
6. 2. 1 算法的描述  
6. 2. 2 复杂性分析  
6. 3 Ford-Johnson排序法  
6. 4 求第k个元素  
6. 5 排序网络  
6. 5. 1 0-1原理  
6. 5. 2 Bn网络  
6. 5. 3 复杂性估计  
6. 5. 4 Batcher奇偶归并网络  
6. 6 快速傅里叶变换(FFT)  
6. 6. 1 问题的提出  
6. 6. 2 预备定理  
6. 6. 3 快速算法  
6. 6. 4 复杂性分析  
6. 7 DFS算法  
6. 7. l 算法的引入  
6. 8 判决树  
6. 8. 1 银币问题  
6. 8. 2 举例  
6. 9 渡河问题  
6. 10 TSM问题与分支定界法  
6. 11 多段判决  
6. 11. 1 问题的提出  
6. 11. 2 *佳原理  
6. 11. 3 矩阵链积问题  
6. 12 NPC问题