置换表、似树表、连接分拆的组合性质及其B类结构的推广研究

Enumerative Combinatorics is a principal research field in Combinatorics and constructing combinatorial transformations is one of its central research methods. This method shows certain complicated problems simply and profoundly. The main objects of this project are permutation tableaux, tree-like tableaux and linked partitions. These new combinatorial structures are introduced recently, and being concerned by including Professor W.Y.C. Chen and Professor R.P. Stanley et al. Nowadays, they have become a hot research topic in Enumerative Combinatorics. In this project, we shall utilize the close relationship among these three structures to deal with the combinatorial properties of permutation tableaux of both type A and type B, and the distributions of their statistics, such as the distributions of 0’s and 1’s in permutation tableaux and sign-imbalance formula, etc., which are all the frontier subjects. Moreover, we shall solve the symmetry of q-Eulerian polynomial of type B and the enumeration of crossings, nestings and alignments in linked partitions of type B. The research on these problems will open up new research ideas and methods for the research in the future, and develop the theoretical achievements in Enumerative Combinatorics.

计数组合学是组合数学领域的一个主要且重要的研究方向。构建组合变换是该方向的核心的研究方法之一。对于某些复杂的组合问题，它往往可以给出简洁而深刻的证明。本项目将主要利用构建组合变换的方法解决组合结构中重要统计量的计数和分布问题。本项目的主要研究对象是置换表、似树表和连接分拆。这三种组合结构均是在近些年才被首次提出的，受到中国科学院院士陈永川教授、美国科学院院士Stanley教授等多位知名学者的关注和研究，是当前计数组合学中的研究热点。项目组将利用这三种新型组合结构之间的紧密联系，解决置换表中0、1的计数分布、符号失衡公式等有关A类和B类置换表的组合性质及其统计量的分布特征等前沿课题，还将利用置换表的结构特征证明B类q-Eulerian多项式的对称性问题，探讨B类连接分拆中交叉、嵌套、队列的分布等问题。对上述问题的研究将为后续研究开辟新的研究思路和方法，丰富和完善计数组合学的理论成果。

在此项目的支持下，项目组成员主要完成了对连接分拆、排列、置换表等组合模型在结构特性和计数特征等方面的研究。首先，将连通非交叉连接分拆定义为波浪连接分拆、构建其波浪分解，并在此分解的基础上建立了一种标号原则，并利用排列中的连续下降子列清晰地构造出波浪连接分拆与首位为1的312有禁排列之间的双射，从而证明前者中一类特殊点“D类结点”的标号之和恰好等于对应的排列的主指标，从而为排列中的主指标提出了一种全新的图形表示。其次，项目组成员还得到一般的连接分拆中的单覆盖最小元和连通分支与排列的圈结构之间一一对应关系。其次，项目负责人指导下，多位研究生在多类格路径及其赋权形式的计数特征和结构特性上挖掘出诸多结果。综上，项目完成顺利，基本符合预期目标。