賦權樹上的組合及漸近結果.pdf

1、有根樹具有非線性結構，在組合數(shù)學中占有重要的地位。有序樹是一類特殊的有根樹，其節(jié)點的子樹具有序關系。格路與有根樹有著緊密的聯(lián)系，利用格路語言，本文給出了一些等式的組合證明。Chen，Deutsch和Elizalde把有序樹上的葉子分類為右葉子和非右葉子，構造了有序樹和2-Motzkin路之間的雙射。Coker在研究MultipleDyck路時，給出了兩個關于Narayana多項式和Catalan數(shù)的組合恒等式，它們的組合證明是Coker

2、提出的公開問題。我們利用Chen-Deutsch-Elizalde雙射，通過2-Motzkin路上的權值變換，給出了Coker等式的組合解釋。Eu，Liu和Yeh利用生成函數(shù)的方法研究了有序樹上葉子個數(shù)的奇偶性問題，得到了一個關于Narayana數(shù)和Catalan數(shù)的關系式，給出了這個關系式的部分組合解釋。本文描述了此關系式的三種不同的組合證明。 在慶祝R.P.Stanley教授60歲生日的學術會議上，Postnikov給出了一

3、個關于二叉樹hooklength的組合等式，并要求給出其組合證明。本文給出了Postnikov等式的一個簡單遞歸證明。Seo通過引進標號樹上正常點的概念構造了一個雙射，給出了Postnikov等式的組合證明，該雙射由三個雙射復合而成，進一步Seo導出了一些關于k叉樹，有序森林hooklength的組合等式，他的證明引進了標號樹上正常點的概念。本文利用Lambert-Rothe等式，給出了一個統(tǒng)一的方法來證明Seo公式和幾個Postnik

4、ov類型的等式。 Meir和Moon定義簡單生成類(simply-generatedfamily)為一類節(jié)點賦權的有序樹。本文考慮了一類特殊的簡單生成類，我們稱之為二項式樹(binomialtrees)，其權值是一些二項式系數(shù)。二項式樹包括了有序樹和k叉樹。特別地，標號無序樹是二項式樹的極限形式。本文主要研究了簡單生成類上的四個統(tǒng)計量：葉子，非右葉子，正常邊和正常點，運用Darboux定理得到了其期望μi(n)和方差的漸進結果，

5、這里n是樹的節(jié)點數(shù)；進一步證明對于任何一個常數(shù)0≤c≤1，都存在一個簡單生成類，當n趨近于無窮時，μi(n)/n趨近于c(對于正常邊而言，0≤c≤1/2)。對于二項式樹，我們給出了四個統(tǒng)計量的期望值的精確公式。根據Lyapunov條件，本文證明二項式樹的正常點的分布接近于正態(tài)分布。 本文的結構如下：第一章介紹關于各種有根樹的定義和計數(shù)公式，給出一些Abel等式的組合證明，引進簡單生成類的概念，二項式樹的定義和例子；第二章研究了葉