第1章 计数

1.1 基本计数

求和原理

抽象化

连续整数求和

乘积原理

二元素子集

重要概念、公式和定理

习题

1.2 序列、排列和子集

使用求和与乘积原理

序列和函数

双射原理

集合的k元素排列

集合子集的计数

重要概念、公式和定理

习题

1.3 二项式系数

帕斯卡三角形

使用求和原理的一个证明

二项式定理

标记与三项式系数

重要概念、公式和定理

习题

1.4 关系

什么是关系

函数作为关系

关系的性质

等价关系

偏序和全序

重要概念、公式和定理

习题

1.5 在计数中运用等价关系

对称原理

等价关系

商原理

等价类计数

多重集

书柜安排问题

n元集合的k元多重集的数目

使用商原理解释商数

重要概念、公式和定理

习题

第2章 密码学与数论

2.1 密码学和模算法

密码学导论

私钥密码学

公钥密码体制

模n算术

使用模n加法的密码学

使用模n乘法的密码学

重要概念、公式和定理

习题

2.2 逆元和最大公因子

方程的解和模n的逆元

模n的逆元

转化模方程为普通方程

最大公因子

欧几里得除法定理

欧几里得最大公因子算法

广义最大公因子算法

计算逆元

重要概念、公式和定理

习题

2.3 RSA密码体制

模n的指数运算

指数运算的规则

费马小定理

RSA密码体制

中国剩余定理

重要概念、公式和定理

习题

2.4 RSA加密体制的细节

模n指数运算的实用性

使用RSA算法会花费多长时间

因式分解有多难

找大素数

重要概念、公式和定理

习题

第3章 关于逻辑与证明的思考

3.1 等价和蕴含

语句的等价

真值表

德摩根律

蕴含

当且仅当

重要概念、公式和定理

习题

3.2 变元和量词

变元和论域

量词

量词化的标准记号

关于变元的语句

重写语句以包含更大的论域

证明量词语句的真假

量词语句的否定

隐式量词化

量词语句的证明

重要概念、公式和定理

习题

3.3 推理

直接推理（演绎推理）和证明

直接证明的推理规则

推理的逆否（对换）规则

反证法

重要概念、公式和定理

习题

第4章 归纳法、递归和递推式

4.1 数学归纳法

最小反例

数学归纳法原理

强归纳法

归纳法的一般形式

从递归视角看归纳法

结构归纳法

重要概念、公式和定理

习题

4.2 递归、递推式和归纳法

递归

一阶线性递推的实例

遍历递推式

等比数列

一阶线性递推式

重要概念、公式和定理

习题

4.3 递推式解的增长率

分治算法

递归树

三种不同的行为

重要概念、公式和定理

习题

4.4 主定理

主定理及其证明

求解更一般的递推式

扩展主定理

重要概念、公式和定理

习题

4.5 更一般的递推式

递推不等式

不等式主定理

归纳法的一个窍门

归纳证明的更多窍门

处理nc以外的函数

重要概念、公式和定理

习题

4.6 递推式和选择

选择的理念

一种递归选择算法

中位数未知情况下的选择

一种从中间一半中查找元素的算法

对修改后的选择算法的分析

不均匀划分

重要概念、公式和定理

习题

第5章 概率

5.1 概率导论

为什么要学习概率

概率计算举例

互补概率

概率和散列

均匀概率分布

重要概念、公式和定理

习题

5.2 并集和交集

并集事件的概率

概率的容斥原理

计数的容斥原理

重要概念、公式和定理

习题

5.3 条件概率和独立性

条件概率

贝叶斯法则

独立性

独立连续过程

树形图

素数测试

重要概念、公式和定理

习题

5.4 随机变量

什么是随机变量

二项式概率

体验生成函数

期望值

期望值的加法和数值乘法

指示器随机变量

第一次成功的尝试次数

重要概念、公式和定理

习题

5.5 散列中的概率计算

每个位置元素的期望个数

空位置的期望个数

冲突的期望个数

元素在哈希表一个位置的最大期望个数

重要概念、公式和定理

习题

5.6 条件期望、递归和算法

什么时候运算时间不止取决于输入的大小

条件期望值

随机算法

重温选择算法

快速排序

更详细的随机选取的分析

重要概念、公式和定理

习题

5.7 概率分布和方差

随机变量的分布

方差

重要概念、公式和定理

习题

第6章 图论

6.1 图

顶点的度

连通性

环

树

树的其他性质

重要概念、公式和定理

习题

6.2 生成树和有根树

生成树

宽度优先搜索

有根树

重要概念、公式和定理

习题

6.3 欧拉图和哈密顿图

欧拉回路与路径

寻找欧拉回路

哈密顿路径和环

P完全问题

证明问题是NP完全的

重要概念、公式和定理

习题

6.4 匹配定理

匹配的概念

让匹配更大

二部图的匹配

二部图增广道路的搜索

增广覆盖算法

高效的算法

重要概念、公式和定理

习题

6.5 染色和平面性

染色的概念

区间图

平面性

平面化的面

五色定理

重要概念、公式和定理

习题

附录A 更一般的主定理的推导

更一般的递推式

对一般n的递推式

去掉下取整和上取整

更强版本主定理中的下取整和上取整

定理的证明

重要概念、公式和定理

习题

附录B 节选习题答案与提示

参考文献