组合数学

引言                  
 第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  Fibonacci（费卜拉契）数列                  
 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, v, r, k, t）-设计                  
 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问题