01 / 導讀
導讀
引用
van Lint, J. H., & Wilson, R. M. (2001). A Course in Combinatorics (2nd ed.). Cambridge University Press.
章節概要
第二版共38個簡短的章，前有兩版的序言，後有參考文獻和索引；印刷本約600頁。劍橋大學出版社把它描述為一本討論事物如何排列與分配的書，涉及幾何、代數和分析的思想，以統一的方式處理圖論、極值問題、設計、著色和編碼，適合高年級本科或研究生起始階段的課程。各章以主題命名，下面的分組依照目錄順序。
第1–4章：圖；樹；圖的著色與拉姆齊定理；圖蘭定理與極值圖
全書以基礎圖論和樹開篇，隨即轉入著色、拉姆齊定理和圖蘭定理所代表的極值問題。
第5–9章：相異代表系；迪爾沃思定理與極值集合論；網路中的流；德布魯因序列；兩個(0, 1, ⋆)問題：圖的編址與雜湊編碼方案
這幾章涵蓋相異代表系、迪爾沃思定理與極值集合論、網路中的流、德布魯因序列，以及關於圖的編址和一種雜湊編碼方案的一對問題。
第10–12章：容斥原理與反演公式；積和式；範德瓦爾登猜想
計數的線索從容斥原理開始，然後轉向積和式以及關於積和式的範德瓦爾登猜想。
第13–15章：基本計數與斯特林數；遞推與生成函式；分拆
計數技術繼續展開，涉及斯特林數、遞推、生成函式和分拆。
第16–18章：(0, 1)矩陣；拉丁方；哈達瑪矩陣與裡德–穆勒碼
接下來的一組轉向由0和1構成的矩陣、拉丁方以及哈達瑪矩陣，並以裡德–穆勒碼結束。
第19–23章：設計；碼與設計；強正則圖與部分幾何；正交拉丁方；射影幾何與組合幾何
書中在這裡彙集了核心的結構：設計及其與碼的關係、強正則圖與部分幾何、正交拉丁方，以及射影幾何與組合幾何。
第24–26章：高斯數與q類比；格與默比烏斯反演；組合設計與射影幾何
這一組討論q類比、格與默比烏斯反演，並再次回到組合設計與射影幾何。
第27–31章：差集與自同構；差集與群環；碼與對稱設計；結合方案；圖論中的（更多）代數技巧
代數部分處理差集、群環、對稱設計與碼、結合方案，以及圖論中更多的代數方法。
第32–36章：圖的連通性；平面性與著色；惠特尼對偶；圖在曲面上的嵌入；電網路與方塊剖分
最後一組圖論章節涉及連通性、平面性與著色、對偶、圖在曲面上的嵌入，以及電網路與「方塊剖分正方形」問題。
第37–38章：波利亞計數理論；巴拉尼艾定理
全書以波利亞計數理論和巴拉尼艾定理收尾。
核心概念
第1–18章：圖、極值問題與計數
- 拉姆齊理論與極值圖：拉姆齊定理和圖蘭定理（第3–4章）。
- 容斥與積和式：第10–12章。
- 生成函式與分拆：第13–15章。
- 拉丁方與哈達瑪矩陣：第17–18章。
第19–38章：設計、碼、幾何與更多圖論
- 設計、碼與結合方案：第19–20章、第29章和第30章。
- 強正則圖、差集與群環：第21、27和28章。
- 平面性、對偶與圖的嵌入：第33–35章。
- 波利亞計數與巴拉尼艾定理：第37–38章。
評析
優點
- 在簡短的章節中展現廣度。 38個緊湊的章節給出這一學科的一幅寬廣地圖，劍橋大學出版社稱其以統一方式處理圖論、極值問題、設計、著色和編碼。迪特爾·榮格尼克爾在 Zentralblatt MATH 上評論時預期它會成為組合學教材中的標準選擇之一。
- 優雅的證明與好問題。 《數學公報》稱它是優雅證明和誘人例子的來源；劍橋引用的另一篇評論則指出，書中有大量有趣的問題、具體的例子，以及有用的註記和參考文獻。
- 在兩個層次上都有用。 劍橋引用了署名 EMS 的一篇評論，稱它值得推薦給任何學習組合學的學生，並說由於內容廣泛，對研究者也有許多新東西。
- 代數與幾何思想並置。 目錄把碼、設計、有限幾何、群環和結合方案放在一本書裡，讓學生從多個側面看到同樣的結構。
侷限
- 要求較高。 《數學公報》的評論說，沒有人會覺得這本書容易，並稱它毫不掩飾地、令人印象深刻地「數學」。作者設定的讀者是高年級本科生或研究生起步階段的學生。
- 不是一條單一的敘事線。 各章按主題而不是連續的論證來編排，因此從第1章到第38章沒有一條貫穿始終的線索，讀者要預期自己選擇一條路線。
- 先修要求不均。 前面的章節除離散數學課程外幾乎不需要什麼，而代數性的章節（群環、結合方案）要用到讀者必須已有的抽象代數。
在課程中的定位
在一份其餘多為入門課程的書單裡，這是高階的組合學著作。Susanna Epp 的《Discrete Mathematics with Applications》、Kenneth Rosen 的《Discrete Mathematics and Its Applications》以及 Oscar Levin 的開放教材，面向初次接觸這類數學的讀者，講授邏輯、證明、計數與圖。Lovász、Pelikán 和 Vesztergombi 的《Discrete Mathematics: Elementary and Beyond》是一本以問題為導向的簡短入門書，自然地排在本書之前。Graham、Knuth 和 Patashnik 的《Concrete Mathematics》在生成函式和遞推上與本書有重疊，但面向演算法分析，而 van Lint 和 Wilson 的書更偏向設計、碼與有限幾何。
如何使用本書
本書適合已修完離散數學課程和第一門線性代數課程的高年級本科生與研究生；一些抽象代數知識對後面的章節有幫助。
- 核心路徑： 第1–4章（圖與極值問題）、第10–15章（計數）以及第19、20章（設計與碼），可以構成一門自足的入門課。
- 代數路徑： 關於強正則圖、幾何、差集與結合方案的第21、23和27–30章，對懂一些抽象代數的讀者回報更大。
- 圖論路徑： 第32–36章構成關於連通性、平面性與曲面的第二門圖論課。
- 練習： 由於各章簡短而相對獨立，可以每週讀一章，也可以不按順序閱讀；做書中的問題，並利用評論者稱讚的註記和參考文獻。