组合数学及其应用

《组合数学及其应用》以组合数学中的存在问题和计数问题为主线展现理论之美,从满足一定条件的排列组合的存在性入手,介绍计数方法和计数工具,将组合数学运用到与生活密切相关的网络安全实例中,展现其应用之美。《组合数学及其应用》分为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
……