组合理论及其应用PDF电子书下载

第1章 排列、组合、二项式定理 1

1.1 加法原理（原则）与乘法原理（原则） 1

1.2 排列与组合 3

1.2.1 集合的排列 3

1.2.2 集合的组合 5

1.3 多重集合的排列与组合 9

1.3.1 多重集合的排列 9

1.3.2 多重集合的组合 12

1.4 二项式定理 15

1.4.1 二项式定理的证明 15

1.4.2 二项式系数的基本性质 16

1.4.3 组合恒等式 18

1.4.4 多项式定理 20

1.5 集合的分划与第2类Stirling数 21

1.6 正整数的分拆 23

1.6.1 有序分拆 24

1.6.2 无序分拆 25

1.6.3 分拆的Ferrers图 26

1.7 分配问题 28

1.8 习题 31

2.1.1 引论 34

2.1 容斥原理 34

第2章 容斥原理与鸽巢原理 34

2.1.2 容斥原理的3个形式 35

2.1.3 应用举例 37

2.2 容斥原理的应用 40

2.2.1 具有有限重复数的多重集合的r组合数 40

2.2.2 错排问题 40

2.2.3 有禁止模式的排列问题 42

2.2.4 n对夫妻问题（ménage） 44

2.3 M？bim反演 45

2.4.2 鸽巢原理的形式 46

2.4.1 引论 46

2.4 鸽巢原理 46

2.5 Ramsey问题与Ramsey数 48

2.6 习题 50

第3章 递推关系 53

3.1 递推关系的建立 53

3.2 常系数线性齐次递推关系的求解 54

3.3 常系数线性非齐次递推关系的求解 57

3.4 用迭代法求解递推关系 59

3.5 Fibonacci数和Catalan数 61

3.5.1 Fibonacci数 61

3.5.2 Catalan数 64

3.6 习题 66

第4章 生成函数 68

4.1 引论 68

4.2 形式幂级数 69

4.3 生成函数的性质 72

4.4 用生成函数求解递推关系 77

4.4.1 用生成函数求解常系数线性齐次递推关系 77

4.4.2 用生成函数求解常系数线性非齐次递推关系 80

4.5 生成函数在计数问题中的应用 82

4.5.1 组合数的生成函数 82

4.5.2 排列数的指数型生成函数 83

4.5.3 分拆数的生成函数 85

4.5.4 组合型分配问题的生成函数 86

4.5.5 排列型分配问题的生成函数 87

4.6 有限制位置的排列及棋子多项式 88

4.7 习题 89

第5章 Pólya计数理论 92

5.1 引论 92

5.2 置换群的基本知识 92

5.2.1 群和子群 92

5.2.2 置换群 93

5.3 计数问题的数学模型 95

5.4 Burnside引理 96

5.4.1 共轭类 96

5.4.2 k不动置换类 98

5.4.3 等价类 98

5.4.4 Burnside引理的应用 99

5.5 Pólya计数定理 101

5.6 习题 106

第6章 二分图 107

6.1 相异代表系 107

6.2 二分图的匹配问题 109

6.3 二分图的一个算法 111

6.4 习题 115

第7章 组合矩阵 118

7.1 （0，1）矩阵 118

7.1.1 关联矩阵 118

7.1.2 积和式 121

7.1.3 （0，1）-矩阵类U（R，S） 125

7.2 Hadamard矩阵 129

7.3 习题 139

第8章 组合设计 140

8.1 拉丁方和正交拉丁方 140

8.2.1 正交拉丁方 141

8.2 正交拉丁方及其性质 141

8.2.2 用有限域构造正交拉丁方完备组 142

8.2.3 正交拉丁方应用举例 145

8.3 平衡不完全区组设计 147

8.3.1 基本概念 147

8.3.2 关联矩阵及其性质 148

8.3.3 三连系 152

8.4 几何设计 154

8.4.1 有限射影平面 155

8.4.2 平面设计 158

8.4.3 仿射平面 160

8.5 习题 166

第9章 基于有向图的网络基本理论 168

9.1 有向图的基本概念 168

9.2 网络 175

9.3 习题 180

第10章 整数规划 183

10.1 引论 183

10.2 线性整数规划基本解法 183

10.2.1 基本解法概述 183

10.2.2 分支定界法 185

10.2.3 割平面法 187

10.2.4 0-1规划的隐枚举法 192

10.3 线性混合整数规划解法 193

10.3.1 拉格朗日松弛法 195

10.3.2 交叉分解算法 197

10.4 背包问题的解法 199

10.4.1 动态规划解法 199

10.4.2 最短路径方法 200

10.4.3 近似算法 201

10.5 指派问题解法—匈牙利法 202

10.6 集合覆盖问题解法 204

10.7.2 拟布尔规划 208

10.7.1 字典序枚举法 208

10.7 非线性整数规划 208

10.7.3 蒙特卡罗法（随机取样法） 209

10.7.4 罚函数-凑整算法 209

10.7.5 相对差商法 210

10.8 习题 211

第11章 组合理论在相关免疫函数中的应用 213

11.1 相关免疫函数 213

11.1.1 相关免疫函数的定义 213

11.1.2 相关免疫函数的研究方法 214

11.2.2 线性结构函数和相关免疫函数 215

11.2.1 概述 215

11.2 线性结构一阶相关免疫函数的构造与计数 215

11.2.3 一阶线性结构相关免疫函数的计数下界 217

11.3 非退化的相关免疫函数的构造与计数 220

11.3.1 几个引理 220

11.3.2 构造方法与计数公式 221

11.4 1阶相关免疫函数的计数下界 223

11.5 高阶相关免疫函数的构造与计数 225

11.5.1 正交矩阵的几个结构定理 225

11.5.2 2阶相关免疫函数的构造与计数 226

11.5.3 m阶相关免疫函数的构造与计数 231

11.6 平衡m阶相关免疫函数 236

11.7 非退化高阶相关免疫函数的存在性 237

11.8 正交矩阵的递归生成算法 239

11.9 布尔函数的相关免疫性与其他密码学性质 240

11.9.1 相关免疫阶与代数次数和非线性度 240

11.9.2 一类高非线性度平衡相关免疫函数的构造 241

11.9.3 相关免疫性与扩散性 242

11.10 满足k次扩散准则的m阶相关免疫函数的构造 243

11.11 习题 245

12.1 λ—演算 246

12.1.1 λK—演算系统 246

第12章 组合逻辑 246

12.1.2 λη—演算系统及λI—演算系统 251

12.1.3 化归 252

12.2 演算的表示能力 256

12.2.1 λ—项上的运算 256

12.2.2 λ—可定义的自然数函数 259

12.2.3 一阶逻辑归约为λ—演算 262

12.3 组合逻辑 263

12.3.1 组合逻辑形式系统 264

12.3.2　λK与CL之间的关系 266

12.4 习题 270

第13章 组合理论的应用——组合搜索技术 271

13.1 分治法 272

13.1.1 SIMD模型的分治算法 272

13.1.2 分治法在MIMD模型上的实现途径 273

13.1.3 分治算法的复杂性 274

13.2 分枝界限法 275

13.2.1 8—谜宫问题 275

13.2.2 分枝界限方法 278

13.3 习题 280

名词索引 281

参考文献 283