Discrete Mathematics: Elementary and Beyond（离散数学：从初等到深入）

引用

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章之前先做完章末习题。
• 与系统性教材搭配。 如果课程考查逻辑、关系或递推，就搭配一本系统性教材，而把本书用于加深对其所涵盖主题的理解和学习动机。