版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、樹(shù)是組合數(shù)學(xué)中一類(lèi)經(jīng)典的組合結(jié)構(gòu),現(xiàn)在依然是組合數(shù)學(xué)中一個(gè)活躍的領(lǐng)域。樹(shù)結(jié)構(gòu)在不同領(lǐng)域都有著廣泛的應(yīng)用,例如組合數(shù)學(xué)、計(jì)算機(jī)科學(xué)、計(jì)算生物學(xué)以及數(shù)學(xué)物理等。從圖論的角度,一棵樹(shù)可以被定義為一幅無(wú)圈連通圖。本論文借助一些經(jīng)典的組合工具來(lái)研究幾類(lèi)樹(shù)上的統(tǒng)計(jì)量,并刻畫(huà)了樹(shù)和其它組合結(jié)構(gòu)的聯(lián)系。首先,利用有根樹(shù)這一結(jié)構(gòu),我們給出了Lacasse在研究機(jī)器學(xué)習(xí)中的PCA-Bayes理論時(shí)提出的一個(gè)猜想的組合證明。其次,我們引入k-優(yōu)勝樹(shù)的概念,并
2、給出了其與k-Stirling排列的雙射。這一雙射解決了Janson,Kuba和Panholzer提出的關(guān)于組合證明k-Stiring排列以及k-平面遞增樹(shù)的等價(jià)性的公開(kāi)問(wèn)題。此外,我們定義了標(biāo)記平面遞增樹(shù),并給出了這一結(jié)構(gòu)和逐級(jí)約化樹(shù)等價(jià)的兩個(gè)證明:文法證明和雙射證明。最后,我們定義了一類(lèi)增廣文法,并利用其研究了一些有禁結(jié)構(gòu)的性質(zhì)。
本論文結(jié)構(gòu)如下。第一章給出了基本的定義及相關(guān)符號(hào)。我們首先介紹樹(shù)的相關(guān)定義,包括不同類(lèi)的樹(shù)的
3、定義以及樹(shù)上一些經(jīng)典的統(tǒng)計(jì)量的定義。接下來(lái),我們簡(jiǎn)單介紹了兩類(lèi)和樹(shù)有密切聯(lián)系的組合結(jié)構(gòu),分別是n-映射和排列。在本章的最后,我們簡(jiǎn)要地回顧了上下文無(wú)關(guān)文法理論。該理論是一種利用形式計(jì)算來(lái)研究組合結(jié)構(gòu)的方法,由陳永川于1993年首先提出。
在第二章中,我們利用樹(shù)的“合并”操作給出了雙根標(biāo)號(hào)樹(shù)三元組和三根標(biāo)號(hào)樹(shù)的一一對(duì)應(yīng),從而給出了Lacasse提出的猜想的組合證明。接下來(lái),我們構(gòu)造了增廣n-映射到三根標(biāo)號(hào)樹(shù)的一一對(duì)應(yīng),這給出了C
4、ayley公式的一個(gè)加細(xì)。另外,這一雙射反映了一些統(tǒng)計(jì)量的同分布性質(zhì)。具體而言,雙射將增廣n-映射中n+1的軌道對(duì)應(yīng)到了三根標(biāo)號(hào)樹(shù)的第二個(gè)根的祖先,而將增廣n-映射中的周期點(diǎn)對(duì)應(yīng)到三根標(biāo)號(hào)樹(shù)的第三個(gè)根的祖先?;谶@一性質(zhì),我們得到了增廣n-映射中周期點(diǎn)和軌道長(zhǎng)度的一個(gè)對(duì)稱(chēng)性質(zhì)。本章的結(jié)尾給出了具有i個(gè)周期點(diǎn)且其中n+1的軌道長(zhǎng)度為j的增廣n-映射的計(jì)數(shù)公式。
在第三章中,我們引入k-優(yōu)勝樹(shù)。這一定義可以看作k-平面遞增樹(shù)的一個(gè)
5、具體化。陳永川和付梅定義了k-Stirling文法,用于生成k-Stirling排列的下降位生成函數(shù)。我們加細(xì)這一文法,使其同時(shí)也可以記錄k-Stirling排列的上升位和平衡位。我們證明這一文法同樣可以用于生成k-優(yōu)勝樹(shù)。這一事實(shí)表明了k-Stirling排列以及k-優(yōu)勝樹(shù)的等價(jià)性。接下來(lái)我們給出了k-Stirling排列和k-優(yōu)勝樹(shù)的一個(gè)直接的雙射。這一雙射解決了Janson,Kuba和Panholzer提出的公開(kāi)問(wèn)題。
6、第四章引入了標(biāo)記平面遞增樹(shù)。我們證明標(biāo)記平面遞增樹(shù)和逐級(jí)約化樹(shù)可以由同一個(gè)上下文無(wú)關(guān)文法來(lái)生成,我們稱(chēng)之為“Schr(o)der文法”。借助Schr(o)der文法,我們證明了具有n個(gè)葉子點(diǎn)和k個(gè)內(nèi)點(diǎn)的逐級(jí)約化樹(shù)的個(gè)數(shù)等于具有n個(gè)點(diǎn),其中有k個(gè)無(wú)標(biāo)記的非根點(diǎn)的標(biāo)記平面遞增樹(shù)的個(gè)數(shù)。接下來(lái),我們考慮樹(shù)上的一對(duì)操作:收縮與分裂,并據(jù)此構(gòu)造出了標(biāo)記平面遞增樹(shù)和逐級(jí)約化樹(shù)的雙射。這一雙射給出了上述同分布性質(zhì)的組合證明。特別地,此雙射的一個(gè)特殊情
7、形給出了二叉全劃分樹(shù)和平面遞增樹(shù)的一個(gè)一一對(duì)應(yīng)。
第五章引入了增廣文法的定義。對(duì)于上下文無(wú)關(guān)文法G,我們記(G)為G的增廣文法。我們研究了(G)和G的關(guān)系,并發(fā)現(xiàn)(G)可用于生成某些有禁結(jié)構(gòu),例如:錯(cuò)排可以視為不含穩(wěn)定點(diǎn)的排列。然后,我們將這一思路應(yīng)用于Eulerian文法,據(jù)此得到0-1-2遞增樹(shù)和“圈交錯(cuò)”型排列的一些有趣的性質(zhì)。通過(guò)計(jì)算,我們發(fā)現(xiàn)擁有n+1個(gè)頂點(diǎn)且不含有1度極小標(biāo)號(hào)點(diǎn)的0-1-2遞增樹(shù)的個(gè)數(shù)等于[n]的“
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 有限Coxeter群上統(tǒng)計(jì)量的研究.pdf
- 樹(shù)結(jié)構(gòu)綜述
- 基于XML樹(shù)結(jié)構(gòu)的索引技術(shù)研究.pdf
- 樹(shù)結(jié)構(gòu)圖模型的研究與應(yīng)用.pdf
- 低電壓時(shí)鐘樹(shù)結(jié)構(gòu)的研究與實(shí)現(xiàn).pdf
- Gnutella網(wǎng)絡(luò)中樹(shù)結(jié)構(gòu)搜索機(jī)制的研究.pdf
- 樹(shù)結(jié)構(gòu)習(xí)題及答案
- 基于樹(shù)結(jié)構(gòu)的精簡(jiǎn)序列模式挖掘算法研究.pdf
- 基于樹(shù)結(jié)構(gòu)的人臉屬性識(shí)別.pdf
- 基于樹(shù)結(jié)構(gòu)的應(yīng)用層組播模型研究.pdf
- 基于樹(shù)結(jié)構(gòu)模型的多類(lèi)識(shí)別算法研究.pdf
- 設(shè)計(jì)出樹(shù)結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)
- 基于二叉樹(shù)結(jié)構(gòu)的漢語(yǔ)韻律邊界研究.pdf
- 統(tǒng)計(jì)流形上的等仿射結(jié)構(gòu).pdf
- 基于樹(shù)結(jié)構(gòu)的生物數(shù)據(jù)挖掘算法的研究與實(shí)現(xiàn).pdf
- 合肥市行道樹(shù)結(jié)構(gòu)及功能研究.pdf
- 樹(shù)結(jié)構(gòu)在程序設(shè)計(jì)中的運(yùn)用
- 基于偏轉(zhuǎn)角的樹(shù)結(jié)構(gòu)數(shù)據(jù)融合路由算法.pdf
- 基于四叉樹(shù)結(jié)構(gòu)的HEVC快速幀內(nèi)算法研究.pdf
- 充分統(tǒng)計(jì)量
評(píng)論
0/150
提交評(píng)論