幾類樹結(jié)構(gòu)上統(tǒng)計量的研究.pdf

1、樹是組合數(shù)學(xué)中一類經(jīng)典的組合結(jié)構(gòu)，現(xiàn)在依然是組合數(shù)學(xué)中一個活躍的領(lǐng)域。樹結(jié)構(gòu)在不同領(lǐng)域都有著廣泛的應(yīng)用，例如組合數(shù)學(xué)、計算機科學(xué)、計算生物學(xué)以及數(shù)學(xué)物理等。從圖論的角度，一棵樹可以被定義為一幅無圈連通圖。本論文借助一些經(jīng)典的組合工具來研究幾類樹上的統(tǒng)計量，并刻畫了樹和其它組合結(jié)構(gòu)的聯(lián)系。首先，利用有根樹這一結(jié)構(gòu)，我們給出了Lacasse在研究機器學(xué)習(xí)中的PCA-Bayes理論時提出的一個猜想的組合證明。其次，我們引入k-優(yōu)勝樹的概念，并

2、給出了其與k-Stirling排列的雙射。這一雙射解決了Janson,Kuba和Panholzer提出的關(guān)于組合證明k-Stiring排列以及k-平面遞增樹的等價性的公開問題。此外，我們定義了標(biāo)記平面遞增樹，并給出了這一結(jié)構(gòu)和逐級約化樹等價的兩個證明:文法證明和雙射證明。最后，我們定義了一類增廣文法，并利用其研究了一些有禁結(jié)構(gòu)的性質(zhì)。
　　本論文結(jié)構(gòu)如下。第一章給出了基本的定義及相關(guān)符號。我們首先介紹樹的相關(guān)定義，包括不同類的樹的

3、定義以及樹上一些經(jīng)典的統(tǒng)計量的定義。接下來，我們簡單介紹了兩類和樹有密切聯(lián)系的組合結(jié)構(gòu)，分別是n-映射和排列。在本章的最后，我們簡要地回顧了上下文無關(guān)文法理論。該理論是一種利用形式計算來研究組合結(jié)構(gòu)的方法，由陳永川于1993年首先提出。
　　在第二章中，我們利用樹的“合并”操作給出了雙根標(biāo)號樹三元組和三根標(biāo)號樹的一一對應(yīng)，從而給出了Lacasse提出的猜想的組合證明。接下來，我們構(gòu)造了增廣n-映射到三根標(biāo)號樹的一一對應(yīng)，這給出了C

4、ayley公式的一個加細(xì)。另外，這一雙射反映了一些統(tǒng)計量的同分布性質(zhì)。具體而言，雙射將增廣n-映射中n+1的軌道對應(yīng)到了三根標(biāo)號樹的第二個根的祖先，而將增廣n-映射中的周期點對應(yīng)到三根標(biāo)號樹的第三個根的祖先。基于這一性質(zhì)，我們得到了增廣n-映射中周期點和軌道長度的一個對稱性質(zhì)。本章的結(jié)尾給出了具有i個周期點且其中n+1的軌道長度為j的增廣n-映射的計數(shù)公式。
　　在第三章中，我們引入k-優(yōu)勝樹。這一定義可以看作k-平面遞增樹的一個

5、具體化。陳永川和付梅定義了k-Stirling文法，用于生成k-Stirling排列的下降位生成函數(shù)。我們加細(xì)這一文法，使其同時也可以記錄k-Stirling排列的上升位和平衡位。我們證明這一文法同樣可以用于生成k-優(yōu)勝樹。這一事實表明了k-Stirling排列以及k-優(yōu)勝樹的等價性。接下來我們給出了k-Stirling排列和k-優(yōu)勝樹的一個直接的雙射。這一雙射解決了Janson，Kuba和Panholzer提出的公開問題。
　　

6、第四章引入了標(biāo)記平面遞增樹。我們證明標(biāo)記平面遞增樹和逐級約化樹可以由同一個上下文無關(guān)文法來生成，我們稱之為“Schr(o)der文法”。借助Schr(o)der文法，我們證明了具有n個葉子點和k個內(nèi)點的逐級約化樹的個數(shù)等于具有n個點，其中有k個無標(biāo)記的非根點的標(biāo)記平面遞增樹的個數(shù)。接下來，我們考慮樹上的一對操作:收縮與分裂，并據(jù)此構(gòu)造出了標(biāo)記平面遞增樹和逐級約化樹的雙射。這一雙射給出了上述同分布性質(zhì)的組合證明。特別地，此雙射的一個特殊情

7、形給出了二叉全劃分樹和平面遞增樹的一個一一對應(yīng)。
　　第五章引入了增廣文法的定義。對于上下文無關(guān)文法G,我們記(G)為G的增廣文法。我們研究了(G)和G的關(guān)系，并發(fā)現(xiàn)(G)可用于生成某些有禁結(jié)構(gòu)，例如:錯排可以視為不含穩(wěn)定點的排列。然后，我們將這一思路應(yīng)用于Eulerian文法，據(jù)此得到0-1-2遞增樹和“圈交錯”型排列的一些有趣的性質(zhì)。通過計算，我們發(fā)現(xiàn)擁有n+1個頂點且不含有1度極小標(biāo)號點的0-1-2遞增樹的個數(shù)等于[n]的“