组合数学基础PDF电子书下载

引言 1

1 什么是组合数学 1

2 组合问题举例 2

3 预备知识 5

第一章 排列与组合 12

1.1 排列与组合 12

1.1.1 排列 12

1.1.2 组合 15

1.2 排列与组合的生成 19

1.2.1 排列的生成 19

1.2.2 组合的生成 23

1.2.3 k-排列的生成 24

1.3 二项式系数与组合恒等式 24

1.3.1 二项式系数 24

1.3.2 组合恒等式 26

1.4 分配问题 30

1.4.1 12种分配问题 30

1.4.2 其它类型分配问题 32

习题一 34

第二章 特殊计数 38

2.1 格子点 38

2.1.1 增路 38

2.1.2 折线 40

2.2 Catalan数 43

2.3 正整数的分拆 47

2.3.1 有序分拆 47

2.3.2 分拆数 48

2.3.3 正整数的分拆与分配问题 53

2.4 集合的分拆和第二类Stiriling数 53

2.4.1 集合的分拆 53

2.4.2 第二类Stirling数的定义 54

2.4.3 第二类Stirling数的递归关系 55

2.4.4 第二类Stirling数的解析定义 56

2.4.5 第二类Stirling数的计数公式 57

2.4.6 集合的分拆与分配问题 57

2.5 置换和第一类Stiriling数 59

2.5.1 置换中的轮换 59

2.5.2 第一类Stirling数的定义 61

2.5.3 第一类Stirling数的递归关系 61

2.5.4 第一类Stirling数的解析定义 62

2.5.5 两类Stirling三角矩阵的性质 63

习题二 64

第三章 母函数 67

3.1 母函数的定义 67

3.2 母函数的性质 72

3.2.1 形式幂级数及其运算 73

3.2.2 母函数的性质 75

3.2.3 母函数的闭公式 79

3.3 组合数的母函数（普通型母函数） 81

3.4 排列个数的指数型母函数 84

3.5 分拆数的母函数 92

3.5.1 分拆数的母函数 93

3.5.2 分拆数的Euler公式 95

习题三 98

第四章 递归关系 100

4.1 基本概念和例子 100

4.2 几类递归关系的解法 106

4.2.1 一阶递归关系 106

4.2.2 r阶齐次常系数线性递归关系 108

4.2.3 r阶非齐次常系数线性递归关系 114

4.2.4 卷积型递归关系 118

4.2.5 线性常系数递归关系组 120

4.3 递归关系的应用举例 124

4.4 差分方程 131

4.4.1 差分运算 132

4.4.2 差分表 134

4.4.3 差分方程 137

习题四 142

第五章 容斥原理 146

5.1 引言 146

5.2 容斥原理的基本公式 147

5.2.1 模型与记号 148

5.2.2 基本公式 149

5.3 容斥原理的推广 154

5.3.1 Jordan定理 154

5.3.2 容斥原理的赋权形式 156

5.4 容斥原理的应用举例 157

5.4.1 Euler函数 157

5.4.2 带限制条件的可重复组合问题 158

5.4.3 耦合问题和错位排列 159

5.4.4 限位排列 161

5.4.5 Ménage问题 162

5.4.6 带限制条件的可重复排列问题 163

5.5 计数问题回顾 164

习题五 168

第六章 鸽笼原理与Ramsey定理 170

6.1 鸽笼原理 170

6.1.1 鸽笼原理的基本形式 170

6.1.2 鸽笼原理的一般形式 172

6.1.3 鸽笼原理的推广形式 175

6.2 Ramsey问题 176

6.2.1 完全图Kn的边着色 177

6.2.2 Ramsey定理 181

6.2.3 Ramsey数 185

6.3 染色问题与染色方法 187

习题六 194

第七章 Pólya计数定理 196

7.1 引论 196

7.2 置换群及其计数模式 197

7.2.1 回顾置换群的概念 197

7.2.2 计数问题的数学模式 199

7.3 Pólya计数定理 202

7.3.1 置换群的轮换指标 202

7.3.2 Pólya定理的特殊情形 203

7.3.3 Pólya定理 203

7.3.4 Pólya定理的推广 204

7.4 Pólya计数定理的应用举例 205

7.5 Pólya计数定理的证明 213

7.5.1 群在集合上的作用 213

7.5.2 Burnside引理 214

7.5.3 Pólya计数定理的证明 216

7.5.4 Pólyo计数定理的推广 217

习题七 219