论文部分内容阅读
有根树具有非线性结构,在组合数学中占有重要的地位。有序树是一类特殊的有根树,其节点的子树具有序关系。格路与有根树有着紧密的联系,利用格路语言,本文给出了一些等式的组合证明。Chen,Deutsch和Elizalde把有序树上的叶子分类为右叶子和非右叶子,构造了有序树和2-Motzkin路之间的双射。Coker在研究MultipleDyck路时,给出了两个关于Narayana多项式和Catalan数的组合恒等式,它们的组合证明是Coker提出的公开问题。我们利用Chen-Deutsch-Elizalde双射,通过2-Motzkin路上的权值变换,给出了Coker等式的组合解释。Eu,Liu和Yeh利用生成函数的方法研究了有序树上叶子个数的奇偶性问题,得到了一个关于Narayana数和Catalan数的关系式,给出了这个关系式的部分组合解释。本文描述了此关系式的三种不同的组合证明。
在庆祝R.P.Stanley教授60岁生日的学术会议上,Postnikov给出了一个关于二叉树hooklength的组合等式,并要求给出其组合证明。本文给出了Postnikov等式的一个简单递归证明。Seo通过引进标号树上正常点的概念构造了一个双射,给出了Postnikov等式的组合证明,该双射由三个双射复合而成,进一步Seo导出了一些关于k叉树,有序森林hooklength的组合等式,他的证明引进了标号树上正常点的概念。本文利用Lambert-Rothe等式,给出了一个统一的方法来证明Seo公式和几个Postnikov类型的等式。
Meir和Moon定义简单生成类(simply-generatedfamily)为一类节点赋权的有序树。本文考虑了一类特殊的简单生成类,我们称之为二项式树(binomialtrees),其权值是一些二项式系数。二项式树包括了有序树和k叉树。特别地,标号无序树是二项式树的极限形式。本文主要研究了简单生成类上的四个统计量:叶子,非右叶子,正常边和正常点,运用Darboux定理得到了其期望μi(n)和方差的渐进结果,这里n是树的节点数;进一步证明对于任何一个常数0≤c≤1,都存在一个简单生成类,当n趋近于无穷时,μi(n)/n趋近于c(对于正常边而言,0≤c≤1/2)。对于二项式树,我们给出了四个统计量的期望值的精确公式。根据Lyapunov条件,本文证明二项式树的正常点的分布接近于正态分布。
本文的结构如下:第一章介绍关于各种有根树的定义和计数公式,给出一些Abel等式的组合证明,引进简单生成类的概念,二项式树的定义和例子;第二章研究了叶子和非右叶子统计量,得到了一些关于其分布的结果,进一步,根据有序树和2-Motzkin路的双射,给出Coker等式和叶子奇偶性等式的组合证明;第三章利用Lambert-Rothe等式研究Postnikov等式和Seo公式;第四章讨论了正常边和正常点统计量,得到了关于其分布的结果。