组合结构中的变换及其相关问题的研究

组合变换是研究组合数学的核心方法之一，对于某些复杂的组合问题其往往可以给出简洁而深刻的证明。本项目旨在研究组合变换在三类问题中的应用：交叉嵌套问题、等式的组合证明、序列的代数性质。.在天元基金支持下，我们已经对交叉嵌套问题进行了初步研究，得到了一些很好的结果。本项目将在此基础上，进一步研究交叉嵌套的对称联合分布与给定交叉嵌套数的组合结构计数两方面的内容。.在先期的工作中我们已经对Pfaff型与Dyson型组合等式的结构进行了系统研究。在此基础上我们将从组合结构入手重点研究这两类等式的q模拟与其它相关组合等式。.序列代数性质是近年来受到广泛关注的前沿课题，我们与南开大学陈永川教授等人合作给出了Boros-Moll系数序列正性、递归关系和对数凹性的组合证明。本项目将继续利用组合结构来探讨其它组合序列的代数性质，并通过构造适当的组合变换给出其组合解释。

组合变换是研究组合数学的核心方法之一，对于某些复杂的组合问题其往往可以给出简洁而深刻的证明。本项目主要研究了组合变换在三类问题中的应用：交叉嵌套问题、等式的组合证明、序列的代数性质。具体来说，我们的研究成果主要集中在下述几个方面：. 1）将经典的计数组合学理论应用于不交树，我们首先给出了限定左、右叶子数的不交树的计数。事实上，平面树中的一些经典对合可以拓展应用于不交树中。依据此思路，我们组合解释了不交树中左叶子数与非根正则顶点数是对称联合分布的。另外，我们构建了不交树的右叶子与不交森林之间的双射。. 2）与陈永川院士合作，构造了部分双染色排列这一组合模型。将Boros-Moll多项式系数对应到赋权的部分双染色排列中，Boros-Moll多项式系数被赋予了组合意义，进而，Boros-Moll多项式系数所满足的一个递归关系得到了解释。同样，该组合意义也可以应用在解释Boros-Moll多项式系数的对数凹性质中。. 3）对于标号树，陈永川院士曾经给出经典的“分解树”算法。我们发现这一算法可以加以推广，将之应用于不交树中。通过构造标号不交树的分解与融合算法，我们对不交树中有关统计量的计数公式给予了组合解释。进一步的，通过构造双射，解决了Hough在《The Electronic Journal of Combinatorics》杂志上提出的一个公开问题。. 4）链划分与左度不超过1的简单图有密切的关系，而不交链划分的计数是大Schroder数。通过细化染色Motzkin路，我们构造了不交链划分和一类Motzkin路的一个双射，给出了大Schroder数和小Schroder数关系的一个简单解释。. 5）作为Stirling数和Lah数递归关系的推广，我们研究了一个更一般的二阶递归关系。利用赋权的组合结构和对称函数理论，我们从组合角度解释了该递归关系的解。. 6）利用两类Stirling数的组合意义，我们组合证明了Hsu提出的含有二项式系数与两类Stirling数的若干等式。