组合理论及其应用

.第2章 容斥原理与鸽巢原理 34
2.1 容斥原理 34
2.1.1 引论 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 鸽巢原理 46
2.4.1 引论 46
2.4.2 鸽巢原理的形式 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 不动置换类 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 正交拉丁方及其性质 141
8.2.1 正交拉丁方 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 非线性整数规划 208
10.7.1 字典序枚举法 208
10.7.2 拟布尔规划 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 线性结构一阶相关免疫函数的构造与计数 215
11.2.1 概述 215
11.2.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章 组合逻辑 246
12.1 (－演算 246
12.1.1 (k －演算系统 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