《用于计算机科学的组合学原理》求取 ⇩

第一章线性次序的基本概念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的生成△328

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的结构：有序映射B106

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

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

4.68练习103

4.69类型树108

4.70练习109

第五章若干古典组合110

5A生成函数110

5B包含——排斥原理121

5C网络流12