组合数学PDF电子书下载

绪论 1

第一篇 计数篇 3

第1章 排列与组合 3

1.1 加法法则和乘法法则 3

1.2 排列 4

1.2.1 简单排列 4

1.2.2 有条件的排列 5

1.2.3 圆排列 6

1.3 组合 8

1.4 多重集的排列 9

1.5 多重集的组合 12

1.6 二项式定理 14

1.6.1 二项式系数 14

1.6.2 组合恒等式 15

1.6.3 牛顿二项式定理 15

1.7 鸽巢原理 16

1.7.1 鸽巢原理的简单形式 16

1.7.2 Ramsey数 18

小结 20

习题 21

第2章 容斥原理 23

2.1 容斥原理 23

2.2 容斥原理的应用 26

2.2.1 对多重集的组合进行计数 26

2.2.2 错排问题 29

2.2.3 带有禁位的错排问题 30

小结 33

习题 34

第3章 生成函数 36

3.1 生成函数的性质 36

3.2 指数生成函数 39

小结 40

习题 41

第4章 递推方程 42

4.1 递推关系 42

4.2 利用特征方程求解递推方程 44

4.2.1 线性递推方程的解 44

4.2.2 非线性递推方程的解 45

4.3 利用生成函数求解递推方程 46

4.4 利用矩阵的性质求解递推方程 48

4.4.1 常系数齐次递推方程矩阵解 48

4.4.2 常系数非齐次递推方程矩阵解 50

4.4.3 变系数齐次递推方程矩阵解 52

4.4.4 变系数非齐次递推方程矩阵解 53

小结 53

习题 54

第5章 特殊计数 56

5.1 Fibonacci（斐波那契）数列 56

5.2 Catlan数（卡特兰数或卡塔兰数） 57

5.3 第一类Stirling数 62

5.4 第二类Stirling数 67

5.5 分拆数 72

5.6 分装问题 79

5.6.1 相同球和相同盒子的情况 79

5.6.2 相同球和不同盒子的情况 79

5.6.3 不同球和相同盒子的情况 80

5.6.4 不同球和不同盒子的情况 81

小结 82

习题 84

第6章 Pólya计数 86

6.1 关系 86

6.2 群 86

6.3 置换群 88

6.4 Burnside（伯恩赛德）定理 88

6.5 Pólya定理 91

小结 92

习题 94

第二篇 图论篇 95

第7章 图 95

7.1 图的基本概念 95

7.2 图的同构 97

7.2.1 两个无向不完全图同构映射的求法 97

7.2.2 两个有向不完全图同构映射的求法 103

7.2.3 不完全图的自同构 105

7.3 无向图的连通性 107

7.4 有向图的连通性 108

7.5 欧拉图 110

7.6 Hamilton图 111

7.6.1 非赋权图Hamilton圈（路）的求法 111

7.6.2 赋权图Hamilton圈（路）的求法 115

小结 118

习题 120

第8章 树 122

8.1 树的基本概念 122

8.2 最短路径 125

8.3 匹配 127

小结 131

习题 132

第9章 图的着色 134

9.1 图的色多项式 134

9.2 图的色数 137

9.3 平面图 140

9.4 地图着色 142

小结 143

习题 145

第三篇 区组设计篇 147

第10章 区组设计 147

10.1 完全区组设计 147

10.1.1 完全区组设计 147

10.1.2 正交拉丁方 149

10.1.3 用循环矩阵构建正交拉丁方 150

10.2 不完全区组设计 152

10.3 柯克曼女学生问题 154

10.4 斯坦纳三元系 156

10.5 Hadamard（阿达马）矩阵 156

10.5.1 Hadamard矩阵 156

10.5.2 Ryser猜想的完整证明 158

小结 160

习题 161

第11章 编码理论 162

11.1 通信系统 162

11.2 离散信源的度量 165

11.2.1 离散信源的信息熵 166

11.2.2 离散信源的联合熵和条件熵 168

11.3 离散信道的度量 170

11.4 无失真信源的编码 174

11.4.1 等长码 176

11.4.2 变长码 179

11.4.3 霍夫曼（Huffman）编码 185

11.4.4 算数编码 187

11.4.5 LZ编码 190

11.4.6 游程（RL）编码 191

11.5 有噪信道编码 192

11.5.1 有噪信道的编码定理 192

11.5.2 纠错码 194

11.5.3 线性分组纠错编码 195

11.5.4 二元汉明码 199

11.5.5 循环码 199

11.5.6 BCH码 204

小结 206

习题 210

参考文献 215