《組合數學（第4版）》是2011年出版的一本圖書，作者是盧開澄。
基本介紹
- 書名：組合數學（第4版）
- 又名：數學組合
- 作者：盧開澄
- ISBN：9787302139614
- 出版社：清華大學出版社
- 出版時間：2011-9-21
- 裝幀：平裝
圖書簡介,圖書前言,圖書目錄,
圖書簡介
本書是《組合數學》第3版的修訂版，全書共分8章，分別是： 排列與組合、遞推關係與母函式、容斥原理與鴿巢原理、Burnside引理與Pólya定理、區組設計、線性規劃、編碼簡介、組合算法簡介。豐富的實例及理論和實際相結合是本書一大特點，有利於對問題的深入理解。
本書是計算機系本科生和研究生的教學用書，也可作為數學專業師生的教學參考書。
本書是計算機系本科生和研究生的教學用書，也可作為數學專業師生的教學參考書。
圖書前言
第4版序言
電子計算機的出現是20世紀最有影響的一件大事，它改變了整個世界的面貌，人們幾乎無處不感到它的存在。哪個領域如果至今還宣稱它與計算機線性無關，十之八九它已落後了。電子計算機使各種難題得以解決，但也萌生出更多的相關理論問題，在這種刺激和影響下，組合數學新軍突起，一躍而成為最活躍的新數學分支，雖然它所討論的問題和所使用的工具有的可追溯到二百多年前。有的組合學家將“計算機科學”定義為研究算法的科學，它為組合數學提供了活動的空間和舞台。組合數學（分析）是算法的理論基礎，它與算法的關係猶如數學分析與計算方法的關係。作者認為這門課實際上是為學習“算法與複雜性分析”作理論的準備。圖論本是這個家族的主要成員，由於它已成長壯大，現已獨立出去。
組合數學來源於實際，不少的討論引人入勝。但初學者也往往有犯難的感覺。其實之所以覺得難，是因為還沒弄懂，一旦明白了，則會恍然大悟而興趣盎然。如果說學這門課有什麼竅門，那就是從實際情況出發，以規模小的問題，模擬“沙盤推演”，尋找其規律性，然後推廣及一般。
作者在實踐中常有這樣的體會：組合數學欲留給讀者以和善可親的形象，相比板著冷峻的面孔，要困難得多。解決方法是求助於實例。如果說法則是支撐肢體的框架，那么它將因豐富多彩的例子而豐滿。本書在這方面，不論質和量都是一個亮點。不少問題饒有趣味，我們也常常為之而上下求索。第4版將依據作者近幾年各自在教學實踐中的經驗，以怎樣使讀者更易接受作為出發點。對第3版的講法和內容作了較大的更改，特別是第2章和第6、7、8章，幾乎重寫了，這部分主要由盧華明執筆。
前面已提到這門課為“算法與複雜性分析”作理論的準備，作者經驗認為，計算機專業的本科生和研究生在學習第1~3章後繼續學習第6~8章是一個不錯的主意，以免有“空返”之憾。其他專業的學生則請酌情處理。
組合數學來源於實際，不少的討論引人入勝。但初學者也往往有犯難的感覺。其實之所以覺得難，是因為還沒弄懂，一旦明白了，則會恍然大悟而興趣盎然。如果說學這門課有什麼竅門，那就是從實際情況出發，以規模小的問題，模擬“沙盤推演”，尋找其規律性，然後推廣及一般。
作者在實踐中常有這樣的體會：組合數學欲留給讀者以和善可親的形象，相比板著冷峻的面孔，要困難得多。解決方法是求助於實例。如果說法則是支撐肢體的框架，那么它將因豐富多彩的例子而豐滿。本書在這方面，不論質和量都是一個亮點。不少問題饒有趣味，我們也常常為之而上下求索。第4版將依據作者近幾年各自在教學實踐中的經驗，以怎樣使讀者更易接受作為出發點。對第3版的講法和內容作了較大的更改，特別是第2章和第6、7、8章，幾乎重寫了，這部分主要由盧華明執筆。
前面已提到這門課為“算法與複雜性分析”作理論的準備，作者經驗認為，計算機專業的本科生和研究生在學習第1~3章後繼續學習第6~8章是一個不錯的主意，以免有“空返”之憾。其他專業的學生則請酌情處理。
作者
2006年9月
2006年9月
圖書目錄
第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公式35
*1.9.1Wallis公式35
*1.9.2Stirling公式的證明37
習題38
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公式35
*1.9.1Wallis公式35
*1.9.2Stirling公式的證明37
習題38
第2章遞推關係與母函式42
2.1遞推關係42
2.2母函式43
2.3Fibonacci序列46
2.3.1Fibonacci序列的遞推關係46
2.3.2若干等式47
2.4優選法與Fibonacci序列的套用48
2.4.1優選法48
2.4.2優選法的步驟50
2.4.3Fibonacci的套用50
2.5母函式的性質51
2.6線性常係數齊次遞推關係54
2.7關於線性常係數非齊次遞推關係61
2.8整數的拆分67
2.9Ferrers圖像70
2.10拆分數估計73
2.11指數型母函式75
2.11.1問題的提出75
2.11.2指數型母函式的定義76
2.12廣義二項式定理77
2.13套用舉例80
2.14非線性遞推關係舉例99
2.14.1Stirling數99
2.14.2Catalan數104
2.14.3舉例108
2.15遞推關係解法的補充111
習題113
第3章容斥原理與鴿巢原理119
3.1De Morgan定理119
3.2容斥定理120
3.3容斥原理舉例123
3.4棋盤多項式與有限制條件的排列128
3.5有禁區的排列131
3.6廣義的容斥原理133
3.6.1容斥原理的推廣133
3.6.2一般公式134
3.7廣義容斥原理的套用137
3.8第二類Stirling數的展開式140
3.9歐拉函式?(n)141
3.10n對夫妻問題142
3.11M?bius反演定理142
3.12鴿巢原理145
3.13鴿巢原理舉例146
3.14鴿巢原理的推廣149
3.14.1推廣形式之一149
3.14.2套用舉例149
3.14.3推廣形式之二154
3.15Ramsey數155
3.15.1Ramsey問題155
3.15.2Ramsey數158
習題161
第4章Burnside引理與Pólya定理167
4.1群的概念167
4.1.1定義167
4.1.2群的基本性質168
4.2置換群170
4.3循環、奇循環與偶循環174
4.4Burnside引理178
4.4.1若干概念178
4.4.2重要定理180
4.4.3舉例說明183
4.5Pólya定理185
4.6舉例187
4.7母函式形式的Pólya定理193
4.8圖的計數196
4.9Pólya定理的若干推廣200
習題203
2.1遞推關係42
2.2母函式43
2.3Fibonacci序列46
2.3.1Fibonacci序列的遞推關係46
2.3.2若干等式47
2.4優選法與Fibonacci序列的套用48
2.4.1優選法48
2.4.2優選法的步驟50
2.4.3Fibonacci的套用50
2.5母函式的性質51
2.6線性常係數齊次遞推關係54
2.7關於線性常係數非齊次遞推關係61
2.8整數的拆分67
2.9Ferrers圖像70
2.10拆分數估計73
2.11指數型母函式75
2.11.1問題的提出75
2.11.2指數型母函式的定義76
2.12廣義二項式定理77
2.13套用舉例80
2.14非線性遞推關係舉例99
2.14.1Stirling數99
2.14.2Catalan數104
2.14.3舉例108
2.15遞推關係解法的補充111
習題113
第3章容斥原理與鴿巢原理119
3.1De Morgan定理119
3.2容斥定理120
3.3容斥原理舉例123
3.4棋盤多項式與有限制條件的排列128
3.5有禁區的排列131
3.6廣義的容斥原理133
3.6.1容斥原理的推廣133
3.6.2一般公式134
3.7廣義容斥原理的套用137
3.8第二類Stirling數的展開式140
3.9歐拉函式?(n)141
3.10n對夫妻問題142
3.11M?bius反演定理142
3.12鴿巢原理145
3.13鴿巢原理舉例146
3.14鴿巢原理的推廣149
3.14.1推廣形式之一149
3.14.2套用舉例149
3.14.3推廣形式之二154
3.15Ramsey數155
3.15.1Ramsey問題155
3.15.2Ramsey數158
習題161
第4章Burnside引理與Pólya定理167
4.1群的概念167
4.1.1定義167
4.1.2群的基本性質168
4.2置換群170
4.3循環、奇循環與偶循環174
4.4Burnside引理178
4.4.1若干概念178
4.4.2重要定理180
4.4.3舉例說明183
4.5Pólya定理185
4.6舉例187
4.7母函式形式的Pólya定理193
4.8圖的計數196
4.9Pólya定理的若干推廣200
習題203
第5章區組設計206
5.1問題的提出206
5.2拉丁方與正交的拉丁方207
5.2.1問題的引入207
5.2.2正交拉丁方及其性質208
5.3域的概念209
5.4Galois域GF(pm)211
5.5正交拉丁方的構造214
5.6正交拉丁方的套用舉例216
5.7均衡不完全的區組設計217
5.7.1基本概念217
5.7.2(b,v,r,k,λ)?設計218
5.8區組設計的構成方法221
5.9Steiner三元素223
5.10Kirkman女生問題225
習題226
第6章線性規劃228
6.1問題的提出228
6.2線性規劃的問題230
6.3凸集230
6.4線性規劃的幾何意義231
6.5單純形法的理論基礎233
6.5.1鬆弛變數233
6.5.2解的充要條件234
6.6單純形法與單純形表格238
6.7改善的單純形法245
6.8對偶概念247
6.9對偶單純形法253
習題258
第7章編碼簡介260
7.1基本概念260
7.2對稱二元信道261
7.3糾錯碼262
7.3.1最近鄰法則262
7.3.2Hamming不等式263
7.4若干簡單的編碼264
7.4.1重複碼264
7.4.2奇偶校驗碼264
7.5線性碼265
7.5.1生成矩陣與校驗矩陣265
7.5.2關於生成矩陣和校驗矩陣的定理268
7.5.3解碼步驟268
7.6Hamming碼269
7.7BCH碼270
習題273
第8章組合算法簡介276
8.1歸併排序276
8.1.1算法276
8.1.2舉例277
8.1.3複雜性分析277
8.2快速排序278
8.2.1算法的描述279
8.2.2複雜性分析280
8.3Ford?Johnson排序法281
8.4排序的複雜性下界283
8.5求第k個元素284
8.6排序網路286
8.6.10?1原理287
8.6.2Bn網路287
8.6.3複雜性分析289
8.6.4Batcher奇偶歸併網路289
8.7快速傅立葉變換290
8.7.1問題的提出290
8.7.2預備定理291
8.7.3快速算法292
8.7.4複雜性分析294
8.8DFS算法295
8.9BFS算法296
8.10αβ剪技術297
8.11狀態與圖298
8.12分支定界法300
8.12.1TSM問題300
8.12.2任務安排問題303
8.13最短樹與Kruskal算法305
8.14Huffman樹305
8.15多段判決307
8.15.1問題的提出307
8.15.2最佳原理309
8.15.3矩陣鏈積問題309
8.15.4圖的兩點間最短路徑310
習題311
5.1問題的提出206
5.2拉丁方與正交的拉丁方207
5.2.1問題的引入207
5.2.2正交拉丁方及其性質208
5.3域的概念209
5.4Galois域GF(pm)211
5.5正交拉丁方的構造214
5.6正交拉丁方的套用舉例216
5.7均衡不完全的區組設計217
5.7.1基本概念217
5.7.2(b,v,r,k,λ)?設計218
5.8區組設計的構成方法221
5.9Steiner三元素223
5.10Kirkman女生問題225
習題226
第6章線性規劃228
6.1問題的提出228
6.2線性規劃的問題230
6.3凸集230
6.4線性規劃的幾何意義231
6.5單純形法的理論基礎233
6.5.1鬆弛變數233
6.5.2解的充要條件234
6.6單純形法與單純形表格238
6.7改善的單純形法245
6.8對偶概念247
6.9對偶單純形法253
習題258
第7章編碼簡介260
7.1基本概念260
7.2對稱二元信道261
7.3糾錯碼262
7.3.1最近鄰法則262
7.3.2Hamming不等式263
7.4若干簡單的編碼264
7.4.1重複碼264
7.4.2奇偶校驗碼264
7.5線性碼265
7.5.1生成矩陣與校驗矩陣265
7.5.2關於生成矩陣和校驗矩陣的定理268
7.5.3解碼步驟268
7.6Hamming碼269
7.7BCH碼270
習題273
第8章組合算法簡介276
8.1歸併排序276
8.1.1算法276
8.1.2舉例277
8.1.3複雜性分析277
8.2快速排序278
8.2.1算法的描述279
8.2.2複雜性分析280
8.3Ford?Johnson排序法281
8.4排序的複雜性下界283
8.5求第k個元素284
8.6排序網路286
8.6.10?1原理287
8.6.2Bn網路287
8.6.3複雜性分析289
8.6.4Batcher奇偶歸併網路289
8.7快速傅立葉變換290
8.7.1問題的提出290
8.7.2預備定理291
8.7.3快速算法292
8.7.4複雜性分析294
8.8DFS算法295
8.9BFS算法296
8.10αβ剪技術297
8.11狀態與圖298
8.12分支定界法300
8.12.1TSM問題300
8.12.2任務安排問題303
8.13最短樹與Kruskal算法305
8.14Huffman樹305
8.15多段判決307
8.15.1問題的提出307
8.15.2最佳原理309
8.15.3矩陣鏈積問題309
8.15.4圖的兩點間最短路徑310
習題311
