Applied Analytic Combinatorics

组合结构作为物理现象的离散数学模型，越来越多地被发现潜伏在数学和其他科学，特别是物理、生物学和计算机科学的交界处。这些结构的简单是具有欺骗性的，因为它们往往足够丰富，在我们对正在研究的潜在现象的理解中发挥关键作用。分析组合学是一个迅速发展的理论领域，它利用复分析和代数来研究组合族及其性质。这一理论的一个核心特征是它的算法性质和一般性质。 这项研究计划考虑了统计力学、基因组学和理论计算机科学领域中的几个问题，每个问题都很适合分析组合学：可解性；枚举和参数分布；以及随机生成。有三个应用作为研究的渠道：(I)晶格路径枚举；(Ii)排列的树模型；以及(Iii)RNA二级结构。 这些问题的形式是“我们期望一种特定的聚合物具有这种形状吗？”“两种哺乳动物及其共同祖先之间的典型进化场景是什么？”以及“在这种长度的RNA链中，这种折叠结构应该多久出现一次？”理想情况下，我们会将结果与实际数据进行比较，以衡量模型的质量。随机生成允许我们形成和测试假设，确定相关算法的实际复杂性，并评估数据的质量。 每个应用的结果都为更大的组合结构研究提供了信息：我们对组合类的元分类感兴趣，这些元分类是通过一些复杂性概念来实现的。这增加了形式语言的经典乔姆斯基等级制度。

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.