《具体数学》第二版全书导览

按9章把递归、离散求和、数论、组合数、生成函数、概率和渐近分析连成算法数学工具链。

先做预测

先预测索引平移、初值改变、参数取边界或n增大时，精确值与近似值如何变化。按9章把递归、离散求和、数论、组合数、生成函数、概率和渐近分析连成算法数学工具链。 本页用、、、和建立对象、变换、证书与误差闭环。

第二版权威目录定位

本页一一对应Graham、Knuth和Patashnik《Concrete Mathematics》第二版“《具体数学》第二版全书导览”。出版社目录给出9个正式章节；作者官网确认1994年第二版、ISBN与657页，并说明新增机械求和内容。

原书小节覆盖

  1. 第1章 Recurrent Problems
  2. 第2章 Sums
  3. 第3章 Integer Functions
  4. 第4章 Number Theory
  5. 第5章 Binomial Coefficients
  6. 第6章 Special Numbers
  7. 第7章 Generating Functions
  8. 第8章 Discrete Probability
  9. 第9章 Asymptotics
  10. 附录A：500余道练习的答案

核心对象

  1. 递归到闭式：从小规模关系出发，经求和、生成函数或特征方法得到可计算表达。
  2. 离散连续类比：差分对应导数，求和对应积分，二项式基对应幂函数基。
  3. 组合恒等式：通过双重计数、生成函数和机械证书连接符号与对象。
  4. 概率与算法：指示变量、PGF和哈希案例把离散结构转为平均行为。
  5. 渐近验收：主导项必须携带误差项、适用范围和精确小样例。

先固定离散契约

公式前先写索引集合、初值、参数范围和边界约定。递推、取整、组合数和渐近式最常见的错误不是代数，而是少一项、从错误下标开始或在不合法参数上继续使用恒等式。

P=(index domain,initial values,parameters,boundary convention)\mathcal P=(\text{index domain},\text{initial values},\text{parameters},\text{boundary convention})

精确问题应先枚举最小规模：空集合、n为零、第一非平凡值和正好落在边界的值。小例子不能替代理论，但能尽早暴露符号和约定不一致。

可核查推导

recurrence→sum→integer structure→generating function→asymptotics\text{recurrence}\to\text{sum}\to\text{integer structure}\to\text{generating function}\to\text{asymptotics}

递推描述局部变化，求和积累变化，整数与数论控制离散边界，组合数与生成函数提供代数变换，概率和渐近法最终回答规模增长与平均行为。 每次换元都同步改上下界，每次交换求和都说明有限性或收敛条件，每次从精确式转为渐近式都保留余项。

official_chapters=list(range(1,10))
assert len(official_chapters)==9
site_pages=1+len(official_chapters)+1
assert site_pages==11

代码与手算必须在至少五个连续规模上相符。只测一个点可能让两个不同序列偶然相等；还应加入边界和随机小规模穷举。

对象与变换链

递归到闭式：从小规模关系出发，经求和、生成函数或特征方法得到可计算表达。

离散连续类比：差分对应导数，求和对应积分，二项式基对应幂函数基。

组合恒等式：通过双重计数、生成函数和机械证书连接符号与对象。

具体数学的核心是把离散对象在多种表示间切换：递推转求和，求和转差分，组合对象转生成函数，概率计数转指示变量，精确式转带余项的渐近式。每一步都要能逆向检查。

边界、反例与误差

概率与算法：指示变量、PGF和哈希案例把离散结构转为平均行为。

渐近验收：主导项必须携带误差项、适用范围和精确小样例。

边界集至少包括空和、空积、零规模、负参数、参数恰在端点、取模负数、重复根、发散级数和小n渐近失真。失败应明确指出哪个前提不成立。

e(n)=exact(n)−approx(n),∣e(n)∣≤B(n)e(n)=\text{exact}(n)-\text{approx}(n),\qquad |e(n)|\le B(n) 
audit={"exact":"enumerate small n","boundary":"zero and endpoint","counterexample":"只背公式，未记录索引域、初值和变量趋向。","certificate":"replay transformations"}
assert set(audit)=={"exact","boundary","counterexample","certificate"}

算法案例

用同一个哈希与递归分析笔记贯穿全书：精确计数、取整边界、组合恒等式、PGF和渐近误差都保留可复算样例。 报告保存精确输入、索引域、中间恒等式、机械证书或组合解释、程序输出与误差界，保证他人能从头重算。

evidence=[("递归到闭式","definition"),("组合恒等式","derivation"),("渐近验收","certificate")]
assert len({name for name,_ in evidence})==3
  1. 写出索引域、初值和空对象约定，手算最小非平凡样例。
  2. 一次只做一种变换，保存边界项和前后等价关系。
  3. 删除一个假设构造反例，解释首个失败步骤。
  4. 对近似结论计算残差与误差界，并标明何时进入渐近区间。

验收证书

accept⁡=exact examples∧derivation∧counterexample∧error budget\operatorname{accept}=\text{exact examples}\land\text{derivation}\land\text{counterexample}\land\text{error budget}

证书拒绝孤立闭式。它应包含问题对象、精确关系、推导步骤、初值、机械或组合证据、小规模重放、反例和误差预算。

常见误区

本章回顾

本章覆盖递归到闭式、离散连续类比、组合恒等式、概率与算法、渐近验收。掌握标准是能从对象建立精确式，逐步变换并保留边界，给出可重放证书，再说明近似误差和反例。

术语表

讨论

评论区加载中…