解析组合数学

课程概况

解析组合学这门课将教会大家精确定量预测大型组合结构的性质。这门课将介绍符号法，用以推导普通、指数和多元生成函数之间的函数关系；这门课还将介绍复分析中的方法，用于从GF方程推导准确渐近性。

解析组合学基于推导生成函数关系的形式方法和将这些函数处理为复平面内函数的渐进分析。这门课涵盖了立刻从组合结构中定义生成函数符号法，然后发展出方法，直接从这些生成函数中推导渐近结果，过程中会用到复渐近、奇异分析、鞍点渐近、和极限定律。课程将教你如下概念：“只要你能具体说明它，你就能够分析它。”

Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.

All the features of this course are available for free. It does not offer a certificate upon completion.

课程大纲

第一讲：组合结构和OGF
Our first lecture is about the symbolic method, where we define combinatorial constructions that we can use to define classes of combinatorial objects. The constructions are integrated with transfer theorems that lead to equations that define generating functions whose coefficients enumerate the classes. We consider numerous examples from classical combinatorics.

第二讲：带标号结构和EGF
This lecture introduces labelled objects, where the atoms that we use to build objects are distinguishable. We use exponential generating functions EGFs to study combinatorial classes built from labelled objects. As in Lecture 1, we define combinatorial constructions that lead to EGF equations, and consider numerous examples from classical combinatorics.

第三讲：组合参数和MGF
This lecture describes the process of adding variables to mark parameters and then using the constructions form Lectures 1 and 2 and natural extensions of the transfer theorems to define multivariate GFs that contain information about parameters. We concentrate on bivariate generating functions (BGFs), where one variable marks the size of an object and the other marks the value of a parameter. After studying ways of computing the mean, standard deviation and other moments from BGFs, we consider several examples in some detail.

第四讲：复分析、有理和亚纯渐近
This week we introduce the idea of viewing generating functions as analytic objects, which leads us to asymptotic estimates of coefficients. The approach is most fruitful when we consider GFs as complex functions, so we introduce and apply basic concepts in complex analysis. We start from basic principles, so prior knowledge of complex analysis is not required.

第五讲：有理和亚纯渐近应用
We consider applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes that we encountered in Lectures 1 and 2. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction.

第六讲：生成函数的奇异分析
This lecture addresses the basic Flajolet-Odlyzko theorem, where we find the domain of analyticity of the function near its dominant singularity,
approximate using functions from standard scale, and then transfer to coefficient asymptotics term-by-term.

第七讲：奇异分析的应用
We see how the Flajolet-Odlyzko approach leads to universal laws covering combinatorial classes built with the set, multiset, and recursive
sequence constructions. Then we consider applications to many of the classic combinatorial classes that we encountered in Lectures 1 and 2.

第八讲：鞍点渐近
We consider the saddle point method, a general technique for contour integration that also provides an effective path to the development of coefficient asymptotics for GFs with no singularities. As usual, we consider the application of this method to several of the classic problems introduced in Lectures 1 and 2.