组合数学（第3版） (2008 年度畅销榜NO.840 )

本书是《组合数学》（第二版）的修订版。全书共有6章，分别是：排列与组合，母函数与递推关系，容斥原理与鸽巢原理，贝恩塞特引理与波利亚定理，区组设计与编码，组合算法与复杂性分析。本书内容取舍得当，理论联系实际。\r\n\r\n 本书是计算机系本科生和研究生的教学用书，也可作为数学专业师生的教学参考书。\r\n
\r\n

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

第3版与第2版不同之点在于将原来第6章的线性规划, 换成现在与算法复杂性分析有关的内容, 还增加了一些应用实例, 删去线性规划是为了给新增加内客让出空间, 新增加的部分无疑更贴近计算机科学.

第2章和第6章是由卢华明执笔的.

电子计算机的出现是20世纪的大事, 它改变了我们这个世界的面貌. 可以毫不夸张地说, 它的影响遍及所有的角落, 几乎无处不感觉到它的存在. 数学更不例外. 严格地说, 电子计算机本身就是近代数学的辉煌成就. 将计算机与数学割裂开来, 既不合理也不可能. 组合学也就是在计算机科学蓬勃发展的刺激下崛起

的, 从而成为近若干年来最活跃的数学分支. 它研究的问题有的可追溯到欧拉和哈密尔顿等18世纪的数学家, 但它成为一个新的分支还是近若干年的事. 它从与计算机科学相结合中获得了广阔的发展空间, 从而也为计算机科学奠定了理论基础.

什么是计算机科学呢？有的学者将它定义为研究算法的一门学科. 研究算法无疑是计算机科学的重要领域, 也是本丛书的核心内容, 贯穿始终. 组合学家在20世纪70年代初建立的算法复杂性“NP理论”, 至今仍然令无数计算机科学工作者与数学工作者为之折腰.

计算机科学里的组合学内容十分广泛. 本丛书涉及组合分析. 图论. 组合算法. 近代密码学. 编码理论及算法复杂性等7部分.

组合分析是算法的理论基础. 组合分析之于组合算法犹如数学分析于与计算数学, 众所周知, 前者是后者的理论根基.

图论原来是组合数学这个“家族”的主要成员, 只因它已成长壮大, 故自立门户独立出去.

算法复杂性的NP理论是近30年的一大成就. 研究表明, 对于一类叫做NPC类的困难问题, 至今都不存在有效算法, 但它们难度相当, 只要其中任何一个找到多项式解法, 则全体都获得解决, 或证明它们根本不存在有效办法. 不论是前者还是后者都还看不见露到海平面上的桅杆塔, 它吸引了众多的有志之士. 密码学是其中十分引人人胜的分支. 如若设计好的密码, 对它的破译等价于某一NPC类困难问题, 无疑这样的密码将是牢不可破的.

在计算机网络深人普及的信息时代, 信息本身就是时间, 就是财富. 信息传输通过的是脆弱的公共信道, 信息储存于“不设防”的计算机系统中, 如何保护信息的安全使之不被窃取乃至于不被篡改或破坏, 已成为当今普遍关注的重大问题. 密码是有效而且可行的办法. 在计算机网络的刺激下, 近代密码学便在算法复杂性理论的基础上建立起来了. 密码作为一种技术, 自从人类有了战争, 不久便有了它. 但作为一门学科则是近20多年的事. 甚至于它已成为其他学科的基础. 密码也从此走出“军营”, 进人百姓家.

实际中的“优化”问题是大量的, 半个多世纪以来它曾经几度辉煌. 近来在计算机科学的影响下, 又出现了若干闪光点, 十分耀眼, 引人注目.

实际上密码也是一种编码. 如果说密码学研究的编码是保证通信的保密与安全, 则编码理论研究的是通信中如何纠错与检错. 计算机纠错码是既实用. 理论上又饶有趣味的分支.

本丛书是作者在清华大学计算机科学与技术系长期工作的总结. 它不是一部长篇记述, 而是互相关联又彼此相对独立, 因此难免有少量交叉. 它们涉及的面如此之广, 圃于作者的水平, 缺点和错误在所难免, 敬请读者不吝指正. 谢谢.

无封面