本書注重對基本概念、基本理論和基本方法的理解和掌握,強調(diào)組合思想及組合數(shù)學在各個領(lǐng)域的應用。全書分為十章,內(nèi)容包括預備知識、遞推關(guān)系與生成函數(shù)、容斥原理及其推廣、特殊計數(shù)序列、Polya計數(shù)定理、鴿籠原理,Ramsey 理論和相異代表系、圖論簡介、代數(shù)結(jié)構(gòu)與集合相交的理論、組合設計、概率的方法。
本書注重對抽象概念和定理的理解,強調(diào)方法的運用以及組合數(shù)學在各個領(lǐng)域的應用。該書內(nèi)容豐富新穎,富有時代氣息;敘述簡潔明了、邏輯嚴謹、條理清晰、深入淺出,便于讀者理解和掌握。
馮榮權(quán):北京大學教授,博士生導師。宋春偉:北京大學教授,博士生導師。
第一章 預備知識 1
1.1 集合, 關(guān)系, 函數(shù) 1
1.2 偏序集 3
1.3 初等計數(shù)方法 6
1.4 組合恒等式 14
習題一 19
第二章 遞推關(guān)系與生成函數(shù) 22
2.1 線性齊次遞推關(guān)系 22
2.2 線性非齊次遞推關(guān)系 27
2.3 生成函數(shù)理 30
2.3.1 普通生成函數(shù) 39
2.3.2 指數(shù)型生成函數(shù) 43
2.3.3 Dirichlet 生成函數(shù) 50
習題二 56
第三章 容斥原理及其推廣 59
3.1 容斥原理在計數(shù)理論中的應用 59
3.2 偏序集上的M?obius 反演 66
3.3 生成函數(shù)與容斥原理的推廣 77
習題三 81
第四章 特殊計數(shù)序列 83
4.1 Catalan 數(shù), Dyck 路, q-模擬和組合統(tǒng)計量 83
4.2 Schroder 數(shù), Schroder 路和格路徑 95
4.3 第一、二類Stirling 數(shù) 100
4.4 分拆數(shù) 109
習題四 116
第五章 Polya 計數(shù)定理 120
5.1 問題的提出 120
5.2 置換群, 群在集合上的作用 121
5.3 Polya 計數(shù)定理 128
5.4 帶權(quán)的P?olya 計數(shù)定理 132
習題五 139
第六章 鴿籠原理, Ramsey 理論和相異代表系 140
6.1 鴿籠原理及其應用 140
6.2 從鴿籠原理到Ramsey 定理 146
6.3 相異代表系和Hall 定理 152
習題六 156
第七章 圖論簡介 159
7.1 一些基本概念 159
7.2 樹 165
7.3 歐拉圖和Hamilton 圖 169
7.4 染色理論 172
7.5 匹配與覆蓋 178
7.6 完美圖 183
習題七 188
第八章 代數(shù)結(jié)構(gòu)與集合相交的理論 191
8.1 偶鎮(zhèn)與奇鎮(zhèn) 191
8.2 相交的集合 196
8.3 幾個經(jīng)典結(jié)果 204
8.4 多項式空間 209
習題八 214
第九章 組合設計 216
9.1 關(guān)聯(lián)結(jié)構(gòu) 216
9.2 t-設計 218
9.3 平衡不完全區(qū)組設計 223
9.4 Hadamard 矩陣和Hadamard 設計 232
9.5 差集 238
9.6 正交拉丁方 243
習題九 254
第十章 概率的方法 260
10.1 幾個例子 260
10.2 線性與修補 265
10.3 二階矩 275
10.4 Lovasz 局部定理 285
習題十 291
參考文獻 292
習題答案與提示 298