本书以组合数学中的存在问题和计数问题为主线展现理论之美,从满足一定条件的排列组合的存在性入手,介绍计数方法和计数工具,将组合数学运用到与生活密切相关的网络安全实例中,展现其应用之美。全书分为7章,介绍了排列组合概念与方法、特殊计数、母函数原理与应用、递推关系和容斥原理计数方法,以及鸽笼原理和Polya计数定理。本书将合理分类与一一对应的思想贯穿全书,通过常见组合方法的使用呈现组合思想,力求深入浅出、通俗易懂。本书适合40至60学时课程讲授,书中还设计了与应用结合的拓展阅读,配有数字化资源,扫描二维码可观看学习。
样章试读
目录
- 目录
序
前言
第0章 引言 1
0.1 什么是组合数学 1
0.2 组合问题举例 2
0.2.1 配置的存在性（存在性问题） 2
0.2.2 配置的计数（计数问题） 3
0.2.3 配置的构造或分类（构造性问题） 3
0.2.4 配置的优化（优化问题） 4
0.3 典型组合问题举例 5
0.3.1 棋盘的完全覆盖 5
0.3.2 K.nigsberg七桥问题 5
0.3.3 四色猜想 6
0.3.4 36军官问题 6
0.3.5 Kirkman女学生问题 7
0.3.6 一个奇怪的函数 7
0.3.7 Nim取子游戏 7
第1章 排列与组合 9
1.1 预备知识 9
1.1.1 集合 9
1.1.2 映射 11
1.1.3 重集 12
1.1.4 四个法则 13
1.2 排列与组合 14
1.2.1 集合的排列 14
1.2.2 集合的环状排列 15
1.2.3 重集合的排列 16
1.2.4 集合的组合 18
1.2.5 重集合的组合 21
1.2.6 一一对应技巧 23
1.3 排列与组合的生成 25
1.3.1 全排列的生成 25
1.3.2 组合与排列的生成 28
1.4 二项式系数与组合恒等式 29
1.4.1 二项式系数 29
1.4.2 Newton二项式定理 32
1.4.3 组合恒等式 34
1.5 分配问题 39
1.5.1 12种分配问题 39
1.5.2 杂类分配问题 41
1.6 反演公式 44
1.6.1 Mobius反演 44
1.6.2 二项式反演 47
1.7* 拓展阅读——手势密码计数 51
习题1 52
第2章 特殊计数 55
2.1 格路径基础 55
2.1.1 增路 55
2.1.2 折线与T路 57
2.2 Catalan数 61
2.2.1 Catalan数的定义 61
2.2.2 更多形式模型 63
2.3 正整数的分拆 65
2.3.1 有序分拆计数公式 65
2.3.2 无序分拆与Ferrers图 67
2.3.3 整数分拆与分配问题 71
2.4 集合分拆和第二类Stirling数 71
2.4.1 集合有序分拆 71
2.4.2 分拆的组合与解析定义 72
2.4.3 递归关系与计数公式 74
2.4.4 集合的分拆与分配问题 77
2.5 置换和第一类Stirling数 78
2.5.1 置换中的轮换 78
2.5.2 组合定义与解析定义 80
2.5.3 递归关系与计数公式 83
2.5.4 两类Stirling数的三角矩阵 85
2.6* 拓展阅读——格路径及其应用 87
习题2 89
第3章 母函数 92
3.1 母函数与形式幂级数 92
3.1.1 母函数的概念 92
3.1.2 形式幂级数 93
3.1.3 闭公式 95
3.2 母函数的性质 97
3.3 普通型母函数 102
3.4 指数型母函数 110
3.5 母函数应用举例 116
3.5.1 母函数与Stirling数 116
3.5.2 母函数与组合恒等式 120
3.6 分拆数的母函数 122
3.6.1 分拆数的母函数 122
3.6.2 分拆数的Euler公式 124
3.7* 拓展阅读——伯努利数 128
习题3 130
第4章 递推关系 133
4.1 基本概念与递推关系的建立 133
4.1.1 递推关系的基本概念 133
4.1.2 递推关系的建立 134
4.2 常系数线性齐次递推关系 139
4.3 常系数线性非齐次递推关系 149
4.4 母函数法解常系数线性递推关系 156
4.4.1 齐次线性递推关系的求解 156
4.4.2 非齐次线性递推关系的求解 161
4.5 其他类型递推关系的求解 163
4.5.1 迭代法求解递推关系 163
4.5.2 卷积型递推关系的求解 168
4.5.3 线性常系数递推关系组 174
4.5.4 错位排列 180
4.6 差分方程 182
4.6.1 差分 182
4.6.2 差分表 186
4.6.3 差分方程 189
4.7* 拓展阅读——递推与分治算法 196
习题4 197
第5章 容斥原理 200
5.1 容斥原理 200
5.2 容斥原理的推广形式 207
5.3 应用举例 213
5.4* 容斥原理在RSA公钥加密算法中的应用 217
习题5 219
第6章 鸽笼原理 221
6.1 鸽笼原理的简单形式 221
6.2 鸽笼原理的推广形式 224
6.3 Ramsey定理 226
6.4 应用举例 234
6.5* Ramsey定理在通信中的应用 241
习题6 243
第7章 Polya计数定理 245
7.1 Polya计数问题导入 245
7.2 置换群及其计数模式 247
7.2.1 群与置换群 247
7.2.2 循环与置换的性质 251
7.2.3 共轭类与循环指标多项式 255
7.3 Polya计数定理 257
7.3.1 置换群诱导的等价关系 257
7.3.2 Burnside定理 259
7.3.3 Polya定理 263
7.3.4 Polya定理的推广 265
7.4 应用举例 270
7.5* 拓展阅读——棋盘游戏 274
习题7 280
参考文献 282
京公网安备 11010102004214号