組合數學（第5版）

《組合數學（第5版）》是2016年11月清華大學出版社出版的圖書，作者是盧開澄、盧華明。

基本介紹

• 書名：組合數學（第五版）
• 作者：盧開澄、盧華明
• 出版社：清華大學出版社
• 出版時間：2016年11月01日
• 定價：45 元
• ISBN：9787302449300

內容簡介

本書是《組合數學(第4版)》的修訂版，全書共分7章，分別是排列與組合、遞推關係與母函式、容斥原理與鴿巢原理、Burnside引理與Pólya定理、區組設計、編碼簡介和組合算法簡介.豐富的實例及理論和實際相結合是本書一大特點，有利於對問題的深入理解. 本書是計算機相關專業本科生和研究生的教學用書，也可作為數學專業師生的教學參考書。

目錄

第1章排列與組合1

1.1加法法則與乘法法則1

1.2一一對應5

1.3排列與組合8

1.3.1排列與組合的模型8

1.3.2排列與組合問題的舉例9

1.4圓周排列14

1.5排列的生成算法15

1.5.1序數法15

1.5.2字典序法17

1.5.3換位法18

1.6允許重複的組合與不相鄰的組合20

1.6.1允許重複的組合20

1.6.2不相鄰的組合21

1.6.3線性方程的整數解的個數問題21

1.6.4組合的生成21

1.7組合意義的解釋22

1.8套用舉例28

1.9Stirling公式36

*1.9.1Wallis公式36

*1.9.2Stirling公式的證明38

習題39

第2章遞推關係與母函式43

2.1遞推關係43

2.2母函式44

2.3Fibonacci序列47

2.3.1Fibonacci序列的遞推關係47

2.3.2若干等式48

2.4優選法與Fibonacci序列的套用49

2.4.1優選法49

2.4.2優選法的步驟51

2.4.3Fibonacci的套用51

2.5母函式的性質52

2.6線性常係數齊次遞推關係55

2.7關於線性常係數非齊次遞推關係62

2.8整數的拆分68

2.9Ferrers圖像71

2.10拆分數估計74

2.11指數型母函式76

2.11.1問題的提出76

2.11.2指數型母函式的定義77

2.12廣義二項式定理78

2.13套用舉例81

2.14非線性遞推關係舉例100

2.14.1Stirling數100

2.14.2Catalan數105

2.14.3舉例109

2.15遞推關係解法的補充112

習題114

第3章容斥原理與鴿巢原理120

31DeMorgan定理120

32容斥定理121

33容斥原理舉例124

3.4棋盤多項式與有限制條件的排列129

3.5有禁區的排列132

3.6廣義的容斥原理134

3.6.1容斥原理的推廣134

3.6.2一般公式135

3.7廣義容斥原理的套用138

3.8第2類司特林數的展開式141

3.9歐拉函式(n)142

3.10n對夫妻問題143

3.11Mbius反演定理143

3.12鴿巢原理146

313鴿巢原理舉例147

314鴿巢原理的推廣150

3141推廣形式之一150

3142套用舉例150

3.14.3推廣形式之二155

3.15Ramsey數156

3.15.1Ramsey問題156

3.15.2Ramsey數159

習題162

第4章Burnside引理與Pólya定理168

41群的概念168

411定義168

412群的基本性質169

42置換群171

43循環、奇循環與偶循環175

44Burnside引理179

441若干概念179

442重要定理181

443舉例說明184

45Pólya定理186

46舉例188

47母函式形式的Pólya定理194

48圖的計數197

習題201

第5章區組設計203

5.1問題的提出203

5.2拉丁方與正交的拉丁方204

5.2.1問題的引入204

5.2.2正交拉丁方及其性質205

5.3域的概念206

5.4Galois域GF(pn)208

5.5正交拉丁方的構造211

5.6正交拉丁方的套用舉例213

5.7均衡不完全的區組設計214

5.7.1基本概念214

5.7.2(b,v,r,k,λ)設計215

5.8區組設計的構成方法218

5.9Steiner三元系220

習題222

第6章編碼簡介225

6.1基本概念225

6.2對稱二元信道226

6.3糾錯碼227

6.3.1最近鄰法則227

6.3.2Hamming不等式228

6.4若干簡單的編碼229

6.4.1重複碼229

6.4.2奇偶校驗碼229

6.5線性碼230

6.5.1生成矩陣與校驗矩陣230

6.5.2關於生成矩陣和校驗矩陣的定理233

6.5.3解碼步驟233

6.6Hamming碼234

6.7BCH碼235

習題238

第7章組合算法簡介241

7.1歸併排序241

7.1.1算法241

7.1.2舉例242

7.1.3複雜性分析242

7.2快速排序243

7.2.1算法的描述244

7.2.2複雜性分析245

7.3FordJohnson排序法246

7.4排序的複雜性下界248

7.5求第k個元素249

7.6排序網路251

7.6.101原理252

7.6.2Bn網路252

7.6.3複雜性分析254

7.6.4Batcher奇偶歸併網路254

7.7快速傅立葉變換255

7.7.1問題的提出255

7.7.2預備定理256

7.7.3快速算法257

7.7.4複雜性分析259

7.8DFS算法260

7.9BFS算法261

7.10αβ剪枝術262

7.11狀態與圖263

7.12分支定界法265

7.12.1TSM問題265

7.12.2任務安排問題268

7.13最短樹與Kruskal算法270

7.14Huffman樹270

7.15多段判決272

7.15.1問題的提出272

7.15.2最佳原理274

7.15.3矩陣鏈積問題274

7.15.4圖的兩點間最短路徑275

習題276