组合数学 （杨雅琴等编著书籍）

书籍信息

书名组合数学

书号978-7-118-08922-6

作者杨雅琴等编著

出版时间2013年8月

译者

版次1版1次

开本16

装帧平装

出版基金

页数224

字数346

中图分类157

丛书名普通高等教育“十二五”规划教材

定价48.00

内容简介

组合数学起源于数学游戏，棋盘上的麦粒和Hanoi塔问题就是经典的有关组合数学的游戏(本书4.1节中对这两个游戏进行了简单介绍)。随着科学研究的不断发展和科学技术的不断进步，组合数学在科学、技术、生产、管理方面的应用越来越广泛、深入，在航天、医学、生物学、金融学、图形处理等领域的前沿阵地发挥着越来越重要的作用。

本书作者多年教学和研究成果的基础上结合组合数学的基本理论，系统地介绍了组合计数、组合设计以及相关数学理论。全书分为11章，介绍了简单排列组合与多重集的简单排列组合、鸽巢原理和Ramsey(拉姆齐)定理、容斥原理、生成函数、递推方程、特殊计数、Burnside(伯恩赛德)定理和Pólya(波利亚)定理、图论、区组设计、编码理论等内容。

本书可以作为数学、计算机科学、密码学或其他相关专业研究生和本科生学习组合数学的教材或参考书。

目录

绪论 1

第一篇计 数 篇

第1章排列与组合 3

1.1加法法则和乘法法则 3

1.2排列 4

1.2.1简单排列 4

1.2.2有条件的排列 5

1.2.3圆排列 6

1.3组合 8

1.4多重集的排列 9

1.5多重集的组合 12

1.6二项式定理 14

1.6.1二项式系数 14

1.6.2组合恒等式 15

1.6.3牛顿二项式定理 15

1.7鸽巢原理 16

1.7.1鸽巢原理的简单形式 16

1.7.2Ramsey数 18

小结 20

习题 21

第2章容斥原理 23

2.1容斥原理 23

2.2容斥原理的应用 26

2.2.1对多重集的组合进行计数 26

2.2.2错排问题 29

2.2.3带有禁位的错排问题 30

小结 33

习题 34

第3章生成函数 36

3.1生成函数的性质 36

3.2指数生成函数 39

小结 40

习题 41

第4章递推方程 42

4.1递推关系 42

4.2利用特征方程求解递推方程 44

4.2.1线性递推方程的解 44

4.2.2非线性递推方程的解 45

4.3利用生成函数求解递推方程 46

4.4利用矩阵的性质求解递推方程 48

4.4.1常系数齐次递推方程矩阵解 48

4.4.2常系数非齐次递推方程矩阵解 50

4.4.3变系数齐次递推方程矩阵解 52

4.4.4变系数非齐次递推方程矩阵解 53

小结 53

习题 54

第5章特殊计数 56

5.1Fibonacci (斐波那契)数列 56

5.2Catlan数(卡特兰数或卡塔兰数) 57

5.3第一类Stirling数 62

5.4第二类Stirling数 67

5.5分拆数 72

5.6分装问题 79

5.6.1相同球和相同盒子的情况 79

5.6.2相同球和不同盒子的情况 79

5.6.3不同球和相同盒子的情况 80

5.6.4不同球和不同盒子的情况 81

小结 82

习题 84

第6章Pólya计数 86

6.1关系 86

6.2群 86

6.3置换群 88

6.4Burnside(伯恩赛德)定理 88

6.5Pólya定理 91

小结 92

习题 94

第二篇图 论 篇

第7章图 95

7.1图的基本概念 95

7.2图的同构 97

7.2.1两个无向不完全图同构映射的求法 97

7.2.2两个有向不完全图同构映射的求法 103

7.2.3不完全图的自同构 105

7.3无向图的连通性 107

7.4有向图的连通性 108

7.5欧拉图 110

7.6Hamilton 图 111

7.6.1非赋权图Hamilton圈(路)的求法 111

7.6.2赋权图Hamilton圈(路)的求法 115

小结 118

习题 120

第8章树 122

8.1树的基本概念 122

8.2最短路径 125

8.3匹配 127

小结 131

习题 132

第9章图的着色 134

9.1图的色多项式 134

9.2图的色数 137

9.3平面图 140

9.4地图着色 142

小结 143

习题 145

第三篇区组设计篇

第10章区组设计 147

10.1完全区组设计 147

10.1.1完全区组设计 147

10.1.2正交拉丁方 149

10.1.3用循环矩阵构建正交拉丁方 150

10.2不完全区组设计 152

10.3柯克曼女学生问题 154

10.4斯坦纳三元系 156

10.5Hadamard（阿达马）矩阵 156

10.5.1Hadamard矩阵 156

10.5.2Ryser猜想的完整证明 158

小结 160

习题 161

第11章编码理论 162

11.1通信系统 162

11.2离散信源的度量 165

11.2.1离散信源的信息熵 166

11.2.2离散信源的联合熵和条件熵 168

11.3离散信道的度量 170

11.4无失真信源的编码 174

11.4.1等长码 176

11.4.2变长码 179

11.4.3霍夫曼（Huffman）编码 185

11.4.4算数编码 187

11.4.5LZ编码 190

11.4.6游程（RL）编码 191

11.5有噪信道编码 192

11.5.1有噪信道的编码定理 192

11.5.2纠错码 194

11.5.3线性分组纠错编码 195

11.5.4二元汉明码 199

11.5.5循环码 199

11.5.6BCH码 204

小结 206

习题 210

参考文献 215