Applied Analytic Combinatorics

组合结构作为物理现象的离散数学模型越来越多地被发现潜伏在数学和其他科学的界面上，特别是物理学、生物学和计算机科学。结构的简单性是具有欺骗性的，因为它们往往足够丰富，在我们理解所研究的潜在现象方面发挥了关键作用。解析组合学是一个迅速发展的理论领域，它利用复分析和代数来研究组合族及其性质。这个理论的一个中心特征是它的算法和通用性。

Combinatorial structures arising as discrete mathematical models of physical phenomena are increasingly found lurking at the interface of mathematics and other sciences, particularly physics, biology and computer science. The simplicity of the structures is deceptive, as they are often sufficiently rich to play a key role in our understanding of the underlying phenomena being studied. Analytic combinatorics is a rapidly advancing area of theory which studies combinatorial families and their properties using complex analysis and algebra. A central feature of this theory is its algorithmic and generic nature. This research program considers several problems in the domain of statistical mechanics, genomics and theoretical computer science, and to each addresses questions well adapted to analytic combinatorics: solvability; enumeration and parameter distribution; and random generation. Three applications act as conduits of study: (I) lattice path enumeration; (II) tree models of permutations; and (III) RNA secondary structures. The questions take the form of "Do we expect a particular polymer to have this shape?" "What is a typical evolution scenario between two mammals and their common ancestor?" and "How often should this folding structure occur in an RNA strand of this length?". Ideally, we then compare results to actual data in order to gauge the quality of the model. Random generation allows us to form and test hypotheses, to determine the practical complexity of related algorithms, and to assess the quality of the data. The results for each application inform a larger study of combinatorial structures:we are interested in the meta classification of combinatorial classes by some notion of complexity. This augments the classical Chomsky Hierarchy of formal languages.