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

第1章排列与组合.1.1加法法则与乘法法则1.2一一对应1.3排列与组合1.3.1排列与组合的模型1.3.2排列与组合问题的举伊1.4圆周排列1.5排列的生成算法1.5.1序数法1.5.2字典序法1.5.3换位法1.6允许重复的组合与不相邻的组合1.6.1允许重复的组合1.6.2不相邻的组合1.6.3线性方程的整数解的个数问题1.6.4组合的生成1.7组合意义的解释1.8应用举例1.9Stirling公式1.9.1Wallis公式1.9.2Stirling公式的证明习题第2章递推关系与母函数2.1递推关系2.2母函数2.3Fibonacci序列2.3.1Fibonacci序列的递推关系2.3.2若干等式2.4优选法与Fibonacci序列的应用2.4.1优选法2.4.2优选法的步骤2.4.3Fibonacci的应用2.5母函数的性质2.6线性常系数齐次递推关系2.7关于线性常系数非齐次递推关系2.8整数的拆分2.9Ferrers图像2.10拆分数估计2.11指数型母函数2.11.1问题的提出2.11.2指数型母函数的定义2.12广义二项式定理2.13应用举例2.14非��性递推关系举例2.14.1Stirling数2.14.2Catalan数2.14.3举例2.15递推关系解法的补充习题第3章容斥原理与鸽巢原理3.1DeMorgan定理3.2容斥定理3.3容斥原理举例3.4棋盘多项式与有限制条件的排列3.5有禁区的排列3.6广义的容斥原理3.6.1容斥原理的推广3.6.2一般公式3.7广义容斥原理的应用3.8第二类Stirling数的展开式3.9欧拉函数φ(n)3.10n对夫妻问题3.11Mobius反演定理3.12鸽巢原理3.13鸽巢原理举例3.14鸽巢原理的推广3.14.1推广形式之一3.14.2应用举例3.14.3推广形式之二3.15Ramsey数3.15.1Ramsey问题3.15.2Ramsey数习题第4章Burnside引理与Polya定理4.1群的概念4.1.1定义4.1.2群的基本性质4.2置换群4.3循环.奇循环与偶循环4.4Burnside引理4.4.1若干概念4.4.2重要定理4.4.3举例说明..4.5Polya定理4.6举例4.7母函数形式的Polya定理4.8图的计数4.9Polya定理的若干推广习题第5章区组设计5.1问题的提出5.2拉丁方与正交的拉丁方5.2.1问题的引入5.2.2正交拉丁方及其性质5.3域的概念5.4Galois域GF(pm)5.5正交拉丁方的构造5.6正交拉丁方的应用举例5.7均衡不完全的区组设计5.7.1基本概念5.7.2(b,u,r,k,λ)-设计5.8区组设计的构成方法5.9Steiner三元素5.10Kirkman女生问题习题第6章线性规划6.1问题的提出6.2线性规划的问题6.3凸集6.4线性规划的几何意义6.5单纯形法的理论基础6.5.1松弛变量6.5.2解的充要条件6.6单纯形法与单纯形表格6.7改善的单纯形法6.8对偶概念6.9对偶单纯形法习题第7章编码简介7.1基本概念7.2对称二元信道7.3纠错码7.3.1*近邻法则7.3.2Hamming不等式7.4若干简单的编码7.4.1重复码7.4.2奇偶校验码7.5线性码7.5.1生成矩阵与校验矩阵7.5.2关于生成矩阵和校验矩阵的定理7.5.3译码步骤7.6Hamming码7.7BCH码习题第8章组合算法简介8.1归并排序8.1.1算法8.1.2举例8.1.3复杂性分析8.2快速排序8.2.1算法的描述8.2.2复杂性分析8.3Ford-Johnson排序法8.4排序的复杂性下界8.5求第是个元素8.6排序网络8.6.10-1原理8.6.2Bn网络8.6.3复杂性分析8.6.4Batcher奇偶归并网络8.7快速傅里叶变换8.7.1问题的提出8.7.2预备定理8.7.3快速算法8.7.4复杂性分析8.8DFS算法8.9BFS算法8.10αβ剪技术8.11状态与图8.12分支定界法8.12.1TSM问题8.12.2任务安排问题8.13*短树与Kruskal算法8.14Huffman树8.15多段判决8.15.1问题的提出8.15.2*佳原理8.15.3矩阵链积问题8.15.4图的两点间*短路径习题...

本书是《组合数学》第3版的修订版,全书共分8章,分别是:排列与组合、递推关系与母函数、容斥原理与鸽巢原理、Burnside引理与Polya定理、区组设计、线性规划、编码简介、组合算法简介。丰富的实例及理论和实际相结合是本书一大特点,有利于对问题的深入理解。.
本书是计算机系本科生和研究生的教学用书,也可作为数学专业师生的教学参考书。...