01 / 導讀
導讀
引用
Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley.
章節概要
全書共九章，其後是全部習題的解答、參考文獻、習題出處說明和索引。前言把這門學科描述為連續數學與離散數學的融合：即運用一系列解題技巧，對數學公式進行有控制的演算。重點在於演算技巧，而不是存在性定理或組合推理。行文輕鬆隨意，頁邊印有學生的評語（“塗鴉”）以及前輩數學家的引文。
第1章：Recurrent Problems（遞迴問題）
全書以三個問題開篇：漢諾塔、平面上的直線和約瑟夫問題。每個問題都匯出一個遞推式，並隨後求解。
第2章：Sums（求和）
Σ 記號、和與遞推的聯絡、和式的變換、多重和，以及求和的一般方法。有限微積分與無限微積分、無窮和兩節結束本章。
第3章：Integer Functions（取整函式）
向下取整與向上取整及其應用、取整遞推、二元運算“mod”，以及含取整的和。
第4章：Number Theory（數論）
整除性、素數、階乘的因子、互素性、作為同餘關係的“mod”、獨立剩餘、更多應用，以及函式 φ 與 μ。
第5章：Binomial Coefficients（二項式係數）
這是最長的一章。先講基本恆等式與基本練習、技巧和母函式，再講超幾何函式及其變換，以及部分超幾何和。最後是第5.8節“機械求和”，這是第二版的新增內容，前言稱其源於 Doron Zeilberger 的想法。
第6章：Special Numbers（特殊數）
Stirling 數、Euler 數、調和數與調和求和、Bernoulli 數、Fibonacci 數，以及連分多項式。
第7章：Generating Functions（母函式）
本章以多米諾骨牌和找零錢兩個引例開頭，隨後講基本操作、解遞推、特殊母函式、卷積、指數母函式和 Dirichlet 母函式。
第8章：Discrete Probability（離散機率）
定義、均值與方差、機率母函式、拋硬幣問題，以及雜湊。
第9章：Asymptotics（漸近分析）
增長率的層級、O 記號及其演算、兩個漸近技巧、Euler 求和公式，以及收尾的“最終求和”一節。
核心概念
第1–3章：遞推、求和、取整函式
- 遞推式與閉式：用前面的值表示的問題，以及求出不含遞迴的公式的目標。
- 有限微積分：針對離散函式的差分與求和演算，與微分和積分相對應。
- 取整函式：第3章展開其性質並貫穿全書使用的整數值函式。
第4–6章：數論、二項式係數、特殊數
- 二項式係數恆等式：第5章中大量的恆等式，以超幾何函式為統一語言。
- 機械求和：第5.8節用演算法方法判定並證明和式恆等式。
- Stirling 數、調和數與 Bernoulli 數：在求和與漸近分析中反覆出現的特殊數列。
第7–9章：母函式、機率、漸近分析
- 母函式：編碼一個數列的冪級數，用於解遞推和計數。
- 機率母函式：同一工具用於隨機變數。
- O 記號：界定誤差項的記號及第9章的演算規則。
評析
優點
- 目標明確、方法明確。 前言稱目標是讓讀者對離散運算像微積分學生對連續運算那樣熟練，全書始終圍繞演算技巧。
- 習題處於核心位置。 前言列出六類共500多道習題（熱身題、基礎題、作業題、考試題、加分題和研究題），出版社說明除研究題外都附有完整解答，因此適合自學。Allen Stenger 在 MAA Reviews（2010）的書評中稱其為有價值的參考書，充滿有用的結果，尤其在習題中。
- 歷史與出處。 作者追溯思想的源頭，在附錄中註明習題來源，並把 Leibniz、Euler、Gauss 的引文穿插在頁邊。
- 可讀性強的文風。 前言說明，輕鬆的語氣和學生塗鴉是有意的選擇，目的是讓內容更易消化。
侷限
- 範圍有意收窄。 前言指出，本書的主題清單與通常的本科離散數學課程不同；邏輯、圖論和證明方法都不在章節之列。
- 計算要求高。 本書期望讀者手工完成冗長的演算，加分題和研究題超出一般課程中普通學生的承受範圍。
- 第二版的改動有限。 第二版新增第5.8節並作了訂正；正文本身寫於上世紀八九十年代，作者為後來的印次維護勘誤表，其中包括一處涉及 Bernoulli 數定義的更正。
在課程中的定位
在本課程書單中，Concrete Mathematics 是最專注於計算技巧的一本。Levin 的開放教材面向初次接觸數學推理的學生；Epp 的教材在講授電腦科學中的離散結構的同時，教學生如何推理和書寫論證；Rosen 的教材是涵蓋邏輯、證明、計數和圖的綜合課程用書；Lovász、Pelikán 與 Vesztergombi 的小書從謎題和簡單的計數出發，以問題為驅動。其中任何一本都能提供背景，使 Graham、Knuth 和 Patashnik 的書更容易讀。
van Lint 與 Wilson 的 A Course in Combinatorics 是研究生層次的綜合性教材，以許多短章涵蓋圖論、設計、編碼和有限幾何。Graham、Knuth 與 Patashnik 與它互補，因為它集中於求和、遞推、母函式和漸近分析，而不是那些結構。
如何使用本書
前言說，這本書源於斯坦福大學的一門課，修課者是三四年級學生，其中多數是研究生，作者也希望能觸及二年級學生。書中解釋和習題常用到微積分，因此需要熟悉微積分。
- 核心： 先讀第1、2章，然後讀第3章，並在時間允許時儘量多讀第5、7章。母函式（第7章）是書中最能反覆使用的工具。
- 電腦科學方向： 第8、9章，涉及雜湊、機率以及分析演算法所用的 O 記號。
- 選讀： 如果已熟悉數論，第4章可以略讀；第5章的超幾何各節（5.5至5.8）可留到第二遍。
初讀時試做每章的熱身題，認真嘗試之後再看答案，並把作業題當作真正的檢驗。前言明確推薦前兩種做法。