解析组合学
这门课学什么
课程讲如何用符号方法把组合结构写成生成函数，再用复分析求出系数的精确渐近估计。8 个单元从普通生成函数讲到奇点分析和鞍点法。
内容摘要
这门课讲解析组合学：一套把组合结构的计数问题转成生成函数、再从生成函数读出精确渐近估计的方法。它回答这类问题：长度为 N 的某类字符串、树或排列大约有多少个，某个参数的平均值是多少。课程对应弗拉若莱（Philippe Flajolet）和塞奇威克合著的《解析组合学》（Analytic Combinatorics）。
全课 8 讲，分 2 个阶段。第 1 阶段是第 1–3 讲，讲符号方法（symbolic method）：用序列、集合、多重集等构造规则描述组合类，直接写出普通生成函数（OGF）、指数生成函数（EGF）和标记参数的多元生成函数。第 2 阶段是第 4–8 讲，讲复渐近：把生成函数看作复变函数，依次用有理函数与亚纯函数方法、奇点分析和鞍点法求系数的渐近式。
每讲配 1 组课后习题和 1 个测验，部分讲次有讨论题。没有编程作业。习题从教材中选出，要求学生自己推导生成函数和渐近式。
学完以后，学生能为常见的组合结构写出生成函数，能判断用哪种复分析方法求渐近，并能把结果用到算法分析、随机结构和统计物理问题上。课程默认学生已学过 Analysis of Algorithms 或具备同等基础，还要懂复变函数。
塞奇威克的讲法偏系统化：每讲先给出一般定理，再用一串经典例子验证，最后总结成可以套用的“模式”（schema）。课程难度高，适合研究生或有扎实数学基础的学习者。
为什么值得学
讲师是该领域权威教材《解析组合学》的作者之一。整本教材在配套网站免费下载。
课程信息
- 学校
- 普林斯顿（Princeton）
- 讲师
- 罗伯特·塞奇威克（Robert Sedgewick）
- 学期
- self-paced
- 平台
- Coursera
- 费用
- 免费
- 难度
- 高级
- 学时
- 8 个单元 × 每单元 2–3 小时
- 先修
- 需要微积分和复变函数基础，建议先学 Analysis of Algorithms。
- 材料
- 视频、幻灯片、教材
- 许可证
- 未注明
课程大纲 · 共 8 节
大纲依据：Coursera 模块列表（8 讲，每讲一个模块；结构取自 api.coursera.org onDemandCourseMaterials.v2 与课程页）（查看原始页面 ↗）
- 1组合结构与普通生成函数Combinatorial Structures and OGFs
先讲学科简史，再讲符号方法：用构造规则描述树、字符串、幂集、多重集、组合与划分，并直接得到普通生成函数。
- 2有标号结构与指数生成函数Labelled Structures and EGFs
把符号方法推广到原子可区分的有标号对象，讲单词、有标号树和映射的指数生成函数。
- 3组合参数与多元生成函数Combinatorial Parameters and MGFs
用额外变量标记参数，得到多元生成函数，并用它计算参数的均值和方差。
- 4复分析与有理、亚纯渐近Complex Analysis, Rational and Meromorphic Asymptotics
把生成函数看作复函数，讲解析函数和复积分，并给出有理函数和亚纯函数系数的渐近转移定理。
- 5有理与亚纯渐近的应用Applications of Rational and Meromorphic Asymptotics
把上一讲的定理用到位串和受限组合，并讲超临界序列模式这一普遍规律。
- 6奇点分析Singularity Analysis
讲 Flajolet-Odlyzko 定理：在主奇点附近用标准函数尺度做近似，再转移到系数的渐近式。
- 7奇点分析的应用Applications of Singularity Analysis
把奇点分析用到简单树族、有标号集合、映射和类树结构，得到一批普遍规律。
- 8鞍点渐近Saddle Point Asymptotics
讲模曲面和鞍点界，用鞍点法处理没有奇点的生成函数，最后总结全课。
普林斯顿的其他经典课
- 算法（上） · Algorithms, Part I
- 算法（下） · Algorithms, Part II
- 计算机科学：有目的的编程 · Computer Science: Programming with a Purpose
- 计算机科学：算法、理论与机器 · Computer Science: Algorithms, Theory, and Machines
- 算法分析 · Analysis of Algorithms
- 比特币与加密货币技术 · Bitcoin and Cryptocurrency Technologies