本书从计算机科学的角度，通过讲解各种计算机应用来讨论相关的离散数学基础知识。可作为高等学校计算机相关专业的离散数学课程的双语教材，也可供计算机技术人员学习与参考。

本书由计算机和数学领域的三位教授联合撰写，是为计算机专业量身定制的离散数学教材。针对这门课程的困境——初入学的本科生不理解为何要学习高深的数学，授课教师苦于向毫无编程经验的学生讲授繁杂的算法程序——本书打破了传统的课程顺序和教学方法，明确“为何学”和“有何用”，不仅清晰呈现了计算机专业学生必需的数学知识，而且通过实践和应用启发学生对后续课程的学习兴趣。
主要内容：涵盖计数、密码学与数论、逻辑与证明、归纳法、递归、概率以及图论，推导严谨、代码清晰、练习丰富。
教学模式：提倡参与式教学，鼓励学生加入小组讨论，主动探索，通过提问、讨论和报告来掌握概念，找到解决方案。
课程建议：建议学生掌握微积分的学前课程，了解递归，书中提供了必要的数据结构解释，可作为“算法”的前导课。

作者简介
克利福德·斯坦（Clifford Stein） 著名计算机科学家，名作《算法导论》的作者之一。现为哥伦比亚大学计算机科学系和工业工程与运筹学系教授。
罗伯特 L. 戴斯得尔（Robert L. Drysdale） 达特茅斯学院计算机科学系教授，曾任该系系主任8年，是算法和计算几何学领域的知名学者。
肯尼斯·博加特（Kenneth Bogart） 生前是达特茅斯学院数学系教授，一生致力于数学研究和教学工作，2005年由于自行车事故不幸去世。

课程动机与目标
很多学院与大学都开设了离散数学这门课程。上这些课程的学生来自多个学科，其中最多的是来自计算机科学的学生。由国家科学基金会支持，作为达特茅斯（Dartmouth）学院跨学科数学项目的一部分，我们提出创建一门离散数学课程来直接解决计算机科学学生的需求。计算机科学的学生需要知道哪些离散数学知识？为什么需要知道这些知识？关于这两个问题，我们的看法如下。
第一，我们认为一些知识对于计算机科学很重要，但是传统的离散数学课程常常不会透彻地讲授这些知识。这些知识包括：递归树和解决递推关系的主定理，计算平均运行时间和分析随机算法的概率理论，以及强归纳法和结构归纳法。
第二，我们认为对于计算机科学的学生而言，那些重要的离散数学知识在计算机科学里对应着一些颇有启发性的问题，并且只具备一两门计算机科学入门课程水平的学生也能够理解。这样有可能回答一届又一届学生在应用数学课程中的疑问：“为什么我们必须学习这个？”因此，我们选择写一本针对计算机科学学生的教科书，为他们提供必要的数学基础，并且通过他们在起步阶段就能够理解的计算机科学问题来启发学习兴趣。
在计算机科学系，离散数学通常是学生的专业首选课之一，甚至是第一门计算机科学课程的先修课。在这种情况下，教师面临着两难困境：是讲授纯数学概念，几乎不涉及计算机应用，还是讲授计算机科学的例子，从而营造一种针对计算机科学学生的教学环境。第一种讲课方式让学生们抱怨在学习第一门计算机科学课程之前，被迫学习太多“不相干的”数学。第二种讲课方式让教授们（通常是数学家）尝试给可能从来没有写过程序的学生解释相当高级的计算机科学知识，比如散列、二叉树和循环程序等。即使在最好的情况，这种方法也明显降低了数学的深度。我们的分析产生了一种不同的讲课方式，创设一门出现在学生稍后学习过程中的课程。尽管我们不强制要求学生已经上过微积分，但是我们假定学生了解并且能够熟练使用加和符号、对数和指数函数，因此对于微积分学前课程的内容有很深的了解是很有帮助的。这意味着要让学生在一门计算机科学的导论课程中先了解递归程序，然后再学习这门课。最好可以和数据结构课程一起或者在其之后学习，不过我们会通过例子解释书中所使用的数据结构，因此数据结构不是这门课的先导课程。
我们觉得这样安排离散数学这门课程有几个优势，下面列举几个特别的例子：
学生已经有了较为深入的问题求解、算法和代码的经验。
学生已经学习过或者在准备学习一些重要的计算机科学概念，比如散列、递归、排序、搜索以及基本的数据结构。
学生已经知道足够的计算机科学知识，包括一些启发性的例子，或者其他容易理解的简单例子。例如：
m散列可以用于启发关于概率的学习。
m分析递归程序（比如并归和快速排序）可以用于启发关于递归关系及其解决方法的学习。
m在寻找队列中最小元素的过程中，分析我们期望多久找到一个新的最小值，可以用来启发关于期望的线性性质和调和数的学习。
m二叉树可以用来讲解结构递归法，也可以启发作为图的特例的树的学习。
在我们自己的讲课经验中，这门课是算法课的前导，并且学生经常在结束离散数学课程不久后就学习算法。这样，他们会发现自己可以直接使用刚刚学过的离散数学知识。
我们的教育哲学
这本教科书是以教学活动为驱动的，并且包含丰富的练习题。通过对这些活动的解释和扩展，教学素材得以不断充实。对于学生最有效的方法是尝试认真完成学生活动，而先不阅读那些教学活动后面的解释。我们最初设计这些教学活动是想让学生在课堂中以小组的形式来完成，因此，如果需要在课外开展教学活动，建议学生组建小组一起完成。我们采用这种方式来设计这门课程以及这本教材，希望借此帮助学生们养成自己的数学思维习惯。我们仔细研究了本科学生应当怎样学习数学，得到了以下几个结论：
如果学生能够主动发现他们正在学习的是什么（经常被称为“主动学习”），往往比那些被动学习的学生能够更长久地记住这些概念，也更有可能在学习环境之外运用这些概念。
当学生在一个小组中和同学一起学习，而不是在由导师带领的一个更大的班级中时，他们更有可能提出问题，直到彻底理解某个主题。（然而，这一点不总是成立。很多学生需要在小组中感到舒适之后才敢提出的问题，因为他们担心自己的提问会耽误别人的学习速度。我们尝试提高课程中的舒适度，方法是允许学生自由选择学习小组，并且根据出席模式允许或者要求学生在不同的天数后更换不同的小组。）
最后，学生在给别人解释概念的时候能够更有效地组织自己脑中的想法，同时能够熟悉数学语言。
本书内容足够支撑一门四学期学时的课程。在达特茅斯学院，我们使用这本书来上一门快节奏的课程，一周上三天且仅仅上九周，并且覆盖了本书除了最后几个章节和一部分带星号的内容之外的所有内容。
证明的作用
我们写这本书的目的之一是给学生们提供一些关于证明的背景知识，在以后的计算机科学课程中，他们将需要理解并且写出证明。我们的观点是用听、看、讨论并且尽量多做证明来学习如何做证明。为了方便讨论，我们需要用一种共同的语言来区分证明的组成成分，并且建立起一个讨论的框架。因为这个原因，书中包含一个关于逻辑的章节，即为学生提供这种语言，并帮助他们反思自己已经看到过的证明。为了使这章的内容言之有物，我们将其放在学生了解一些组合和数论的证明之后。这种方法使得学生能够掌握一些用来阐述逻辑证明的具体例子。我们意识到这不是在离散数学书中常用的顺序。然而，我们发现用具体的例子来处理重要事实的证明，可以使学生理解一些实际的基础知识，否则这些证明看起来就像是罗列很长的推理形式规则。
我们已经把关于逻辑的章节放在数学归纳法章节之前，从而可以用逻辑语言来讨论和思考数学归纳法。
数学归纳法
计算机科学的归纳证明经常使用子问题而不是实际问题的精缩版“小问题”。因此，我们强调强归纳法和弱归纳法，我们也介绍树和图的结构归纳法。我们尝试用学生关于递归的经验来帮助他们理解归纳证明，并且设计基于归纳法的证明。特别是，当开始设计归纳证明时，从一个大问题开始并且把它递归分成小问题，比从小问题开始组成大问题更加有利。
伪代码的使用
我们同时使用文字和伪代码描述算法。对于任何使用Java、C或者C++编过程序的人，伪代码很容易读懂，使用其他语言写过程序的人理解起来也不费力。我们不求给出语法上正确的任何一种语言的代码，而是力求代码的清晰。比如“互换变量x和y的值”，我们会写成“交换x和y”，而不是写成三行的代码。类似的，我们写“如果点i、j和k不共线”，而不用担心详细的计算过程如何处理它。这里有一些本书使用的特别约定。
代码区通过缩进来表示，而没有像许多语言一样使用“begin”“end”或者“{　}”。
for循环写成“for i = 1 to n”来标记变量i的取值范围为从1到n。
如果while之后的布尔表达式取值为真，while循环的主体会重复执行。
repeat循环使用格式“repeat…until”。在repeat和unitl之间的代码最少执行一次，并且会重复执行直到在until之后的布尔表达式取值为真。
if语句可以使用以下任意一个格式：
mif（表达式）　代码区
mif（表达式）　代码区1　else　代码区2
在第一种格式中，当且仅当表达式为真时代码区执行。在第二种格式中，如果表达式为真则代码区1执行，如果表达式为假则代码区2执行。
数组的下标使用“[]”。
赋值用“=”，而等式比较用“==”。
x递增和递减的缩写用“x ++”和“x ––”。
逻辑操作符“not”用“！”表示，所以“!true”是“false”，当x不小于y时，
! (x新版中的变化
有一本和本书题目相似且作者相同的书，已由另一家出版社出版，但那家出版社退出了大学教科书市场。Ken Bogart是那本书的主要作者，他在书出版前不久辞世。我们非常怀念他参与准备这本新书的日子。
新版相对于之前版本最明显的更新如下：
上一版书讨论过等价关系，不过只是作为一个集合的划分。等价关系的自反性、对称性和传递性被纳入附录，并且讨论了偏序和全序关系。这本书介绍关系，并且将其作为一个用于关联函数、等价关系、偏序关系和全序关系的概念。书中也解释了为什么自反性、对称性和传递性可以推导出等价关系，而自反性、反对称性和传递性则推导出偏序关系。
本书包含结构归纳法，同时，关于递归和归纳关系的章节已经扩展，并且使用了一些不同的例子。
一些关于递推关系的章节已经被移除或者放在附录中，这些章节证明在递推中去掉下取整和上取整，并将关系的作用域扩展到非同底数幂的数域，主定理仍然有效。我们认为这些内容不利于章节的顺畅，并且需要处理一些大多数学生在这个阶段不需要知道的细节。
在概率一章中增加贝叶斯定理。
增加问题以讲解新的知识主题。
还有一些细小的改变（例如，介绍“乘以x和相减”方法来得到一个几何级数的封闭形式）。
教辅资源
下列教辅资源只针对于符合资格的教师开放。请访问www.pearsonhighered.com/irc或联系当地的Addison-Wesley/Pearson Education销售代表，或者发送邮件到computing@aw.com，以获得关于怎样取得这些资料的信息。本书教辅资源包括：
带有答案的教师参考手册
教学建议
课后作业的答案
课堂练习题
关于如何开展课堂小组练习来活跃讨论的详细资料
幻灯片
致谢
很多人对这本书的最初版做出了贡献。我们要谢谢Eddie Cheng（Oakland University）、Alice Dean（Skidmore College）、Ruth Hass（Smith College）和Italo Dejter（University of Puerto Rico），感谢他们对早期手稿的充满价值的评论。随着本书的不断改进，我们和Neal Young、Pasad Jayanti、Tom Shemanske、Rose Orellana、April Rasala、Amit Chakrabarti以及Carl Pomerance用预备版在达特茅斯学院教授离散数学课程。他们中的每个人都对最后的成品有影响，而且有一些是很大的影响，感谢他们提出的建议。特别感谢Carl Pomerance在他的教学过程中卓有见地和前瞻性的评论。Qun Li是我们开始准备手稿时的研究生助教，正是他使得我们出的所有问题都有了答案！现在提供给教师的答案中，核心部分仍然是他完成的工作。计算机科学系和数学系的其他研究生助教也提供了很大的帮助，在我们教授手稿时，他们了解学生听懂了哪些内容而不明白哪些内容，从而进一步帮助他们解决问题。按照这些助教加入的顺序，他们是S. Agrawal、Elishiva Werner-Reiss、Robert Savell、Virgiliu Pavlu、Libo Song、Geeta Chaudhry、King Tan、Yurong Xu、Gabriella Dumitrascu、Florin Constantin、Alin Popescu和Wei Zhang。我们过去的学生也提供了很有价值的反馈。特别是Eric Robinson读过此书临近出版的版本，并且非常认真地指出了那些难以理解的章节。
我们也要感谢审稿人和出版社的编辑们。以下审稿人提供了很有益的建议：Michael Rothstein（Kent Stat University），Ravi Janardan（University of Minnesota, Twin Cities），Klaus Sutner（Carnegie Mellon University），Doug Baldwin（SUNY Genesco），Stuart Reges（University of Washington），Richard Anderson（University of Washington），Jonathan Goldstine（Penn State University）。Sandra Hakanson是Pearson的销售代表，她首先向Pearson的Addison-Wesley部门推荐此书，并协助我们联系编辑负责人Michael Hirsch。Hirsch同意出版这本书，并且负责整个出版流程，很多改进本书的建议都来源于他。其他对本书的出版做出直接贡献的人有：Stephanie Sellinger（编辑助理），Jeff Holcomb（总编辑），Heather McNally（项目编辑），Elena Sidorova（封面设计）。在Laserwords的Bruce Hobart负责手稿的修改、合并和错误纠正。
每一个作者都想感谢另外两位作者从各自的专业活动上抽出时间花在这本书上，因为的确需要时间来融合不同学科的观点。在国家科学基金会的支持下，我们能够承担这个项目。本科生教学部门的员工在这个项目中展现了他们出色的洞察力，在数学科学的项目构思和整个教学课程的实践中，他们清楚本科生的需求，也了解开展跨学科课程的困难。我们感谢这个项目在本科数学教育和跨学科课程发展中起到的积极作用。

Cliff Stein
Scot Drysdale

计算机\离散数学

【不允许使用原书封面，请重新设计】

本书由计算机和数学领域的三位教授联合撰写，是为计算机专业量身定制的离散数学教材。针对这门课程的困境——初入学的本科生不理解为何要学习高深的数学，授课教师苦于向毫无编程经验的学生讲授繁杂的算法程序——本书打破了传统的课程顺序和教学方法，明确“为何学”和“有何用”，不仅清晰呈现了计算机专业学生必需的数学知识，而且通过实践和应用启发学生对后续课程的学习兴趣。

·主要内容：涵盖计数、密码学与数论、逻辑与证明、归纳法、递归、概率以及图论，推导严谨、代码清晰、练习丰富。
·教学模式：提倡参与式教学，鼓励学生加入小组讨论，主动探索，通过提问、讨论和报告来掌握概念，找到解决方案。
·课程建议：建议学生掌握微积分的学前课程，了解递归，书中提供了必要的数据结构解释，可作为“算法”的前导课。

[美]克利福德·斯坦（Clifford Stein） 罗伯特 L. 戴斯得尔（Robert L. Drysdale） 肯尼斯·博加特（Kenneth Bogart） 著：
【加照片】克利福德·斯坦（Clifford Stein） 著名计算机科学家，名作《算法导论》的作者之一。现为哥伦比亚大学计算机科学系和工业工程与运筹学系教授。 罗伯特 L. 戴斯得尔（Robert L. Drysdale） 达特茅斯学院计算机科学系教授，曾任该系系主任8年，是算法和计算几何学领域的知名学者。 肯尼斯·博加特（Kenneth Bogart） 生前是达特茅斯学院数学系教授，一生致力于数学研究和教学工作，2005年由于自行车事故不幸去世。

Contents

CHAPTER1 Counting　31
1.1 Basic Counting　31
The Sum Principle　31
Abstraction　33
Summing Consecutive Integers　33
The Product Principle　34
Two-Element Subsets　36
Important Concepts, Formulas, and Theorems　37
Problems　38
1.2 Counting Lists, Permutations, and Subsets　40
Using the Sum and Product Principles　40
Lists and Functions　42
The Bijection Principle　44
k-Element Permutations of a Set　45
Counting Subsets of a Set　46
Important Concepts, Formulas, and Theorems　48
Problems　50
1.3 Binomial Coeffiients　52
Pascal’s Triangle　52
A Proof Using the Sum Principle　54
The Binomial Theorem　56
Labeling and Trinomial Coefficient　58
Important Concepts, Formulas, and Theorems　59
Problems　60
1.4 Relations　62
What Is a Relation 　62
Functions as Relations　63
Properties of Relations　63
Equivalence Relations　66
Partial and Total Orders　69
Important Concepts, Formulas, and Theorems　71
Problems　72
1.5 Using Equivalence Relationsin Counting　73
The Symmetry Principle　
Equivalence Relations　75
The Quotient Principle　76
Equivalence Class Counting　76
Multisets　78
The Bookcase Arrangement Problem　80
The Number of k-Element Multisets of an n-Element Set　81
Usingthe Quotient Principle to Explain a Quotient　82
Important Concepts, Formulas, and Theorems　83
Problems　84
CHAPTER2 Cryptography and Number Theory　89
2.1 Cryptography and Modular Arithmetic　89
Introduction to Cryptography　89
Private-Key Cryptography　90
Public-Key Cryptosystems　93
Arithmetic Modulo n　95
Cryptography Using Addition mod n　98
Cryptography Using Multiplication mod n　99
Important Concepts, Formulas, and Theorems　101
Problems 102
2.2 Inverses and Greatest Common Divisors　105
Solutions to Equations and Inverses mod n　105
Inverses mod n　106
Converting Modular Equations to Normal Equations　109
Greatest Common Divisors　110
Euclid’s Division Theorem　111
Euclid’s GCD Algorithm　114
Extended GCD Algorithm　115
Computing Inverses　118
Important Concepts, Formulas, and Theorems　119
Problems　120
2.3 The RSA Cryptosystem　123
Exponentiation mod n　123
The Rules of Exponents　123
Fermat’s Little Theorem　126
The RSA Cryptosystem　127
The Chinese Remainder Theorem　131
Important Concepts, Formulas, and Theorems　132
Problems　134
2.4 Details of the RSA Cryptosystem　136
Practical Aspects of Exponentiation mod n　136
How Long Does It Take to Use the RSA Algorithm 　139
How Hard Is Factoring 　140
Finding Large Primes　140
Important Concepts, Formulas, and Theorems　143
Problems　144
CHAPTER3 Reflectionon Logic and Proof　147
3.1 Equivalence and Implication　147
Equivalence of Statements　147
Truth Tables　150
DeMorgan’s Laws　153
Implication　155
If and Only If　156
Important Concepts, Formulas, and Theorems　159
Problems　161
3.2　Variables and Quantifier　163
Variables and Universes　163
Quantifier　164
Standard Notation for Quantificatio　166
Statements about Variables　168
Rewriting Statements to Encompass Larger Universes　168
Proving Quantifie Statements Trueor False　169
Negation of Quantifie Statements　170
Implicit Quantificatio　173
Proof of Quantifie Statements　174
Important Concepts, Formulas, and Theorems　175
Problems　177
3.3 Inference　179
Direct Inference (Modus Ponens) and Proofs　179
Rules of Inference for Direct Proofs　181
Contrapositive Ruleof Inference　183
Proof by Contradiction　185
Important Concepts, Formulas, and Theorems　188
Problems　189
CHAPTER4 Induction, Recursion, and Recurrences　191
4.1 Mathematical Induction 191
Smallest Counterexamples　191
The Principle of Mathematical Induction　195
Strong Induction　199
Induction in General　201
A Recursive Viewof Induction　203
Structural Induction　206
Important Concepts, Formulas, and Theorems　208
Problems　210
4.2 Recursion, Recurrences, and Induction　213
Recursion　213
Examples of First-Order Linear Recurrences　215
Iteratinga Recurrence　217
Geometric Series　218
First-Order Linear Recurrences　221
Important Concepts, Formulas, and Theorems　225
Problems　227
4.3 Growth Rates of Solutions to Recurrences　228
Divide and Conquer Algorithms　228
Recursion Trees　231
Three Different Behaviors　239
Important Concepts, Formulas, and Theorems　240
Problems　242
4.4 The Master Theorem　244
Master Theorem　244
Solving More General Kinds of Recurrences　247
Extending the Master Theorem　248
Important Concepts, Formulas, and Theorems　250
Problems 251
4.5 More General Kinds of Recurrences　252
Recurrence Inequalities　252
The Master Theorem for Inequalities　253
A Wrinkle with Induction　255
Further Wrinkles in Induction Proofs　257
Dealing with Functions Other Thannc　260
Important Concepts, Formulas, and Theorems　262
Problems 263
4.6 Recurrences and Selection　265
The Idea of Selection　265
A Recursive Selection Algorithm　266
Selection without Knowing the Median in Advance　267
An Algorithm to Find an Element in the Middle Half　269
An Analysis of the Revised Selection Algorithm　272
Uneven Divisions274
Important Concepts, Formulas, and Theorems　276
Problems　277
CHAPTER5 Probability　279
5.1 Introduction to Probability　279
Why Study Probability 　279
Some Examples of Probability Computations　282
Complementary Probabilities　283
Probability and Hashing　284
The Uniform Probability Distribution　286
Important Concepts, Formulas, and Theorems　289
Problems　290
5.2 Unions and Intersections　292
The Probability of a Union of Events　292
Principle of Inclusion and Exclusion for Probability　295
The Principle of Inclusion and Exclusion for Counting　301
Important Concepts, Formulas, and Theorems　303
Problems　304
5.3 Conditional Probability and Independence　306
Conditional Probability　306
Bayes’ Theorem　310
Independence　310
Independent Trials Processes　312
Tree Diagrams　314
Primality Testing　318
Important Concepts, Formulas, and Theorems　319
Problems　320
5.4 Random Variables　322
What Are Random Variables 　322
Binomial Probabilities　323
A Taste of Generating Functions　325
Expected Value　326
Expected Values of Sums and Numerical Multiples　329
Indicator Random Variables　332
The Number of Trialsuntil the First Success　334
Important Concepts, Formulas, and Theorems　336
Problems　337
5.5 Probability Calculations in Hashing　340
Expected Number of Itemsper Location　340
Expected Number of Empty Locations　341
Expected Number of Collisions　342
Expected Maximum Number of Elementsin a Location of a Hash Table　345
Important Concepts, Formulas, and Theorems　350
Problems　351
5.6 Conditional Expectations, Recurrences, and Algorithms　355
When Running Times Depend on More than Sizeof Inputs　355
Conditional Expected Values　357
Randomized Algorithms　359
Selection Revisited　361
QuickSort　363
A More Careful Analysis of RandomSelect　366
Important Concepts, Formulas, and Theorems　369
roblems　370
5.7 Probability Distributions and Variance　373
Distributions of Random Variables　373
Variance　376
Important Concepts, Formulas, and Theorems　384
Problems　385
CHAPTER6 Graphs　389
6.1 Graphs　389
The Degreeofa Vertex　393
Connectivity　395
Cycles　397
Trees　398
Other Properties of Trees　398
Important Concepts, Formulas, and Theorems　401
Problems　403
6.2 Spanning Trees and Rooted Trees　405
Spanning Trees　405
Breadth-First Search　407
Rooted Trees　412
Important Concepts, Formulas, and Theorems 416
Problems　417
6.3 Eulerian and Hamiltonian Graphs　419
Eulerian Tours and Trails　419
Finding Eulerian Tours　424
Hamiltonian Paths and Cycles　425
NP-Complete Problems　431
Proving That Problems Are NP-Complete　433
Important Concepts, Formulas, and Theorems　436
Problems　437
6.4 Matching Theory　440
The Idea of a Matching　440
Making Matchings Bigger　444
Matching in Bipartite Graphs　447
Searching for Augmenting Pathsin Bipartite Graphs　447
The Augmentation-Cover Algorithm　450
Efficien Algorithms　456
Important Concepts, Formulas, and Theorems　457
Problems　458
6.5 Coloring and Planarity　460
The Idea of Coloring　460
Interval Graphs　463
Planarity　465
TheFaces of a Planar Drawing　467
The Five-Color Theorem　471
Important Concepts, Formulas, and Theorems　474
Problems　475
APPENDIX A Derivation of the More General Master Theorem　479
More General Recurrences　479
Recurrences for Generaln　481
Removing Floors and Ceilings　482
Floors and Ceilingsin the Stronger Version of the Master Theorem　483
Proofs of Theorems　483
Important Concepts, Formulas, and Theorems　487
Problems　488
APPENDIX B Answers and Hints to Selected Problems　491
Bibliography　507



目　　录
第1章　计数 31
1.1　基本计数 31
求和原理 31
抽象化 33
连续整数求和 33
乘积原理 34
二元素子集 36
重要概念、公式和定理 37
习题 38
1.2　序列、排列和子集 40
使用求和与乘积原理 40
序列和函数 42
双射原理 44
集合的k元素排列 45
集合子集的计数 46
重要概念、公式和定理 48
习题 50
1.3　二项式系数 52
帕斯卡三角形 52
使用求和原理的一个证明 54
二项式定理 56
标记与三项式系数 58
重要概念、公式和定理 59
习题 60
1.4　关系 62
什么是关系 62
函数作为关系 63
关系的性质 63
等价关系 66
偏序和全序 69
重要概念、公式和定理 71
习题 72
1.5　在计数中运用等价关系 73
对称原理 73
等价关系 75
商原理 76
等价类计数 76
多重集 78
书柜安排问题 80
n元集合的k元多重集的数目 81
使用商原理解释商数 82
重要概念、公式和定理 83
习题 84
第2章　密码学与数论 89
2.1　密码学和模算法 89
密码学导论 89
私钥密码学 90
公钥密码体制 93
模n算术 95
使用模n加法的密码学 98
使用模n乘法的密码学 99
重要概念、公式和定理 101
习题 102
2.2　逆元和最大公因子 105
方程的解和模n的逆元 105
模n的逆元 106
转化模方程为普通方程 109
最大公因子 110
欧几里得除法定理 111
欧几里得最大公因子算法 114
广义最大公因子算法 115
计算逆元 118
重要概念、公式和定理 119
习题 120
2.3　RSA密码体制 123
模n的指数运算 123
指数运算的规则 123
费马小定理 126
RSA密码体制 127
中国剩余定理 131
重要概念、公式和定理 132
习题 134
2.4　RSA加密体制的细节 136
模n指数运算的实用性 136
使用RSA算法会花费多长时间 139
因式分解有多难 140
找大素数 140
重要概念、公式和定理 143
习题 144
第3章　关于逻辑与证明的思考 147
3.1　等价和蕴含 147
语句的等价 147
真值表 150
德摩根律 153
蕴含 155
当且仅当 156
重要概念、公式和定理 159
习题 161
3.2　变元和量词 163
变元和论域 163
量词 164
量词化的标准记号 166
关于变元的语句 168
重写语句以包含更大的论域 168
证明量词语句的真假 169
量词语句的否定 170
隐式量词化 173
量词语句的证明 174
重要概念、公式和定理 175
习题 177
3.3　推理 179
直接推理（演绎推理）和证明 179
直接证明的推理规则 181
推理的逆否（对换）规则 183
反证法 185
重要概念、公式和定理 188
习题 189
第4章　归纳法、递归和递推式 191
4.1　数学归纳法 191
最小反例 191
数学归纳法原理 195
强归纳法 199
归纳法的一般形式 201
从递归视角看归纳法 203
结构归纳法 206
重要概念、公式和定理 208
习题 210
4.2　递归、递推式和归纳法 213
递归 213
一阶线性递推的实例 215
遍历递推式 217
等比数列 218
一阶线性递推式 221
重要概念、公式和定理 225
习题 227
4.3　递推式解的增长率 228
分治算法 228
递归树 231
三种不同的行为 239
重要概念、公式和定理 240
习题 242
4.4　主定理 244
主定理及其证明 244
求解更一般的递推式 247
扩展主定理 248
重要概念、公式和定理 250
习题 251
4.5　更一般的递推式 252
递推不等式 252
不等式主定理 253
归纳法的一个窍门 255
归纳证明的更多窍门 257
处理nc以外的函数 260
重要概念、公式和定理 262
习题 263
4.6　递推式和选择 265
选择的理念 265
一种递归选择算法 266
中位数未知情况下的选择 267
一种从中间一半中查找元素的算法 269
对修改后的选择算法的分析 272
不均匀划分 274
重要概念、公式和定理 276
习题 277
第5章　概率 279
5.1　概率导论 279
为什么要学习概率 279
概率计算举例 282
互补概率 283
概率和散列 284
均匀概率分布 286
重要概念、公式和定理 289
习题 290
5.2　并集和交集 292
并集事件的概率 292
概率的容斥原理 295
计数的容斥原理 301
重要概念、公式和定理 303
习题 304
5.3　条件概率和独立性 306
条件概率 306
贝叶斯法则 310
独立性 310
独立连续过程 312
树形图 314
素数测试 318
重要概念、公式和定理 319
习题 320
5.4　随机变量 322
什么是随机变量 322
二项式概率 323
体验生成函数 325
期望值 326
期望值的加法和数值乘法 329
指示器随机变量 332
第一次成功的尝试次数 334
重要概念、公式和定理 336
习题 337
5.5　散列中的概率计算 340
每个位置元素的期望个数 340
空位置的期望个数 341
冲突的期望个数 342
元素在哈希表一个位置的最大期望个数 345
重要概念、公式和定理 350
习题 351
5.6　条件期望、递归和算法 355
什么时候运算时间不止取决于输入的大小 355
条件期望值 357
随机算法 359
重温选择算法 361
快速排序 363
更详细的随机选取的分析 366
重要概念、公式和定理 369
习题 370
5.7　概率分布和方差 373
随机变量的分布 373
方差 376
重要概念、公式和定理 384
习题 385
第6章　图论 389
6.1　图 389
顶点的度 393
连通性 395
环 397
树 398
树的其他性质 398
重要概念、公式和定理 401
习题 403
6.2　生成树和有根树 405
生成树 405
宽度优先搜索 407
有根树 412
重要概念、公式和定理 416
习题 417
6.3　欧拉图和哈密顿图 419
欧拉回路与路径 419
寻找欧拉回路 424
哈密顿路径和环 425
P完全问题 431
证明问题是NP完全的 433
重要概念、公式和定理 436
习题 437
6.4　匹配定理 440
匹配的概念 440
让匹配更大 444
二部图的匹配 447
二部图增广道路的搜索 447
增广覆盖算法 450
高效的算法 456
重要概念、公式和定理 457
习题 458
6.5　染色和平面性 460
染色的概念 460
区间图 463
平面性 465
平面化的面 467
五色定理 471
重要概念、公式和定理 474
习题 475
附录A　更一般的主定理的推导 479
更一般的递推式 479
对一般n的递推式 481
去掉下取整和上取整 482
更强版本主定理中的下取整和上取整 483
定理的证明 483
重要概念、公式和定理 487
习题 488
附录B　节选习题答案与提示 491
参考文献 507