賦權(quán)樹上的組合及漸近結(jié)果.pdf

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

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

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

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

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