面向計算機科學的組合數學

目錄

第0 章緒論........................................................................... 1

第1 章排列組合...................................................................... 8

1.1 基本計數原理.............................................................................. 8

1.1.1 加法原理........................................................................... 8

1.1.2 乘法原理........................................................................... 10

1.1.3 減法原理........................................................................... 11

1.1.4 除法原理........................................................................... 12

1.2 集合的排列與組合........................................................................ 13

1.2.1 排列................................................................................. 13

1.2.2 組合................................................................................. 15

1.3 球盒模型與格路模型..................................................................... 18

1.3.1 球盒模型........................................................................... 18

1.3.2 格路模型........................................................................... 19

1.4 二項式定理與組合恒等式............................................................... 21

1.4.1 二項式定理與二項式系數...................................................... 21

1.4.2 利用二項式定理推導組合恒等式.............................................. 24

1.4.3 多項式定理........................................................................ 26

1.5 多重排列與環形排列..................................................................... 27

1.5.1 多重排列........................................................................... 27

1.5.2 環形排列........................................................................... 30

1.6 可重組合與不相鄰組合.................................................................. 31

1.6.1 可重組合........................................................................... 31

1.6.2 不相鄰組合........................................................................ 36

1.7 生成全排列....................................................................... 36

1.7.1 Stirling 近似公式................................................................. 36

1.7.2 字典序法........................................................................... 37

1.7.3 遞增進位制數法.................................................................. 40

1.7.4 遞減進位制數法.................................................................. 42

1.7.5 SJT 算法............................................................................ 42

1.8 生成組合........................................................................ 45

習題.................................................................................. 46

第2 章鴿巢原理.................................................................... 52

2.1 鴿巢原理的基本形式..................................................................... 52

2.2 鴿巢原理的推廣形式..................................................................... 55

2.3 整點問題.................................................................... 57

2.4 Ramsey 問題..................................................................... 58

2.4.1 完全圖二染色的Ramsey 定理................................................. 59

2.4.2 Ramsey 定理的推廣形式.............................................. 62

習題................................................................................ 63

第3 章母函數........................................................................ 66

3.1 引論............................................................................ 66

3.2 母函數的性質........................................................... 69

3.3 整數拆分與Ferrers 圖像................................................................. 72

3.3.1 有序拆分........................................................................... 73

3.3.2 無序拆分........................................................................... 73

3.3.3 Ferrers 圖像........................................................................ 77

3.4 指數型母函數................................................................... 79

習題.............................................................................. 84

第4 章線性常系數遞推關系..................................................................... 87

4.1 引論.............................................................................. 87

4.2 Fibonacci 數列.............................................................. 89

4.3 母函數與遞推關系........................................................................ 94

4.4 齊次線性常系數遞推關系............................................................... 104

4.4.1 特征多項式........................................................................ 105

4.4.2 通過特征多項式求解齊次線性常系數遞推關系............................ 106

4.5 非齊次線性常系數遞推關系............................................................ 118

4.5.1 差分法.............................................................................. 118

4.5.2 特解法.............................................................................. 123

4.6 遞推關系的漸近分析..................................................................... 129

習題.............................................................................. 137

第5 章特殊計數序列............................................................... 141

5.1 Catalan 數...................................................................... 141

5.2 錯位排列...................................................................... 148

5.3 第二類Stirling 數........................................................... 151

5.4 第一類Stirling 數............................................................. 160

5.4.1 無符號的第一類Stirling 數..................................................... 160

5.4.2 有符號的第一類Stirling 數..................................................... 164

5.4.3 第一類與第二類Stirling 數的關系............................................ 165

習題.............................................................................. 167

第6 章容斥原理..................................................................... 169

6.1 容斥原理及其證明........................................................................ 169

6.2 帶約束的排列問題........................................................................ 175

6.3 帶約束的組合問題........................................................................ 183

6.4 廣義容斥原理................................................................... 187

6.5 M?bius 反演.................................................................... 188

習題............................................................................... 195

第7 章Pólya 計數理論................................................................ 199

7.1 群論基礎..................................................................... 199

7.2 置換群...................................................................... 202

7.3 Burnside 引理.............................................................. 210

7.4 Pólya 計數定理.............................................................. 214

7.5 空間多面體的染色問題.......................................................... 218

習題................................................................................ 225

第8 章組合設計......................................................................... 229

8.1 區組設計...................................................................... 229

8.1.1 平衡不完全區組設計............................................................ 229

8.1.2 對稱的平衡不完全區組設計.................................................... 235

8.1.3 Steiner 三元系..................................................................... 241

8.1.4 區組設計的可解性............................................................... 243

8.2 有限平面幾何................................................................... 246

8.2.1 有限射影平面..................................................................... 246

8.2.2 利用有限域構造有限射影平面................................................. 252

8.2.3 有限仿射平面..................................................................... 254

8.2.4 利用有限域構造有限仿射平面................................................. 259

8.3 正交拉丁方.................................................................... 260

8.3.1 拉丁方.............................................................................. 261

8.3.2 互正交拉丁方..................................................................... 265

習題................................................................................ 273

附錄A 離散數學基礎..................................................................... 277

A.1 集合與偏序關系.......................................................................... 277

A.2 偏序卷積與M?bius 反演................................................................ 281

附錄B 組合數學中的代數結構.................................................................. 289

B.1 群............................................................................. 289

B.2 環與形式冪級數環........................................................................ 292

B.3 有限域........................................................................ 299