本文選題：平面樹(shù) + Catalan數(shù)��； 參考：《華東師范大學(xué)》2015年碩士論文

【摘要】：平面樹(shù)是組合學(xué)與圖論中的一種常見(jiàn)結(jié)構(gòu).它與Dyck路,Motzkin路及三角剖分等結(jié)構(gòu)聯(lián)系緊密,并且在統(tǒng)計(jì)學(xué)、數(shù)據(jù)結(jié)構(gòu)及生物信息學(xué)等領(lǐng)域有著廣泛應(yīng)用.本文主要研究平面樹(shù)中給定出度或度的點(diǎn)的計(jì)數(shù)問(wèn)題.2001年Deutsch和Shapiro證明了n條邊的平面樹(shù)中所有奇度點(diǎn)個(gè)數(shù)是所有奇出度點(diǎn)個(gè)數(shù)的2倍,并給出了奇出度點(diǎn)個(gè)數(shù)的一個(gè)公式.本文給出了更為細(xì)化的計(jì)數(shù)結(jié)果：在所有n邊平面樹(shù)中,對(duì)任意正整數(shù)i,i度點(diǎn)總數(shù)是i出度點(diǎn)總數(shù)的2倍,i出度點(diǎn)的總數(shù)為(2n-i-1/n-1).對(duì)這一結(jié)論,我們分別給出了生成函數(shù)和構(gòu)造雙射兩種證明.
[Abstract]:Plane tree is a common structure in combinatorial theory and graph theory. It is closely related to Dyck Road Motzkin path and triangulation, and is widely used in statistics, data structure and bioinformatics. In 2001 Deutsch and Shapiro proved that the number of all odd points in a plane tree with n edges is twice as many as the number of all odd outdegree points, and a formula for the number of odd outlier points is given. In this paper, we give a more detailed counting result: in all n-edge plane trees, the total number of positive integer I I degree points is 2 times of the total number of I out degree points, and the total number of I degree points is (2n-i-1/n-1). For this conclusion, we give two kinds of proofs of generating function and constructing bijection, respectively.
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李國(guó)慶,程林鳳;組合問(wèn)題中生成函數(shù)的應(yīng)用[J];彭城職業(yè)大學(xué)學(xué)報(bào);2001年02期

2 邱紅軍;張艷紅;;生成函數(shù)在概率計(jì)算中的應(yīng)用[J];科技信息;2009年34期

3 朱偉義;;冪和序列的生成函數(shù)與冪和新的計(jì)算公式[J];商洛學(xué)院學(xué)報(bào);2009年06期

4 安永紅;張春霞;;生成函數(shù)的若干應(yīng)用[J];呼倫貝爾學(xué)院學(xué)報(bào);2010年03期

5 陳廣軍;;由生成函數(shù)構(gòu)成的梯度投影法[J];運(yùn)籌學(xué)雜志;1987年01期

6 邵學(xué)才，，李東昊，葉秀明;一些特殊圖的生成函數(shù)[J];北京工業(yè)大學(xué)學(xué)報(bào);1996年03期

7 于秀源,周岳;關(guān)于位數(shù)碼列的生成函數(shù)的注記[J];杭州師范學(xué)院學(xué)報(bào);1999年06期

8 于秀源,周岳;關(guān)于位數(shù)碼列的生成函數(shù)的注記[J];杭州師范學(xué)院學(xué)報(bào);1999年06期

9 邱建霞;環(huán)狀限距組合計(jì)數(shù)的一些結(jié)果[J];海南師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2003年04期

10 李中恢;黃小潔;;生成函數(shù)及其應(yīng)用[J];寧波教育學(xué)院學(xué)報(bào);2007年02期

相關(guān)會(huì)議論文 前3條

1 孟昭為;;數(shù)列的生成函數(shù)及其在概率計(jì)算中的應(yīng)用[A];數(shù)學(xué)及其應(yīng)用文集——中南模糊數(shù)學(xué)和系統(tǒng)分會(huì)第三屆年會(huì)論文集（上卷）[C];1995年

2 章忠志;;Random walks in complex networks[A];第六屆全國(guó)網(wǎng)絡(luò)科學(xué)論壇暨第二屆全國(guó)混沌應(yīng)用研討會(huì)論文集[C];2010年

3 亓萬(wàn)鋒;羅鐘鉉;樊鑫;;由任意擴(kuò)張矩陣的Primal逼近型細(xì)分推導(dǎo)的細(xì)分[A];第六屆全國(guó)幾何設(shè)計(jì)與計(jì)算學(xué)術(shù)會(huì)議論文集[C];2013年

相關(guān)博士學(xué)位論文 前7條

1 亓萬(wàn)鋒;基于生成函數(shù)的細(xì)分格式和小波研究[D];大連理工大學(xué);2013年

2 安宗文;基于通用生成函數(shù)的離散化應(yīng)力—強(qiáng)度干涉模型研究[D];電子科技大學(xué);2009年

3 代玉林;上升序列與排列中的有禁模式[D];南開(kāi)大學(xué);2013年

4 樊如冰;分拆鉤和秩的組合研究[D];南開(kāi)大學(xué);2014年

5 張永杰;分拆與匹配中的有禁模式[D];南開(kāi)大學(xué);2009年

6 李淑萍;網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)傳播的影響研究[D];中北大學(xué);2015年

7 魯大前;算子方法在特殊函數(shù)方面的一些應(yīng)用[D];華東師范大學(xué);2011年

相關(guān)碩士學(xué)位論文 前6條

1 邵文凱;狄利克萊級(jí)數(shù)及其生成函數(shù)[D];四川師范大學(xué);2012年

2 員雪莉;平面樹(shù)中給定出度或度的點(diǎn)的計(jì)數(shù)[D];華東師范大學(xué);2015年

3 李雪陽(yáng);變系數(shù)廣義Hamilton系統(tǒng)的生成函數(shù)方法[D];湘潭大學(xué);2010年

4 何佳;K-叉樹(shù)中給定出度的點(diǎn)的計(jì)數(shù)[D];華東師范大學(xué);2015年

5 孫曉敏;三類WZ-方程的一些探討[D];蘇州大學(xué);2012年

6 馮玉銘;海鹽粒子生成函數(shù)及其應(yīng)用[D];中國(guó)海洋大學(xué);2011年

本文編號(hào)：2104219