面向計算機科學的組合數學
馬昱春、高健
- 出版商: 清華大學
- 出版日期: 2026-05-01
- 售價: $360
- 語言: 簡體中文
- 頁數: 316
- ISBN: 7302715092
- ISBN-13: 9787302715092
-
相關分類:
離散數學 Discrete-mathematics
下單後立即進貨 (約4週~6週)
商品描述
"本書系統介紹組合數學的核心理論與方法，並緊密結合現代計算機科學前沿領域的應用需求。全書共8章，主要內容包括排列組合、鴿巢原理、母函數、線性常系數遞推關系、特殊計數序列、容斥原理、Pólya計數理論與組合設計，附錄部分深入補充了集合論、偏序集、群論等數學基礎，為理解組合結構提供堅實支撐。 本書突破傳統組合數學教材的編排方式，以“概念-方法-應用”為主線，註重數學思維與計算思維的融合。本書不僅涵蓋生成函數、遞推關系、容斥原理等經典工具，還引入格路模型、球盒模型、Ramsey理論、Catalan數、Stirling數等計算機科學中的典型問題，並通過大量示例展示組合數學在算法分析、網絡優化、編碼理論等方面的實際應用。 本書強調組合數學在智能時代的重新定位與拓展，適合作為高等學校計算機科學、軟件工程、人工智能等相關專業的本科生或研究生教材，也可供從事算法研究、數據科學、人工智能開發的科研人員與工程師參考。 "
作者簡介
馬昱春，博士，清華大學計算機科學與技術系教授、北京市青年教學名師。獲得高等教育（本科）國家級教學成果獎二等獎一項，北京市教學成果獎一等獎兩項，其負責的“組合數學”課程被評為國家精品在線開放課程、清華大學研究生精品課；“離散數學（1）”被評為北京市課程思政示範課、清華大學本科生精品課程、清華大學標桿課。曾獲北京高校青年教師教學基本功比賽理工組一等獎、清華大學青年教師優秀獎、寶鋼優秀教師獎、高校計算機專業優秀教師獎勵計劃、全國混合式創新大賽特等獎第一名。
目錄大綱
目錄
第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
