新書推薦:
《
洛克现代性政治学之根
》
售價:HK$
109.3
《
奥登诗精选
》
售價:HK$
112.7
《
《你的名字。》美术画集
》
售價:HK$
124.2
《
北齐书(点校本二十四史修订本 全2册)
》
售價:HK$
170.2
《
美丽的地球:高山(呈现世界70余座宏伟高山,感受世界的起伏)
》
售價:HK$
112.7
《
下一个风口:新质生产力驱动下的科创投资逻辑
》
售價:HK$
80.4
《
傻钱:社交浪潮与散户革命
》
售價:HK$
78.2
《
猎头高情商沟通实务
》
售價:HK$
56.4
編輯推薦:
本书是系统阐述组合数学基础、理论、方法和实例的优秀教材,出版30多年来多次改版,被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用,对国内外组合数学教学产生了较大影响,也是相关学科的主要参考文献之一。
內容簡介:
本书侧重于组合数学的概念和思想,包括鸽巢原理、计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构(匹配、实验设计、图)等,深入浅出地表达了作者对该领域全面和深刻的理解。
關於作者:
理查德·A. 布鲁迪(Richard A. Brualdi) 国际线性代数学会前主席,美国工业与应用数学学会(SIAM)会士。美国威斯康星大学麦迪逊分校数学系荣休教授,曾任该系主任多年。他的研究方向包括组合数学、图论、线性代数和矩阵理论、编码理论等。Brualdi教授的学术活动非常丰富,担任过多种学术期刊的主编。2000年由于“在组合数学研究中所做出的杰出终身成就”而获得国际组合数学及其应用学会颁发的欧拉奖。
目錄 :
目 录
译者序
前言
第1章 什么是组合数学1
1.1 例子:棋盘的完美覆盖2
1.2 例子:幻方4
1.3 例子:四色问题6
1.4 例子:36军官问题7
1.5 例子:最短路径问题9
1.6 例子:相互重叠的圆10
1.7 例子:Nim游戏10
1.8 练习题12
第2章 排列与组合16
2.1 四个基本的计数原理16
2.2 集合的排列21
2.3 集合的组合(子集)24
2.4 多重集合的排列28
2.5 多重集合的组合32
2.6 有限概率34
2.7 练习题37
第3章 鸽巢原理42
3.1 鸽巢原理:简单形式42
3.2 鸽巢原理:加强版44
3.3 Ramsey定理47
3.4 练习题50
第4章 生成排列和组合53
4.1 生成排列53
4.2 排列中的逆序57
4.3 生成组合60
4.4 生成r子集67
4.5 偏序和等价关系70
4.6 练习题73
第5章 二项式系数78
5.1 帕斯卡三角形78
5.2 二项式定理80
5.3 二项式系数的单峰性85
5.4 多项式定理88
5.5 牛顿二项式定理90
5.6 再论偏序集92
5.7 练习题95
第6章 容斥原理及应用100
6.1 容斥原理100
6.2 带重复的组合105
6.3 错位排列107
6.4 带有禁止位置的排列110
6.5 另一个禁止位置问题113
6.6 莫比乌斯反演114
6.7 练习题124
第7章 递推关系和生成函数128
7.1 若干数列128
7.2 生成函数134
7.3 指数生成函数138
7.4 求解线性齐次递推关系142
7.5 非齐次递推关系152
7.6 一个几何例子157
7.7 练习题160
第8章 特殊计数序列164
8.1 Catalan数164
8.2 差分序列和Stirling数169
8.3 分拆数180
8.4 一个几何问题185
8.5 格路径和Schrder数187
8.6 练习题195
第9章 相异代表系198
9.1 问题表述198
9.2 SDR的存在性200
9.3 稳定婚姻204
9.4 练习题207
第10章 组合设计210
10.1 模运算210
10.2 区组设计217
10.3 Steiner三元系224
10.4 拉丁方228
10.5 练习题241
第11章 图论导引245
11.1 基本性质245
11.2 欧拉迹251
11.3 哈密顿路径和哈密顿圈256
11.4 二分多重图259
11.5 树263
11.6 Shannon开关游戏268
11.7 再论树271
11.8 练习题278
第12章 再论图论284
12.1 色数284
12.2 平面和平面图290
12.3 五色定理293
12.4 独立数和团数295
12.5 匹配数300
12.6 连通性303
12.7 练习题306
第13章 有向图和网络310
13.1 有向图310
13.2 网络316
13.3 回顾二分图匹配321
13.4 练习题326
第14章 Pólya计数330
14.1 置换群与对称群330
14.2 Burnside定理337
14.3 Pólya计数公式341
14.4 练习题351
练习题答案与提示354
参考文献363
索引364
內容試閱 :
前 言
在这一新版本中,我做了一些细微的改变,具体概括如下:
在第1章,新增加了一节(1.6节),讨论相互重叠圆的问题,用来具体说明后面章节中所讨论的某些计数问题。之前,这一节的相关内容出现在第7章。
第1章中原来关于切割立方体的一节已经删除,但是相关内容放在练习题中。
之前版本中的第2章(鸽巢原理)改成了第3章。之前版本中关于排列和组合的第3章改成了第2章。帕斯卡公式在之前的版本中第一次出现在第5章中,现在出现在第2章中。另外。为了清晰起见。在关于集合的论述中我们不再强调“组合”这一术语,而启用了一个本质上等价的术语“子集”。然而,在多重集合的情况下,我们继续使用“组合”,而不使用在我们看来易产生混淆的术语“多重子集”。
此版本的第2章包含一节(2.6 节)有限概率简介。
此版本的第3章包含Ramsey 定理的证明。
第7章的变化比较大,其中生成函数和指数生成函数移到了本章靠前部分(7.2 节和7.3节),成为更核心的内容。
分拆数这一节(8.3节) 做了扩展。
之前版本中关于二分图匹配的第9章做了根本的改变。现在的第9章是新插入的章节,讨论的是相异代表系(SDR)的问题,包括婚姻和稳定婚姻匹配问题,而不再讨论二分图。
第9章这样改动的结果是,介绍图论的章节(第11章)不再假设先前已介绍过二分图的知识。
再论图论一章(之前版本中的第13章)现在变成了第12章。在本章中,新增加了关于图的匹配数一节(12.5节),在这一节中,第9章中SDR的基础结果被用于二分图。
有向图和网络这一章(之前是第12章)现在是第13章。它新增加了一节,回顾了二分图的匹配,其中有些相关内容出现在之前版本的第9章中。
对于第5版,除了以上列出的这些变化之外,还更正了我注意到的所有印刷错误;增加了少量的说明;改动了一些顺序,使前后文更加通顺;另外还增加了练习题,第5版中共有700道练习题。
根据多年来很多读者的评论,这本书似乎已经通过了时间的检验。因此,我总是犹豫不决而迟迟没有做出更多的改变,也没有增加更多的新话题。我不希望一本书 “太长”(这一前言也不会太长),也不愿意让这本书迎合每个人的癖好。不过,我的确做了上述细节上的改变,相信这些改变会使这本书更加完善。
与之前各版本一样,这一版可以用于一到两个学期的本科生课程。第一个学期可以侧重计数,而第二个学期可以侧重图论和设计。也可以把相关内容合并在一起作为一个学期的课程,如讲解一些计数和图论知识,或者一些计数与设计理论知识,或者选择其他的组合搭配。下面简要说明各章以及它们之间的相互关系。
第1章是介绍,我通常只从中选出一两个话题,最多花两节课时间。第2章讨论的是排列和组合,这一章应该全讲。第3章讨论的是鸽巢原理,这一章至少应该做简单介绍。但是,需要注意的是,后面没有用到一些较难的鸽巢原理应用以及关于Remsey定理那一节的内容。第4章到第8章主要讨论计数技巧及计数序列的相关性质。这些内容应该按照顺序依次讲解。第4章讨论的是排列和组合的生成方案,包括4.5节的偏序和等价关系的介绍。我认为至少应该讲解等价关系,因为它们在数学中无处不在。除了第5章关于偏序集这一节(5.7节) 之外,其余各章本质上都独立于第4章,所以这一章可以跳过或者略讲。你也可以选择根本不讲解偏序集。我把关于偏序集的内容分成两节(4.5节和5.7节),目的是给学生少许时间去消化某些概念。第5章讨论的是二项式系数的性质,而第6章所涉及的是容斥原理。莫比乌斯反演那节(6.6节) 可以归结到容斥原理,这一节对后面没有用。第7章比较长,讨论的是生成函数和递推关系求解。第8章主要讨论的是Catalan数、第一和第二类Stirling数、分拆数以及大Schrder数和小Schrder数。对于这一章的各节你可以选择学习,也可以选择跳过。第8章之后的各章与它都没有关系。第9章讨论的是相异代表系(所谓的婚姻问题)。第12章和第13章要用到第9章的一些内容以及第10章中的拉丁方一节(10.4节)。第10章讨论的是组合设计的某些内容,它与本书其后的内容无关。第11章和第12章对图论进行了比较全面的讨论,并稍侧重于某些图论算法。第13章讨论的是有向图和网络流。第14章讨论置换群作用下的计数问题,这一章大量使用了前面的计数思想。除了最后一个例子之外,它与关于图论和设计的各章无关。
当我将本书用于一学期课程时,喜欢以第14章的Burnside定理及其几个应用收尾。这种做法使学生们能够解决很多计数问题,而这些用前面几章的计数技巧是不能解决的。通常,我不会讲Pólya定理。
继第14章之后,我给出了本书一些练习题的答案和提示。少数练习题旁边标上了“*” 号,表明它们有相当的挑战性。每一个证明结束及每一个例子结束处都标有 “□”号予以明示。
很难评说学习这本书所需要的前提条件。与其他教科书一样,高度激发学生的热情、提起学生的兴趣是很有用的,另外还需要指导教师的热情投入。也许这些前提条件应该这样描述为好:有完备的数学知识。即成功地学习了数学分析相关内容以及线性代数的初等课程。本书对数学分析使用