本书介绍组合计数及解决计数问题的数学工具，如母函数、容斥原理、鸽笼原理、P'olya定理等，还介绍了组合设计、计算机编码理论、组合算法及其复杂性。书中有大量的示例、习题，书后附有习题解答与提示，便于讲授、自学。既可作为计算机、数学及相关专业本、研教材，又可作为计算机、数学爱好者的自学用书。

本书介绍组合计数及解决计数问题的数学工具，如母函数、容斥原理、鸽笼原理、P'olya定理等，还介绍了组合设计、计算机编码理论、组合算法及其复杂性。该书基础理论部分讲述比较详细，且突出了算法。书中有大量的示例、习题，书后附有习题解答与提示，便于讲授、自学。

本书既可作为计算机、数学及相关专业本、研教材，又可作为计算机、数学爱好者的自学用书。

第1章 基本解题方法与计数法则

1.1 组合数学简介与基本解题方法

  1.1.1 组合数学简介

  1.1.2 基本解题方法

1.2 常用符号与基本计数法则

  1.2.1 常用符号

  1.2.2 基本计数法则

习题1

第2章 二项式与多项式定理

2.1 二项式定理与杨辉三角形

  2.1.1 二项式定理

  2.1.2 杨辉三角形

2.2 多项式定理

  2.2.1 多项式定理简介

  2.2.2 多项式系数的性质

  2.2.3 多项式系数的计数意义

习题2

第3章 排列与组合

3.1 初等排列与组合

  3.1.1 排列

  3.1.2 组合

3.2 排列与组合恒等式

  3.2.1 基本恒等式

  3.2.2 组合恒等式

  3.2.3 排列恒等式

  3.2.4 可重组合恒等式

3.3 网络路径问题

3.4 进位制与正整数的阶乘表示法

  3.4.1 进位制

  3.4.2 最优进制

  3.4.3 正整数的阶乘表示法

3.5 排列与组合的生成

  3.5.1 排列的生成算法

  3.5.2 组合的生成算法

3.6 Wallis公式

3.7 Stirling公式

习题3

第4章 母函数与递推关系

4.1 母函数

  4.1.1 母函数的定义

  4.1.2 母函数的性质

4.2 递推关系

  4.2.1 Hanoi塔问题

  4.2.2 Fibonacci级数

  4.2.3 递推关系的定义

  4.2.4 有理分式的分项表示

  4.2.5 递推关系的解

4.3 普母函数与递推关系

  4.3.1 示例

  4.3.2 线性常系数齐次递推关系的母函数解法

  4.3.3 线性常系数非齐次递推关系的母函数解法

4.4 母函数与排列组合

  4.4.1 普母函数与组合

  4.4.2 指母函数与排列

4.5 指母函数与错排

4.6 普母函数与分拆

  4.6.1 分拆的定义

  4.6.2 有序分拆

  4.6.3 Ferrers图

  4.6.4 无序分拆

  4.6.5 关于p(n)

4.7 普母函数与Catalan数

  4.7.1 三角剖分问题

  4.7.2 乘法结合方式问题

  4.7.3 Catalan数的通项公式

  4.7.4 Catalan数的组合意义

  4.7.5 Catalan数的性质

4.8 母函数与Stirling数

  4.8.1 Stirling数的定义

  4.8.2 Stirling数的递推关系

  4.8.3 Stirling数的母函数

  4.8.4 Stirling数的通项公式

  4.8.5 Stirling数的组合意义

  4.8.6 Stirling数的性质

4.9 球盒分配问题

4.10 有限和式

  4.10.1 递推关系求有限和式

  4.10.2 母函数求有限和式

  4.10.3 差分表求有限和式

习题4

第5章 容斥原理

5.1 容斥原理

  5.1.1 容斥原理的简单形式

  5.1.2 容斥原理的一般形式

  5.1.3 对称筛公式

5.2 容斥原理与限位排列

5.3 棋盘多项式与限位排列

  5.3.1 棋盘多项式

  5.3.2 限位排列

5.4 Mbius函数与Euler函数

5.5 Mbius反演

5.6 多重集的圆排列

习题5

第6章 鸽笼原理

6.1 鸽笼原理

  6.1.1 鸽笼原理的简单形式

  6.1.2 鸽笼原理的基本形式

  6.1.3 鸽笼原理的推广

6.2 Ramsey理论

  6.2.1 Ramsey定理

  6.2.2 Ramsey数

习题6

第7章 几何图形计数

7.1 简单图形计数

7.2 子图形计数

7.3 图形的切割

7.4 折线法

7.5 整点与整边三角形

习题7

第8章 P′olya定理

8.1 群的基本概念

8.2 置换与置换群

  8.2.1 置换

  8.2.2 置换群

8.3 轮换与置换的奇偶性

  8.3.1 轮换

  8.3.2 置换的奇偶性

8.4 Burnside引理

  8.4.1 共轭类

  8.4.2 置换群的轨道

  8.4.3 不变置换类

  8.4.4 Burnside引理

8.5 P′olya定理

8.6 母函数型的P′olya定理

习题8

第9章 组合设计

9.1 拉丁方

  9.1.1 拉丁方的概念

  9.1.2 正交拉丁方

9.2 域

  9.2.1 域的概念

  9.2.2 Galois域

  9.2.3 正交拉丁方的构造

9.3 区组设计

  9.3.1 区组设计

  9.3.2 完全区组设计

  9.3.3 均衡不完全区组设计

  9.3.4 区组设计的构造

9.4 Hadamard矩阵

  9.4.1 Hadamard矩阵

  9.4.2 Hadamard矩阵的构成

9.5 编码理论简介

  9.5.1 编码及其分类

  9.5.2 线性码

习题9

第10章 组合算法及其复杂性

10.1 排序

  10.11 选择排序

  10.1.2 气泡浮起排序

  10.1.3 分段交换排序

  10.1.4 树型排序

  10.1.5 合并排序

  10.1.6 FORD_JOHNSON排序

10.2 查找

  10.2.1 顺序查找

  10.2.2 折半查找

  10.2.3 分块查找

10.3 寻求第k个元素

10.4 快速Fourier变换

10.5 组合算法的复杂性

  10.5.1 示例

  10.5.2 贪心算法的时间上界

  10.5.3 “倒树”算法

  10.5.4 组合算法的复杂性问题

习题10

附录A 习题答案与提示

习题1答案

习题2答案

习题3答案

习题4答案

习题5答案

习题6答案

习题7答案

习题8答案

习题9答案

参考文献