第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