扫一扫
关注中图网
官方微博
本类五星书更多>
-
>
宇宙、量子和人类心灵
-
>
(精)BBC地球故事系列-星际旅行
-
>
从一到无穷大
-
>
图说相对论(32开平装)
-
>
一本有趣又有料的化学书
-
>
刘薰宇的数学三书:原来数学可以这样学全3册
-
>
光学零件制造工艺学
组合数学及其应用 版权信息
- ISBN：9787030750815
- 条形码：9787030750815 ; 978-7-03-075081-5
- 装帧：一般胶版纸
- 册数：暂无
- 重量：暂无
- 所属分类：>
组合数学及其应用 内容简介
全书安排七章内容。分别为排列与组合；母函数；递归关系；容斥原理；鸽笼原理与Ramsey定理；Pólya计数定理；区组设计。在基本框架基础上，补充网安特色案例，配套相应章节习题。可供大中专院校计算机、信息安全、密码工程等相关专业本科生研究生使用，也可供相关科技工作者参考。
组合数学及其应用 目录
目录
序
前言
第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
序
前言
第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
展开全部
组合数学及其应用 节选
第0章引言 组合数学，又称组合论、组合分析、组合学，在数学游戏和博弈中有它的历史渊源，在工程学、化学、生物学、统计学、运筹学、密码学、计算机科学等学科都有广泛的应用.同时兼顾纯粹数学和应用数学两个领域，是组合数学的特色之一.内容的离散性、问题的趣味性、解决问题方法的多样性，是组合数学的独有特色. 组合数学是一个古老而又年轻的数学分支.说它古老，是因为早在4000多年前我国的“河图洛书”的传说就与组合数学有关，历史上许多著名的数学难题与组合数学有关，诸如Konigsberg七桥问题、四色问题、Kirkman女学生问题、正交拉丁方问题等.这些问题吸引了一代又一代青年学子，把他们引进了组合数学研究的殿堂，使得组合数学这门学科不断完善和发展.由于这门学科在自然科学的众多学科里、管理科学的很多分支中及工程学的许多技术领域里，尤其在计算机科学的理论和应用上近几十年得到迅猛飞速的发展，所以在信息时代的今天人们越来越认识到组合数学的重要性.组合数学是一块充满珍花异草的圣地，足以使观赏者流连忘返，更能激发观赏者研究的欲望和热情. 0.1什么是组合数学 我们先举一个典型例子来了解组合数学探讨的到底是什么：把一张白纸划分成n个区域，称两个区域是相邻的如果它们有公共线段，现在把每一个区域都染上一种颜色，条件是相邻的两个区域都不能同色，对这n个区域染色是否用四种颜色就够了？组合数学的问题常常是如此，先规定一件要做的事情，如用四种颜色给区域染色，这件事多半都是很容易做到，而且有各种各样的做法，但我们同时加上了一些约束条件，如相邻区域不得同色，情形就大不一样了.现在有些做法符合条件有些不符合条件，我们问符合条件的做法有多少种，或者问有没有符合条件的做法，或者要找出一种好的做法. 组合数学是研究离散结构的存在、计数、构造和优化等问题的一门学科.组合数学所研究的问题是按照一定的模式将集合的元素进行配置安排），通常反复出现的是以下四种类型的问题： （Ⅰ）配置的存在性； （Ⅱ）配置的计数或近似估计； （Ⅲ）配置的构造或分类； （Ⅳ）配置的优化. 如上述例子中集合的元素是n个区域，配置是用四种颜色染n个区域，规定的模式是相邻的两个区域都不能同色.当配置并非显然存在或不存在时，首要的问题是证明或否定它的存在；当配置显然存在或已证明存在时，需要无重复、无遗漏地求出这种配置的个数，当配置个数的计数存在困难时可对其进行近似估计，随着计算机科学的迅猛发展，为了充分利用计算机资源，需要对配置的计数问题给出算法，因此组合数学成了算法的理论基础；如有可能还要给出配置的构造或按照某种性质对配置进行分类.按照一定的模式将集合的元素进行配置可看作是一种组合结构，组合结构又可看作一种数学模型，社会实践中的一些实际问题可抽象为数学模型，因此对数学模型的研究是十分有意义的.当组合结构确定后，能否进一步优化是组合优化的重要研究内容. 0.2组合问题举例 0.2.1配置的存在性（存在性问题） 如果研究对象在满足某些条件下才能进行下一步安排，当对象是否符合条件并非显然存在或者显然不存在时，首要解决的就是证明存在或者否定存在. 例如，分组密码算法扩散层设计时，经常用到矩阵作为基本单位.设A为n阶方阵，I为n阶单位阵，则满足的方阵A称为对合矩阵.由于对合矩阵的逆矩阵就是本身，所以为了加密和解密过程的一致性，对合矩阵自然被重点关注.那么对于二元域上的n阶方阵，是否一定存在对合矩阵呢？这个问题似乎容易回答，利用穷举方法或者利用特征值构造方法可以容易构造出二元域上n阶对合矩阵.但扩散层设计还有一个性质，就是要求不动点越少越好，也就是点经过矩阵乘积作用后的结果仍是该点，具有这种性质的点的数量越少越好，此时问题变成对于二元域上的n阶对合矩阵，其不动点个数能否达到*低？通过下面简单的证明，我们知道这种要求是完全不存在的. 性质0.1设A为二元域上的n阶对合矩阵，则其不动点个数不小于. 证 这个性质说明二元域上的n阶对合矩阵的不动点个数相当多，几乎占空间的一半，要求同时满足对合性质和不动点个数低，这种配置不存在.从这个例子可以看出，满足一定条件的配置并不总是存在的，这就给我们提出了新的问题：什么条件下配置才是存在的？这就是配置的存在性研究的根本问题，有些时候这些问题的回答并不显而易见. 0.2.2配置的计数（计数问题） 如果所要求的配置存在，则可能有多种不同的配置，这又经常给我们提出这样的问题：有多少可能的配置方案？如何对配置方案进行合理分类？ 例如，银行卡在操作的时候都需要输入6位数字的口令，这里口令个数一共是106个.我们在利用RAR加密一个压缩文档时，同样输入6位口令，这时要求必须有1个小写字母、一个大写字母、一个特殊字符，这时可能的口令又是多少个呢？ 这个时候可以输入的小写字母26个，大写字母26个，数字10个，特殊字符32个，若没有特殊限制此时6位口令共计（26×2+10+32）6=946.加上限制之后，计数变为10×26x26×（94）3. 对于一般的计数问题，多数情形需要研究两个配置是否属于同一个等价数学模型，也就是先研究清楚同类配置判定的数学方法，再给出配置方案分类的计算公式.虽然任何组合问题的计数都有方法可循，但有时需要做大量研究，此时其计数的难度也是巨大的，如果问题有明显的特解，则可以追寻特解的规律进行分类并计算出解的个数. 例如，手机的九宫格图案解锁总共能绘出多少种图案？这个问题相当于把先行后列标记为1，2，3，4，5，6，7，8，9这九个数字的9个点排成3阶矩阵，且合法的密码要求如下： 密码的长度至少为4，*长为9; 密码中不能有重复的数字出现，比如不能同时出现两个2; 密码相邻的数字必须在图形上是相连的，这样才符合手的滑动. 这个问题的计数就复杂得多，需要进行细致的分类研究，其*终结果是389112种，1.7节会详细讨论计算方法. 0.2.3配置的构造或分类（构造性问题） 幻方是古老且流行的数学游戏之一，一个n阶幻方是由数字，构成的矩阵，满足每行每列及两个对角线上的元素之和均为S，这个和数S称为幻和.因为，所以.与此相关的组合问题是确定可以构造n阶幻方的n的值以及寻找构造幻方的一般方法.不难验证不存在2阶幻方，而对于其他任意的n值，都可以构造出n阶幻方.容易给出3阶幻方. 有很多种特殊的幻方构造方法，这里介绍delaLoubere在17世纪发现的构造方法.当n为奇数时，有一种简单的方法来构造n阶幻方.首先把1放在*上面一行的中间位置，然后按下面规则把2，3， ，n这些数字沿一条由左下至右上的斜线相邻放置. （1）当一个数放在*上面一行的（1，k）位置，下一个数放在*下面一行的（n，k+1）位置 （2）当一个数放在*右边一列（kn，n）位置，下一个数放在*左边一列的（1，k-1）位置. （3）当遇到一个位置已经放置，或已经放在右上角位置，则下一个数就放在前一个数的正下方位置. 下面是一个5阶幻方 1992年，丁宗智在《幻方》一书中分别介绍了奇数阶、单偶数阶、双偶数阶幻方的多种构造方法，而且分别给出了这三种幻方的构造模型，然后利用构造模型分别构造出相应的2k+1阶、4k阶、4k+2阶幻方，有兴趣的读者可以参见该书. 在中国数学的发展历程中，我们能够看到有趣的数学、计算工具、棋类游戏都与幻方有着内在的联系.幻方对于近代科学的发展起着很大的作用，可应用到“建路”和“Jordan曲线”等的位置解析学及组合解析学.幻方在密码科学中也发挥着作用.例如，按幻方的置乱变换技术，可以将需保密的图像置乱后，再按幻方原理复原，这种置乱变换可以进行多次. 0.2.4配置的优化（优化问题） 很多应用问题有多种配置方案，不同的配置方案考虑的因素和产生的结果并不完全相同，在实际中我们多希望降低因素个数并提高结果精度，这就需要在一些方案中构造或者发现一些较优的方案配置.这类都是优化问题. 0.3典型组合问题举例 例如，在密码算法利用MILP方法分析时，会碰到用不等式刻画成本的问题.设n为正整数，Z2={0，1}，Z2n=Z2xZ2x xZ2为所有分量均在Z2上取值的n元组组成的集合.对任意给定集合Z2n的非空子集我们总可以用一组整系数线性不等式L完全刻画，也就是说，该线性不等式组在限制变元取值为0和1时，其解所构成的集合恰好等于A.例如，n=3，A={（000），（101），（011），（110）}.我们可以构造一线性不等式组L: 其由4个不等式组成.容易验证，上述线性不等式组L关于，的解集恰好为A给定上的非空子集A，求一整系数线性不等式组L，使得该线性不等式组在Z2n上的解集恰好等于4且要求L中不等式个数尽可能少.当集合A规模增大时，不等式组L并不容易发现，可以用逻辑条件模型和凸闭包的方法进行优化. 本书作为组合数学的基础教材，只涉及前三类问题，并且以计数方法为重点介绍组合数学的基本理论和方法，重点介绍数学归纳法、迭代方法、一一对应方法、组合含义法等基本计数方法.关于上面提到的优化问题，有兴趣的读者可以参考运筹学方面的教材. 0.3典型组合问题举例 0.3.1棋盘的完全覆盖 考虑一个8x8的棋盘，假设有足够多的形状相同的骨牌，骨牌的大小恰好能盖住棋盘的两方格.是否能用32张骨牌盖住棋盘的64个方格？如果能，称这样的配置为棋盘的完全覆盖.一般地，当m和n为何值时，mxn的棋盘能完全覆盖？ 0.3.2Konigsberg七桥问题 Konigsberg这座城市被河流划分为A，B，C，D四区，有七座桥连接这四个区.问能否从某一区出发，每一座桥经过一次且仅一次回到原区（图0.1）? 0.3.3四色猜想 在组合数学（图论）中，也许是在全部数学中，*出名的没有（用数学方法）解决的问题是著名的四色猜想.1872年，著名数学家凯利正式向数学学会提出四色猜想问题，从此四色猜想席卷全球，吸引了大量的数学家为之痴迷.任何一个数学家可以在五分钟之内将这个非凡的问题（也称为四色问题）向马路上的任何一个普通人讲清楚.在讲清楚之后，虽然两个人都懂得了这个问题，但是要想解决它却也无能为力. 四色猜想是：“在一个平面或球面上的任何一张地图只用四种颜色着色，使得具有一段公共边界的两个国家染上不同的颜色.每个国家必须由一个单连通的区域构成1976年6月，两位数学家在两台不同的电子计算机上，用了1200个小时，作了100亿个判断，结果没有一张地图是需要五色的，*终证明了四色定理，轰动了世界.当两位数学家发表他们的研究成果后，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这困扰了人们一个多世纪的难题*终得到了解决.不过该方法就像是穷举法，姑且不论这两位数学家是否真的穷举了所有可能情况，相比严谨的理论证明，这种证明无法让人真正信服.四色猜想的理论证明还在继续 0.3.4 36军官问题 有36名军官，来自6个不同的团队，他们有6种不同的军衔.问能否把这36名军官排成一个6x6的方阵，使得每行和每列都是不同团队的军官并且军衔互不相同？ 这个问题是欧拉（Euler）在18世纪作为一个数学游戏提出来的.每名军官可用一个有序对（i，j）来表示，这里i表示他的军衔，j表示他所在的团队，i，j=1，2， ，6.这样36名军官对应36个有序对⑷j）.于是上述问题可表述为：排列这36个有序对（i，j）为一个6x6方阵，使得每行和每列的有序对中**个坐标和第二个坐标上数字1，2， ，6都出现.这样的方阵可以分成两个6x6的
书友推荐
- >
名家带你读鲁迅:故事新编
名家带你读鲁迅:故事新编
¥13.0¥26.0 - >
我与地坛
我与地坛
¥25.8¥28.0 - >
月亮与六便士
月亮与六便士
¥13.4¥42.0 - >
唐代进士录
唐代进士录
¥17.1¥39.8 - >
山海经
山海经
¥20.4¥68.0 - >
推拿
推拿
¥12.2¥32.0 - >
苦雨斋序跋文-周作人自编集
苦雨斋序跋文-周作人自编集
¥6.9¥16.0 - >
【精装绘本】画给孩子的中国神话
【精装绘本】画给孩子的中国神话
¥17.6¥55.0
本类畅销
-
时间简史-普及版
¥16.3¥38 -
数学的魅力;初等数学概念演绎
¥10.8¥22 -
图说相对论(32开平装)
¥14.7¥46 -
刘薰宇的数学三书:原来数学可以这样学全3册
¥35.4¥118 -
中职对口升学数学复习指导
¥23.1¥30 -
高等数学基础
¥31.5¥45
