上下文无关文法在排列统计量研究中的应用

The statistics on permutations become a research focus in enumerative combinatorics in recent decades. In this project, context-free grammar, a powerful tool for calculation in combinatorics, is used to study the following two aspects of permutations: one is Eulerian-Mahonian joint statistics, and the other is pattern avoidance for permutations. In 2012, J. Haglund posed an open problem to find a stable multivariate refinement of the generating function of some pair of Eulerian-Mahonian statistics. This project will construct a grammar which can generate permutations with sorting index and descent number. By giving a refinement of this grammar, we will obtain a multivariate stable refinement of the generating function of sorting index and descent number to give an answer to Haglund’s problem. Furthermore, while Wilf equivalence of patterns with length three or four has been fully determined, the situations of the patterns with length more than four are more complicated and less studied. In this project wo aim to give a grammatical description of permutation patterns. By using the grammatical description, the property of permutations avoiding general patterns will be characterized. Finally, we will construct a framwork of context-free frammars and find a method to calculate the generating function of a general context-free grammar automatically.

近几十年，排列的统计量一直是计数组合学的研究热点。本项目运用组合数学中的重要研究工具——上下文无关文法来研究排列统计量研究中的两个重要内容：Eulerian-Mahonian联合统计量和有禁排列。2012年，J. Haglund提出公开问题，希望能找到某一对Eulerian-Mahonian联合统计量生成函数的稳定细化。通过构造相关的文法，本项目将研究“排序指标——下降位”这一对联合统计量的分布；进而通过构造细化文法来得到“排序指标——下降位”多元生成函数q-模拟的多元稳定细化，解决Haglund提出的公开问题。此外，目前对于有禁排列的研究主要是针对有长度为3或者4的，对于一般长度模式下有禁排列的研究结果并不多。本项目将上下文无关文法理论运用到有禁排列的研究，通过给定禁模式的文法表示，研究长度大于4的有禁排列的性质。最后，本项目将构建一套完整的陈氏文法生成函数的自动计算方法。