平面树中给定出度或度的点的计数

发布时间：2018-07-07 07:18

  本文选题：平面树 + Catalan数　； 参考：《华东师范大学》2015年硕士论文

【摘要】：平面树是组合学与图论中的一种常见结构.它与Dyck路,Motzkin路及三角剖分等结构联系紧密,并且在统计学、数据结构及生物信息学等领域有着广泛应用.本文主要研究平面树中给定出度或度的点的计数问题.2001年Deutsch和Shapiro证明了n条边的平面树中所有奇度点个数是所有奇出度点个数的2倍,并给出了奇出度点个数的一个公式.本文给出了更为细化的计数结果：在所有n边平面树中,对任意正整数i,i度点总数是i出度点总数的2倍,i出度点的总数为(2n-i-1/n-1).对这一结论,我们分别给出了生成函数和构造双射两种证明.
[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.
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157

【相似文献】

相关期刊论文 前10条

1 李国庆,程林凤;组合问题中生成函数的应用[J];彭城职业大学学报;2001年02期

2 邱红军;张艳红;;生成函数在概率计算中的应用[J];科技信息;2009年34期

3 朱伟义;;幂和序列的生成函数与幂和新的计算公式[J];商洛学院学报;2009年06期

4 安永红;张春霞;;生成函数的若干应用[J];呼伦贝尔学院学报;2010年03期

5 陈广军;;由生成函数构成的梯度投影法[J];运筹学杂志;1987年01期

6 邵学才，，李东昊，叶秀明;一些特殊图的生成函数[J];北京工业大学学报;1996年03期

7 于秀源,周岳;关于位数码列的生成函数的注记[J];杭州师范学院学报;1999年06期

8 于秀源,周岳;关于位数码列的生成函数的注记[J];杭州师范学院学报;1999年06期

9 邱建霞;环状限距组合计数的一些结果[J];海南师范学院学报(自然科学版);2003年04期

10 李中恢;黄小洁;;生成函数及其应用[J];宁波教育学院学报;2007年02期

相关会议论文 前3条

1 孟昭为;;数列的生成函数及其在概率计算中的应用[A];数学及其应用文集——中南模糊数学和系统分会第三届年会论文集（上卷）[C];1995年

2 章忠志;;Random walks in complex networks[A];第六届全国网络科学论坛暨第二届全国混沌应用研讨会论文集[C];2010年

3 亓万锋;罗钟铉;樊鑫;;由任意扩张矩阵的Primal逼近型细分推导的细分[A];第六届全国几何设计与计算学术会议论文集[C];2013年

相关博士学位论文 前7条

1 亓万锋;基于生成函数的细分格式和小波研究[D];大连理工大学;2013年

2 安宗文;基于通用生成函数的离散化应力—强度干涉模型研究[D];电子科技大学;2009年

3 代玉林;上升序列与排列中的有禁模式[D];南开大学;2013年

4 樊如冰;分拆钩和秩的组合研究[D];南开大学;2014年

5 张永杰;分拆与匹配中的有禁模式[D];南开大学;2009年

6 李淑萍;网络拓扑结构对传播的影响研究[D];中北大学;2015年

7 鲁大前;算子方法在特殊函数方面的一些应用[D];华东师范大学;2011年

相关硕士学位论文 前6条

1 邵文凯;狄利克莱级数及其生成函数[D];四川师范大学;2012年

2 员雪莉;平面树中给定出度或度的点的计数[D];华东师范大学;2015年

3 李雪阳;变系数广义Hamilton系统的生成函数方法[D];湘潭大学;2010年

4 何佳;K-叉树中给定出度的点的计数[D];华东师范大学;2015年

5 孙晓敏;三类WZ-方程的一些探讨[D];苏州大学;2012年

6 冯玉铭;海盐粒子生成函数及其应用[D];中国海洋大学;2011年

本文编号：2104219