組合數學（簡體書）

本書注重對基本概念、基本理論和基本方法的理解和掌握，強調組合思想及組合數學在各個領域的應用。全書分為十章，內容包括預備知識、遞推關係與生成函數、容斥原理及其推廣、特殊計數序列、Polya計數定理、鴿籠原理，Ramsey理論和相異代表系、圖論簡介、代數結構與集合相交的理論、組合設計、概率的方法。

馮榮權，北京大學數學科學學院教授、博士生導師，教育部大學數學課程教學指導委員會委員，中國數學會理事、北京數學會秘書長、中國密碼學會理事、中國密碼學會密碼數學專業委員會和學術工作委員會委員、中國組合數學與圖論學會理事，《數學的實踐與認識》副主編。主要研究方向為密碼學與信息安全及代數組合論，主持或參加多項國家自然科學基金、國家863計劃、國家973計劃、教育部留學回國人員基金和中央辦公廳國家密碼發展基金等項目，參與的項目“數學專業本科生課程體系建設”獲得第六屆高等教育國家教學成果獎二等獎和北京市教育教學成果獎（高等教育）一等獎，項目“北京大學代數類課程體系的綜合改革”獲得第七屆北京市高等教育教學成果獎一等獎。主持的課程“線性代數”2008年被評為國家精品課程（網絡教育），入選第四批國家精品資源共享課（網絡教育課程）立項項目。在國內外核心期刊上發表論文80餘篇，合作翻譯出版《數學天書的證明（第三、四版）》。

宋春偉，北京大學數學科學學院教授、博士生導師，從事組合數學與圖論領域的研究工作。在北京大學多次講授“組合數學”“高等代數”“高等數學”等課程，在日本東京工業大學曾主講“數理情報科學先端特別講座——Topics in Advanced Combinatorics：Extremal Com-binatorics and Algebraic/Probabilistic Methods”。

本書注重對抽象概念和定理的理解，強調方法的運用以及組合數學在各個領域的應用。該書內容豐富新穎，富有時代氣息；敘述簡潔明了、邏輯嚴謹、條理清晰、深入淺出，便於讀者理解和掌握。

自1995年以來，在姜伯駒院士的主持下，北京大學數學科學學院根據國際數學發展的要求和北京大學數學教育的實際，創造性地貫徹教育部“2J口強基礎，淡化專業，因材施教，分流培養”的辦學方針，全面發揮我院學科門類齊全和師資力量雄厚的綜合優勢，在培養模式的轉變、教學計劃的修訂、教學內容與方法的革新，以及教材建設等方面進行了全方位、大力度的改革，取得了顯著的成效。 2001年，北京大學數學科學學院的這項改革成果榮獲全國教學成果特等獎，在國內外產生很大反響。
在本科教育改革方面，我們按照加強基礎、淡化專業的要求，對教學各主要環節進行了調整，使數學科學學院的全體學生在數學分析、高等代數、幾何學、計算機等主乾基礎課程上，接受學時充分、強度足夠的嚴格訓練；在對學生分流培養階段，我們在課程內容上堅決貫徹“少而精”的原則，大力壓縮後續課程中多年逐步形成的過窄、過深和過繁的教學內容，為新的培養方向、實踐性教學環節，以及為培養學生的創新能力所進行的基礎科研訓練爭取到了必要的學時和空間。這樣既使學生打下寬廣、堅實的基礎，又充分照顧到每個人的不同特長、愛好和發展取向。與上述改革相適應，積極而慎重地進行教學計劃的修訂，適當壓縮常微、複變、偏微、實變、微分幾何、抽象代數、泛函分析等後續課程的周學時，並增加了數學模型和計算機的相關課程，使學生有更大的選課餘地。
在研究生教育中，在註重專題課程的同時，我們制定了30多門研究生普選基礎課程（其中數學系18門），重點拓寬學生的專業基礎和加強學生對數學整體發展及最新進展的了解。
教材建設是教學成果的一個重要體現。與修訂的教學計劃相配合，我們進行了有組織的教材建設。計劃自1999年起用8年的時間修訂、編寫和出版40餘種教材。這就是將陸續呈現在大家面前的“北京大學數學教學系列叢書”，這套叢書凝聚了我們近十年在人才培養方面的思考，記錄了我們教學實踐的足跡，體現了我們教學改革的成果，反映了我們對新世紀人才培養的理念，代表了我們新時期的數學教學水平。
經過20世紀的空前發展，數學的基本理論更加深入和完善，而計算機技術的發展使得數學的應用更加直接和廣泛，而且活躍於生產第一線，促進著技術和經濟的發展，所有這些都正在改變著人們對數學的傳統認識。同時也促使數學研究的方式發生巨大變化，作為整個科學技術基礎的數學，正突破傳統的範圍而向人類一切知識領域滲透，作為一種文化，數學科學已成為推動人類文明進化、知識創新的重要因素，將更深刻地改變著客觀現實的面貌和人們對世界的認識，數學素質已成為今天培養高層次創新人才的重要基礎。數學的理論和應用的巨大發展必然引起數學教育的深刻變革，我們現在的改革還是初步的。教學改革無禁區，但要十分穩重和積極；人才培養無止境，既要遵循基本規律，更要不斷創新，我們現在推出這套叢書，目的是向大家學習。讓我們大家攜起手來，為提高中國數學教育水平和建設世界一流數學強國而共同努力。

第一章 預備知識 1
1.1 集合, 關係, 函數 1
1.2 偏序集 3
1.3 初等計數方法 6
1.4 組合恆等式 14
習題一 19
第二章 遞推關係與生成函數 22
2.1 線性齊次遞推關係 22
2.2 線性非齊次遞推關係 27
2.3 生成函數理 30
2.3.1 普通生成函數 39
2.3.2 指數型生成函數 43
2.3.3 Dirichlet 生成函數 50
習題二 56
第三章 容斥原理及其推廣 59
3.1 容斥原理在計數理論中的應用 59
3.2 偏序集上的M?obius 反演 66
3.3 生成函數與容斥原理的推廣 77
習題三 81
第四章 特殊計數序列 83
4.1 Catalan 數, Dyck 路, q-模擬和組合統計量 83
4.2 Schroder 數, Schroder 路和格路徑 95
4.3 第一、二類Stirling 數 100
4.4 分拆數 109
習題四 116
第五章 Polya 計數定理 120
5.1 問題的提出 120
5.2 置換群, 群在集合上的作用 121
5.3 Polya 計數定理 128
5.4 帶權的P?olya 計數定理 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
第八章 代數結構與集合相交的理論 191
8.1 偶鎮與奇鎮 191
8.2 相交的集合 196
8.3 幾個經典結果 204
8.4 多項式空間 209
習題八 214
第九章 組合設計 216
9.1 關聯結構 216
9.2 t-設計 218
9.3 平衡不完全區組設計 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