01 / 導讀
導讀
引用
Lovász, L., Pelikán, J., & Vesztergombi, K. (2003). Discrete Mathematics: Elementary and Beyond. Springer (Undergraduate Texts in Mathematics).
章節概要
全書約290頁，包含15個簡短的章節，最後是一章篇幅較長的習題答案。序言說明，本書並不試圖深入全面地覆蓋離散數學，而是討論精選的結果和方法，主要來自組合學和圖論，並少量涉及初等數論、機率和組合幾何。小節標題常常很隨意（「一場聚會」「分禮物」「遭受攻擊的星球」）。
第1章：來數一數！
本書從一場聚會講起（誰和誰握手，座位有多少種排法），並由此建立基本的計數工具，包括集合、子集的個數及其近似大小、數列、排列、有序子集以及給定大小的子集。
第2章：組合工具
歸納法、數的比較與估計、容斥原理和鴿巢原理。本章以「雙胞胎悖論與老朋友對數」收尾。
第3章：二項式係數與巴斯卡三角
從二項式定理以及分禮物、分錢、組字謎等計數問題出發，引出巴斯卡三角。本章研究其中的恆等式，然後從「鳥瞰」和「鷹眼」兩個角度觀察係數的變化規律。
第4章：斐波那契數
斐波那契的兔子習題、大量恆等式，以及斐波那契數的顯式公式。
第5章：組合機率
有限樣本空間上的事件與機率、實驗的獨立重複、大數定律，以及關於小數定律和「極大數定律」的一節。
第6章：整數、因數與質數
篇幅最長的一章：整除性、質數及其歷史、質因數分解、質數集合、費馬「小」定理、輾轉相除法和同餘。隨後討論「奇特的數」、數論與組合學的聯繫以及質數檢定。
第7章：圖
頂點度數的奇偶、路徑、圈與連通性，以及尤拉路與哈密頓圈。
第8章：樹
如何定義、生長、計數和儲存樹，以及無標號樹的數目。
第9章：尋找最優
圖上的兩個最佳化問題：尋找最佳的樹，以及旅行商問題。
第10章：圖的匹配
由一個跳舞問題和另一個匹配問題引出關於匹配的主要定理，隨後介紹尋找完美匹配的方法。
第11章：幾何中的組合學
對角線交點的計數、區域的計數，以及關於凸多邊形的結果。
第12章：尤拉公式
借「遭受攻擊的星球」引入平面圖和多面體的尤拉公式。
第13章：地圖與圖的著色
用兩種顏色給區域和圖著色、用多種顏色給圖著色，以及地圖著色與四色定理。
第14章：有限幾何、編碼、拉丁方及其他美妙的造物
小小的奇異世界、有限仿射平面與射影平面、區組設計、斯坦納系、拉丁方和編碼。
第15章：複雜性與密碼學一瞥
從「亞瑟王宮廷裡的康乃狄克課堂」出發討論古典密碼學，隨後轉向如何儲存國際象棋的最後一步、如何在不知道密碼的情況下驗證密碼、如何找到大質數，以及公鑰密碼學。
第16章：習題答案
正文中習題的答案，篇幅超過三十頁。
核心概念
第1–4章：計數
- 子集與排列的計數：二項式係數和階乘背後的基本計數。
- 容斥原理與鴿巢原理：用於計數和存在性論證的兩種通用工具。
- 巴斯卡三角：二項式係數的排列方式，及其恆等式和整體規律。
- 斐波那契數：一個有大量恆等式和顯式閉合公式的遞推數列。
第5–6章：機率與數論
- 大數定律：獨立重複實驗中平均值的行為。
- 質因數分解的唯一性：每個整數在本質上只有一種方式寫成質數之積。
- 輾轉相除法與同餘：求最大公因數以及模 m 的算術。
- 費馬小定理與質數檢定：同餘與判別質數之間的聯繫。
第7–13章：圖
- 尤拉路與哈密頓圈：每條邊恰好經過一次與每個頂點恰好訪問一次的區別。
- 樹：不含圈的連通圖，以及如何計數和儲存它們。
- 圖上的最佳化：在網路中選取最佳的樹，以及旅行商問題。
- 完美匹配：圖的頂點何時能沿著邊兩兩配對。
- 平面圖與尤拉公式：頂點、邊和麵之間的關係。
- 圖與地圖的著色：二著色性與四色定理。
第14–15章：設計、編碼與密碼學
- 有限射影平面與區組設計：具有均衡關聯性質的有限結構。
- 拉丁方與編碼：組合排列與糾錯碼。
- 公鑰密碼學：在古典密碼學和複雜性思想之後討論的、以數論為基礎的加密方法。
評析
優點
- 有意精選內容。 序言說，本書的目標不是深入全面地覆蓋離散數學，並稱這一任務本身就定義不清、也不可能完成。本書轉而細緻地展開精選的結果，因此每個主題都有足夠的篇幅來講動機和證明。
- 以證明和解題為核心。 作者儘可能給出證明；證明過難時，也會說明它技術性強、超出本書範圍。序言強烈建議讀者回答正文中提出的問題，並「像解謎一樣」去做每章末的習題。
- 展現數學的連貫與生機。 序言希望表明：結果建立在先前結果之上，存在緊迫的未解問題，思想之美同樣重要。目錄從巴斯卡三角和斐波那契數一直延伸到有限幾何、編碼、複雜性和公鑰密碼學。
- 附有答案。 篇幅可觀的答案一章便於自學。
局限
- 不是一門完整的離散數學課程。 邏輯、形式集合論、關係、斐波那契數以外的遞推求解技巧以及生成函數都沒有出現在章節標題中。需要這些內容的課程得另配一本更全面的教材。
- 演算法本身著墨不多。 演算法出現在輾轉相除法、生成樹、匹配和質數檢定等主題之中，但沒有對演算法分析的系統論述。
- 有些章節很短。 好幾章（幾何中的組合學、尤拉公式）只有十頁左右，更多是引入主題而非充分展開。
在課程中的定位
在本課程書單中，Lovász、Pelikán 和 Vesztergombi 的書是一本以問題為中心、出自數學家之手的入門書。Oscar Levin 的免費教材 Discrete Mathematics: An Open Introduction 和 Susanna Epp 的 Discrete Mathematics with Applications 更系統地覆蓋標準的第一門課程，包括邏輯和證明技巧。Kenneth Rosen 的 Discrete Mathematics and Its Applications 是全面的參考書，幾乎在每個方向上都比本書更廣。用這些書修讀標準課程的學生，可以閱讀本書相應的章節，對計數、數論和圖獲得更深入、更以趣題為導向的理解。
進一步學習時，Graham、Knuth 和 Patashnik 的 Concrete Mathematics 對求和、遞推和生成函數的討論遠遠超出本書第4章。van Lint 與 Wilson 的 A Course in Combinatorics 把本書第10–14章的主題——設計、編碼、拉丁方和圖論——推進到研究水平。第14章可以作為那本書的預習。
如何使用本書
出版社把本書定位於希望體會數學究竟是什麼的數學和電腦科學大學部學生。序言面向的讀者在大學裡可能只學過微積分。閱讀本書不需要微積分，只需要中學數學和動手解題的意願；歸納法在第2章中介紹。
- 核心： 講計數的第1–3章、講數論的第6章以及講圖和樹的第7–8章構成主幹。
- 按興趣選讀： 機率看第5章，最佳化與匹配看第9–10章，幾何、平面性與著色看第11–13章，設計與編碼看第14章，複雜性與密碼學看第15章。第15章會用到第6章的數論。
- 邊讀邊做題。 序言把解題視為必不可少。繼續往下讀之前先嚐試正文中的每個問題，核對第16章之前先做完章末習題。
- 與系統性教材搭配。 如果課程考查邏輯、關係或遞推，就搭配一本系統性教材，而把本書用於加深對其所涵蓋主題的理解和學習動機。