用于计算机科学的组合学原理PDF电子书下载

第一章 线性次序的基本概念 1

1.1定义（集合上的关系） 1

1.2定义（等价关系，有序关系） 1

1.3定义（集的划分） 1

1.4定义（等价类） 1

1.5定理（划分和等价关系之间的关系） 2

1.6注释 2

1.7等价关系的例子 2

1.8定义（覆盖关系） 3

1.9有序集的例子 3

1.10定义（哈希图） 3

1.11以x|y为序关系，集合S＝12的哈希图 3

1.12?的所有子集的哈希图 3

1.13练习 4

1.14检验表 4

1.15链接表 5

1.16图1.15的结构图表 6

1.17更复杂的数据结构 6

1.18一般情况的结构图表 8

1.19练习 8

1.20定义（字母次序） 8

1.21评论（伴同字典序） 8

1.22练习 9

1.23练习 9

1.24辞典式桶排序 9

1.25练习 10

1.26前缀字典序的树图 10

1.27练习 11

1.28练习 11

1.29练习 11

1.30例题 12

1.31瓷砖所铺之盘的字典表（回溯问题） 12

1.32样品砖的形状 12

1.33练习 13

1.34例题 13

1.35多米诺骨牌复盖 14

1.36 4×4盘的全部多米诺骨牌覆盖 14

1.37练习 15

1.38有序划分树 16

1.39划分树的局部描述 16

1.40 2 3的划分树 17

1.41 2 3上的字母次序 17

1.42图1.41的变形 1

1.43图1.42的变形 18

1.44 S.上的字典序 18

1.45练习 19

1.46 S3的直接插入划分树 19

1.47直接插入树的编码翻译 19

1.48练习 20

1.49练习 20

1.50 2 3递减函数的划分树 20

1.51用字典序表示D（6 4）的树图 21

1.52练习 21

1.53定义 22

1.54定义 22

1.55边的补树 22

1.56以补树形式描述叶子的序同构 23

1.57D（6 2）的叶子序同构 23

1.58定理 23

1.59定理 24

1.60练习 24

1.61棋盘对称的问题 25

1.62练习 25

1.63例题 25

1.64用于改进轨道的键 26

1.65轨道的第三种排序改进法 26

1.66轨道的第四种排序改进法 26

1.67轨道划分树 27

1.68关于四个或更少皇后问题的若干解 27

1.69练习 27

1.70练习 27

1.71 8个皇后问题的两个解 28

1.72练习 28

1.73关于Q3的生成△3 28

1.74△3的生成中最初一段 29

1.75△3的生成中最后一段 30

第二章 论题I：排序问题 31

2.1比较排序的一般观念 31

2.2定义 32

2.3 2.1节中各种方法的比较次数 32

2.4希尔法 33

2.5 h—类 33

2.6希尔法的一些综合结论 33

2.7一个载短的完全二叉树 33

2.8删除和重建堆 34

2.9二叉树的数据结构和颠倒广度优先表 34

2.10模糊观念 34

2.11排序方法和排序网络 35

2.12定义 36

2.13排序网络的例子 37

2.14定义 38

2.15 σ＝71654832的反演图 38

2.19反演网格 38

2.17相邻反演 39

2.18图2.19的变形 39

2.19定义 39

2.20辅助定理 40

2.21辅助定理 40

2.22证明辅助定理2.21的图示 40

2.23定理 41

2.24关于排序谋略的信息理论下界 41

2.25定理 41

2.26定理 41

2.27练习 41

2.28合并插入 42

2.29定理 42

2.30定理（0一1原理） 44

2.31定理（推广的矩阵原理） 44

2.32定理 45

2.33定理 46

2.34 Batcher排序 47

第三章 论题11：基本组合表 48

3.1从?4到?3的函数（a3，a2，a1，ao）的辞典表 48

3.2同一函数的三种描述 49

3.3定理 49

3.4定理3.3的补树图 50

3.5练习 51

3.6下降因子表 52

3.7评论 53

3.8通过相邻符号而得到的排列表 53

3.9按字典序排列的增函数 55

3.10定理 56

3.11系 56

3.12二项式系数（n k）（n＝0，.，20； k＝0，.，5）表 57

3.13不减函数的代码 57

3.14有固定多项式指数的有序划分 61

3.15对划分块排序的约定 61

3.16关于字典序的RG函数 62

3.17与RG函数相关的划分 64

3.18尾部系数表 64

3.19限制尾部系数表 66

3.20尾部系数E（r）（n， m）表 67

3.21定义 68

3.22递归式 68

3.23定理 68

3.24定理3.23的补树图 68

3.25图3.42的简化树图 69

3.26系 70

3.27递归公式 70

3.28递归式 71

3.29 S（d，k）——将d放进k块的划分总数 71

3.30练习 72

3.31没有循环的算法（组合Gray Code） 73

第四章 论题：对称——轨道计数和有序算法 74

4.1定义 74

4.2群作用的例子：二面体群 75

4.3练习 76

4.4注释 76

4.5定义 76

4.6练习 76

4.7定义 76

4.8两面体群作用的轨道 76

4.9引理 77

4.10引理 77

4.11三角形的旋转和反射作用矩阵 78

4.12定义 79

4.13练习 79

4.14定义 79

4.15引理（一般化的Burnside引理） 79

4.16推论 79

4.17例题4.18的作用矩阵 79

4.18处理集元素的Burnside引理的例题 80

4.19图4.17所示作用矩阵中的变量更换 82

4.20三角形的对称 82

4.21经典Burnside引理的例题 83

4.22等式 84

4.23 Burnside引理及群特征 84

4.24 Burnside引理与群特征的第二个例题 85

4.25等式 85

4.26练习 86

4.27注释 86

4.28定义 86

4.29引理（White引理） 86

4.30定义 87

4.31定义（White引理的矩阵解释） 87

4.32练习 87

4.33六边形的对称群的标准矩阵 87

4.34函数f：D→R的例子 88

4.35练习 89

4.36定义（Po lya作用） 89

4.37 Potya作用的例题 90

4.38定义 90

4.39定义4.38的例题 90

4.40 Potya作用的恒等式及其例题 91

4.41定理（Potya定理） 92

4.42定义 92

4.43 Potya定理的循环指数多项式 92

4.44作用在面上的立方体旋转群 92

4.45练习 93

4.46对称群的循环指数多项式 94

4.47练习 94

4.43作用在3×2上S3与S2的圈积 95

4.49立方体的完全对称群为一个圈积 96

4.50圈积C4［C3］的作用 97

4.51C4［C3］的圈积恒等式 97

4.52一般情况的圈积等式 97

4.53定理 98

4.54定理 99

4.55定义 99

4.56定义 100

4.57示意能够发生的所有事情的分类 100

4.58引理 101

4.59引理 102

4.60定理（debruijn） 102

4.61练习 102

4.62正方形顶点的LMR图 104

4.63LMR图的轨道代表系 105

4.64练习 106

4.65有序算法4.66的结构：有序映射B 106

4.66有序映射B的有序算法 106

4.67对值域作用的有序算法 107

4.68练习 103

4.69类型树 108

4.70练习 109

第五章 若干古典组合 110

5A生成函数 110

5B包含——排斥原理 121

5C网络流 12