组合数学

绪论 第一篇计数篇 第一章排列与组合 1.1加法法则和乘法法则 1.2排列 1.2.1简单排列 1.2.2有条件的排列 1.2.3圆排列 1.3组合 1.4多重集的排列 1.5多重集的组合 1.6二项式定理 1.6.1二项式系数 1.6.2组合恒等式 1.6.3牛顿二项式定理 1.7鸽巢原理 1.7.1鸽巢原理的简单形式 1.7.2Ramsey数 小结 习题 第2章容斥原理 2.1容斥原理 2.2容斥原理的应用 2.2.1对多重集的组合进行计数 2.2.2错排问题 2.2.3带有禁位的错排问题 小结 习题 第3章生成函数 3.1生成函数的性质 3.2指数生成函数 小结 习题 第4章递推方程 4.1递推关系 4.2利用特征方程求解递推方程 4.2.1线性递推方程的解 4.2.2非线性递推方程的解 4.3利用生成函数求解递推方程 4.4利用矩阵的性质求解递推方程 4.4.1常系数齐次递推方程矩阵解 4.4.2常系数非齐次递推方程矩阵解 4.4.3变系数齐次递推方程矩阵解 4.4.4变系数非齐次递推方程矩阵解 小结 习题 第5章特殊计数 5.1Fibonacci（斐波那契）数列 5.2Catlan数（卡特兰数或卡塔兰数） 5.3类Stirling数 5.4第二类Stirling数 5.5分拆数 5.6分装问题 5.6.1相同球和相同盒子的情况 5.6.2相同球和不同盒子的情况 5.6.3不同球和相同盒子的情况 5.6.4不同球和不同盒子的情况 小结 习题 第6章Polya计数 6.1关系 6.2群 6.3置换群 6.4Burnside（伯恩赛德）定理 6.5Polya定理 小结 习题 第二篇图论篇 第7章图 7.1图的基本概念 7.2图的同构 7.2.1两个无向不完全图同构映射的求法 7.2.2两个有向不完全图同构映射的求法 7.2.3不完全图的自同构 7.3无向图的连通性 7.4有向图的连通性 7.5欧拉图 7.6Hamilton图 7.6.1非赋权图Hamilton圈（路）的求法 7.6.2赋权图Hamilton圈（路）的求法 小结 习题 第8章树 8.1树的基本概念 8.2最短路径 8.3匹配 小结 习题 第9章图的着色 9.1图的色多项式 9.2图的色数 9.3平面图 9.4地图着色 小结 习题 第三篇区组设计篇 0章区组设计 10.1完全区组设计 10.1.1完全区组设计 10.1.2正交拉丁方 10.1.3用循环矩阵构建正交拉丁方 10.2不完全区组设计 10.3柯克曼女学生问题 10.4斯坦纳三元系 10.5Hadamard（阿达马）矩阵 10.5.1Hadamard矩阵 10.5.2Ryser猜想的完整证明 小结 习题 1章编码理论 11.1通信系统 11.2离散信源的度量 11.2.1离散信源的信息熵 11.2.2离散信源的联合熵和条件熵 11.3离散信道的度量 11.4无失真信源的编码 11.4.1等长码 11.4.2变长码 11.4.3霍夫曼（Huffman）编码 11.4.4算数编码 11.4.5LZ编码 11.4.6游程（RL）编码 11.5有噪信道编码 11.5.1有噪信道的编码定理 11.5.2纠错码 11.5.3线性分组纠错编码 11.5.4二元汉明码 11.5.5循环码 11.5.6BCH码 小结 习题 参考文献