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）可留到第二遍。
初读时试做每章的热身题，认真尝试之后再看答案，并把作业题当作真正的检验。前言明确推荐前两种做法。