解析组合学 (2009) [pdf]

- 《Analytic Combinatorics》（解析组合学）是法国计算机科学家 Philippe Flajolet 与 Robert Sedgewick 合著的经典教科书（2009年出版），可免费下载。Flajolet（1948–2011）是法国国家信息与自动化研究所（INRIA）的杰出研究员，组合数学与算法分析领域的泰斗。 - 这本书的核心思想是：用复分析（微积分中的一项高阶工具）来精确研究组合结构的计数问题——简单说，就是“数东西”并搞清楚那些数字增长的规律。传统上用生成函数做组合计数，Flajolet 则把生成函数视为复平面上的解析函数，利用奇点分析来得到渐近结果。 - 该书首创了“符号法”（symbolic method）的系统框架：用少量语法构造（如序列、集合、循环）就能描述大量组合对象（树、排列、字符串、映射……），然后自动翻译成生成函数方程，再通过解析工具求解。 - 这一方法广泛应用于算法平均复杂度分析、生物信息学、统计物理、网络科学等领域。对技术读者来说，它是连接“离散数学”与“连续数学”的一座桥梁，理论深度极高，但实践中用于推导算法性能界非常高效。