论文部分内容阅读
组合结构是研究组合数学的基础,在组合计数领域中占有重要的地位。格路径和平面树是应用最为广泛的两种组合结构,并且两者之间存在着非常紧密的联系。本文主要研究了几类格路径以及平面树的计数问题。
首先我们给出了Shapiro,Woan和Getru利用Riordan排列的方法研究的一个关于Catalan数和序列(1,4,4<2>,4<3>….)的矩阵等式的组合证明。通过构造带有一条提升线的赋权局部Motzkin路与自由Motzkin路之间的双射,我们得到了一类关于赋权Motzkin路和k≥2的序列(1,k,k<2>,k<3>,….)的矩阵等式。进一步,利用染色的Dyck路,我们给出了一类关于序列(1,t<2>+t,(t<2>+t)<2>,…)的矩阵等式。
其次我们研究了平面树的计数问题,提出了双根树的概念并给出了这类树的Butterfly分解算法,且通过这种分解算法建立了双根树与自由Dyck路之间的双射。由这个双射可以很自然的导出一个关于Catalan数和二项式系数的关系式。作为这个算法的又一个应用,我们还构造了叶子染色的双根树和自由Schroder路之问的双射,而且给出了经典的Chung-Feller定理及其多种推广形式的组合证明,同时得到了两个关于Dyck路和Schroder路的对合,并进一步导出了一系列的奇偶性结果和组合恒等式。应用Butterfly分解算法,我们还给出了Klazar关于平面树上链条的生成函数的组合解释,进而揭示了n条边的平面树上链条的平均长度趋进于n+9/6。最后我们利用对于标号平面树的Chen算法,给出了一个关于平面森林的双射,由此解释了一类关于Narayana数的组合恒等式。
2002年,Alex Postnikov提出了一个关于多面体体积的Chan—Robbins-Yeun猜想的约简规则的公开问题,并要求给出其组合证明。在Postnikov给出的用Catalan数计数的二叉树的约简规则基础上,我们定义了新的单项式上的约简规则,并通过建立双射的方法证明了这些约简规则与许多种类的平面树相关,其中包括完全对称k叉树、局部对称k叉树、对称偶树、对称不交树、Motzkin树以及带圈的平面树。在证明过程中,我们归纳地使用了一种消除算法来对单项式上的约简规则的终项进行计数。同时我们还得到了包括3-Catalan数和Motzkin数在内的许多计数性质。
在本文的最后我们定义了一种新的组合结构--2-二叉树:根节点染黑色而其他节点染黑色或白色的有根二叉树。我们研究了许多类2-二二叉树并给出了它们与多种组合结构之间的双射关系,其中包括三叉树、不交树、Schroder路、Motzkin路以及Dyck路。同时我们得到了很多统计量的计数结果。