组合数学PDF电子书下载

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

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

1.1.1 组合数学简介 1

1.1.2 基本解题方法 1

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

1.2.1 常用符号 3

1.2.2 基本计数法则 4

习题1 8

2.1.1 二项式定理 9

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

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

2.1.2 杨辉三角形 10

2.2 多项式定理 15

2.2.1 多项式定理简介 15

2.2.2 多项式系数的性质 18

2.2.3 多项式系数的计数意义 20

习题2 21

第3章 排列与组合 24

3.1 初等排列与组合 24

3.1.1 排列 24

3.1.2 组合 32

3.2 排列与组合恒等式 36

3.2.1 基本恒等式 36

3.2.2 组合恒等式 36

3.2.3 排列恒等式 37

3.2.4 可重组合恒等式 38

3.3 网络路径问题 39

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

3.4.1 进位制 42

3.4.3 正整数的阶乘表示法 43

3.4.2 最优进制 43

3.5 排列与组合的生成 44

3.5.1 排列的生成算法 44

3.5.2 组合的生成算法 49

3.6 Wallis公式 49

3.7 Stirling公式 50

习题3 52

第4章 母函数与递推关系 54

4.1 母函数 54

4.1.1 母函数的定义 54

4.1.2 母函数的性质 55

4.2.1 Hanoi塔问题 57

4.2 递推关系 57

4.2.2 Fibonacci级数 58

4.2.3 递推关系的定义 61

4.2.4 有理分式的分项表示 62

4.2.5 递推关系的解 63

4.3 普母函数与递推关系 66

4.3.1 示例 66

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

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

4.4.1 普母函数与组合 71

4.4 母函数与排列组合 71

4.4.2 指母函数与排列 73

4.5 指母函数与错排 74

4.6 普母函数与分拆 75

4.6.1 分拆的定义 75

4.6.2 有序分拆 76

4.6.3 Ferrers图 77

4.6.4 无序分拆 79

4.6.5 关于p(n) 82

4.7.1 三角剖分问题 86

4.7.2 乘法结合方式问题 86

4.7 普母函数与Catalan数 86

4.7.3 Catalan数的通项公式 87

4.7.4 Catalan数的组合意义 88

4.7.5 Catalan数的性质 89

4.8 母函数与Stirling数 90

4.8.1 Stirling数的定义 90

4.8.2 Stirling数的递推关系 91

4.8.3 Stirling数的母函数 94

4.8.4 Stirling数的通项公式 96

4.8.5 Stirling数的组合意义 96

4.9 球盒分配问题 99

4.8.6 Stirling数的性质 99

4.10 有限和式 103

4.10.1 递推关系求有限和式 103

4.10.2 母函数求有限和式 103

4.10.3 差分表求有限和式 104

习题4 109

第5章 容斥原理 111

5.1 容斥原理 111

5.1.1 容斥原理的简单形式 111

5.1.2 容斥原理的一般形式 113

5.1.3 对称筛公式 118

5.2 容斥原理与限位排列 119

5.3.1 棋盘多项式 121

5.3 棋盘多项式与限位排列 121

5.3.2 限位排列 122

5.4 M？bius函数与Euler函数 123

5.5 M？bius反演 125

5.6 多重集的圆排列 127

习题5 131

第6章 鸽笼原理 132

6.1 鸽笼原理 132

6.1.1 鸽笼原理的简单形式 132

6.1.3 鸽笼原理的推广 133

6.1.2 鸽笼原理的基本形式 133

6.2 Ramsey理论 140

6.2.1 Ramsey定理 140

6.2.2 Ramsey数 142

习题6 146

第7章 几何图形计数 147

7.1 简单图形计数 147

7.2 子图形计数 148

7.3 图形的切割 154

7.4 折线法 157

7.5 整点与整边三角形 159

习题7 161

8.1 群的基本概念 162

第8章 P'olya定理 162

8.2 置换与置换群 163

8.2.1 置换 163

8.2.2 置换群 164

8.3 轮换与置换的奇偶性 165

8.3.1 轮换 165

8.3.2 置换的奇偶性 166

8.4 Burnside引理 168

8.4.1 共轭类 168

8.4.3 不变置换类 169

8.4.2 置换群的轨道 169

8.4.4 Burnside引理 170

8.5 P'olya定理 173

8.6 母函数型的P'olya定理 174

习题8 178

第9章 组合设计 180

9.1 拉丁方 180

9.1.1 拉丁方的概念 180

9.1.2 正交拉丁方 181

9.2 域 182

9.2.1 域的概念 182

9.2.2 Galois域 183

9.2.3 正交拉丁方的构造 185

9.3 区组设计 186

9.3.1 区组设计 186

9.3.2 完全区组设计 187

9.3.3 均衡不完全区组设计 188

9.3.4 区组设计的构造 191

9.4 Hadamard矩阵 194

9.4.1 Hadamard矩阵 194

9.4.2 Hadamard矩阵的构成 195

9.5.1 编码及其分类 197

9.5 编码理论简介 197

9.5.2 线性码 198

习题9 204

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

10.1 排序 206

10.1.1 选择排序 206

10.1.2 气泡浮起排序 207

10.1.3 分段交换排序 208

10.1.4 树型排序 209

10.1.5 合并排序 211

10.1.6 FORD_JOHNSON排序 212

10.2.2 折半查找 213

10.2 查找 213

10.2.1 顺序查找 213

10.2.3 分块查找 214

10.3 寻求第k个元素 215

10.4 快速Fourier变换 216

10.5 组合算法的复杂性 218

10.5.1 示例 218

10.5.2 贪心算法的时间上界 219

10.5.3 “倒树”算法 220

10.5.4 组合算法的复杂性问题 221

习题10 222

习题1答案 223

附录A 习题答案与提示 223

习题2答案 225

习题3答案 232

习题4答案 232

习题5答案 239

习题6答案 241

习题7答案 243

习题8答案 244

习题9答案 245

参考文献 247