《組合理論及其套用》是2005年清華大學出版社出版的圖書，作者是李凡長。
基本介紹
- 書名：組合理論及其套用
- 作者：李凡長
- ISBN：9787302112358
- 類別：圖書 > 科學與自然 > 數學
- 頁數：282
- 出版社：清華大學出版社
- 出版時間：2005-09-01
- 裝幀：平裝
內容簡介
《組合理論及其套用》系統地介紹了組合理論的相關知識，全書由13章組成。第1章介紹排列、組合、二項式定理的基本知識；第2章介紹容斥原理與鴿巢原理；第3章介紹遞推關係；第4章介紹生成函式；第5章介紹Pólya計數定理；第6章介紹二分圖；第7章介紹組合矩陣；第8章介紹組合設計；第9章介紹基於有向圖的網路基本理論；第10章介紹整數規劃；第11章介紹組合理論在相關免疫函式中的套用；第12章介紹組合邏輯；第13章介紹組合理論在組合搜尋技術中的套用。本書和同類文獻相比較，新增了組合矩陣、整數規劃、組合理論在相關免疫函式中的套用、組合邏輯和組合搜尋等內容。
本書可作為計算機科學、信息科學、智慧型科學、自動化科學等領域的碩士生、博士生作為一學期72學時的教材使用，同時也可供高等院校相關教師、科研院所的相關研究人員及其他科技工作者作為參考書使用。
目 錄
第1章 排列、組合、二項式定理 1
1.1 加法原理（原則）與乘法原理（原則） 1
1.2 排列與組合 3
1.2.1 集合的排列 3
1.2.2 集合的組合 5
1.3 多重集合的排列與組合 9
1.3.1 多重集合的排列 9
1.3.2 多重集合的組合 12
1.4 二項式定理 15
1.4.1 二項式定理的證明 15
1.4.2 二項式係數的基本性質 16
1.4.3 組合恆等式 18
1.4.4 多項式定理 20
1.5 集合的分劃與第2類Stirling數 21
1.6 正整數的分拆 23
1.6.1 有序分拆 24
1.6.2 無序分拆 25
1.6.3 分拆的Ferrers圖 26
1.7 分配問題 28
1.8 習題 31
第2章 容斥原理與鴿巢原理 34
2.1 容斥原理 34
2.1.1 引論 34
2.1.2 容斥原理的3個形式 35
2.1.3 套用舉例 37
2.2 容斥原理的套用 40
2.2.1 具有有限重複數的多重集合的r組合數 40
2.2.2 錯排問題 40
2.2.3 有禁止模式的排列問題 42
2.2.4 n對夫妻問題（ménage） 44
2.3 M?bim反演 45
2.4 鴿巢原理 46
2.4.1 引論 46
2.4.2 鴿巢原理的形式 46
2.5 Ramsey問題與Ramsey數 48
2.6 習題 50
第3章 遞推關係 53
3.1 遞推關係的建立 53
3.2 常係數線性齊次遞推關係的求解 54
3.3 常係數線性非齊次遞推關係的求解 57
3.4 用疊代法求解遞推關係 59
3.5 Fibonacci數和Catalan數 61
3.5.1 Fibonacci數 61
3.5.2 Catalan數 64
3.6 習題 66
第4章 生成函式 68
4.1 引論 68
4.2 形式冪級數 69
4.3 生成函式的性質 72
4.4 用生成函式求解遞推關係 77
4.4.1用生成函式求解常係數線性齊次遞推關係 77
4.4.2用生成函式求解常係數線性非齊次遞推關係 80
4.5生成函式在計數問題中的套用 82
4.5.1組合數的生成函式 82
4.5.2排列數的指數型生成函式 83
4.5.3分拆數的生成函式 85
4.5.4組合型分配問題的生成函式 86
4.5.5排列型分配問題的生成函式 87
4.6有限制位置的排列及棋子多項式 88
4.7習題 89
第5章Pólya計數理論 92
5.1引論 92
5.2置換群的基本知識 92
5.2.1群和子群 92
5.2.2置換群 93
5.3計數問題的數學模型 95
5.4Burnside引理 96
5.4.1共軛類 96
5.4.2不動置換類 98
5.4.3等價類 98
5.4.4Burnside引理的套用 99
5.5Pólya計數定理 101
5.6習題 106
第6章二分圖 107
6.1相異代表系 107
6.2二分圖的匹配問題 109
6.3二分圖的一個算法 111
6.4習題 115
第7章組合矩陣 118
7.1（0,1）矩陣 118
7.1.1關聯矩陣 118
7.1.2積和式 121
7.1.3（0,1）-矩陣類U(R,S) 125
7.2Hadamard矩陣 129
7.3習題 139
第8章組合設計 140
8.1拉丁方和正交拉丁方 140
8.2正交拉丁方及其性質 141
8.2.1正交拉丁方 141
8.2.2用有限域構造正交拉丁方完備組 142
8.2.3正交拉丁方套用舉例 145
8.3平衡不完全區組設計 147
8.3.1基本概念 147
8.3.2關聯矩陣及其性質 148
8.3.3三連繫 152
8.4幾何設計 154
8.4.1有限射影平面 155
8.4.2平面設計 158
8.4.3仿射平面 160
8.5習題 166
第9章基於有向圖的網路基本理論 168
9.1有向圖的基本概念 168
9.2網路 175
9.3習題 180
第10章整數規劃 183
10.1引論 183
10.2線性整數規劃基本解法 183
10.2.1基本解法概述 183
10.2.2分支定界法 185
10.2.3割平面法 187
10.2.40-1規劃的隱枚舉法 192
10.3線性混合整數規劃解法 193
10.3.1拉格朗日鬆弛法 195
10.3.2交叉分解算法 197
10.4背包問題的解法 199
10.4.1動態規劃解法 199
10.4.2最短路徑方法 200
10.4.3近似算法 201
10.5指派問題解法—匈牙利法 202
10.6集合覆蓋問題解法 204
10.7非線性整數規劃 208
10.7.1字典序枚舉法 208
10.7.2擬布爾規劃 208
10.7.3蒙特卡羅法（隨機取樣法） 209
10.7.4罰函式-湊整算法 209
10.7.5相對差商法 210
10.8習題 211
第11章組合理論在相關免疫函式中的套用 213
11.1相關免疫函式 213
11.1.1相關免疫函式的定義 213
11.1.2相關免疫函式的研究方法 214
11.2線性結構一階相關免疫函式的構造與計數 215
11.2.1概述 215
11.2.2線性結構函式和相關免疫函式 215
11.2.3一階線性結構相關免疫函式的計數下界 217
11.3非退化的相關免疫函式的構造與計數 220
11.3.1幾個引理 220
11.3.2構造方法與計數公式 221
11.41階相關免疫函式的計數下界 223
11.5高階相關免疫函式的構造與計數 225
11.5.1正交矩陣的幾個結構定理 225
11.5.22階相關免疫函式的構造與計數 226
11.5.3m階相關免疫函式的構造與計數 231
11.6平衡m階相關免疫函式 236
11.7非退化高階相關免疫函式的存在性 237
11.8正交矩陣的遞歸生成算法 239
11.9布爾函式的相關免疫性與其他密碼學性質 240
11.9.1相關免疫階與代數次數和非線性度 240
11.9.2一類高非線性度平衡相關免疫函式的構造 241
11.9.3相關免疫性與擴散性 242
11.10滿足k次擴散準則的m階相關免疫函式的構造 243
11.11習題 245
第12章組合邏輯 246
12.1(－演算 246
12.1.1(K－演算系統 246
12.1.2(η－演算系統及(I－演算系統 251
12.1.3化歸 252
12.2(演算的表示能力 256
12.2.1(－項上的運算 256
12.2.2(－可定義的自然數函式 259
12.2.3一階邏輯歸約為(－演算 262
12.3組合邏輯 263
12.3.1組合邏輯形式系統 264
12.3.2(K與CL之間的關係 266
12.4習題 270
第13章組合理論的套用——組合搜尋技術 271
13.1分治法 272
13.1.1SIMD模型的分治算法 272
13.1.2分治法在MIMD模型上的實現途徑 273
13.1.3分治算法的複雜性 274
13.2分枝界限法 275
13.2.18－謎宮問題 275
13.2.2分枝界限方法 278
13.3習題 280
名詞索引 281
參考文獻 283
