...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The butterfly decomposition of plane trees
【24h】

The butterfly decomposition of plane trees

机译：梧桐树的蝴蝶分解

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We introduce the notion of doubly rooted plane trees and give a decomposition of these trees, called the butterfly decomposition, which turns out to have many applications. From the butterfly decomposition we obtain a one-to-one correspondence between doubly rooted plane trees and free Dyck paths, which implies a simple derivation of a relation between the Catalan numbers and the central binomial coefficients. We also establish a one-to-one correspondence between leaf-colored doubly rooted plane trees and free Schroder paths. The classical Chung-Feller theorem as well as some generalizations and variations follow quickly from the butterfly decomposition. We next obtain two involutions on free Dyck paths and free Schroder paths, leading to parity results and combinatorial identities. We also use the butterfly decomposition to give a combinatorial treatment of Klazar's generating function for the number of chains in plane trees. Finally we study the total size of chains in plane trees with n edges and show that the average size of such chains tends asymptotically to (n + 9)/6. (C) 2007 Elsevier B.V. All rights reserved.
机译：我们介绍了双根平面树的概念，并给出了这些树的分解，称为蝴蝶分解，结果证明它具有许多应用。从蝴蝶分解中，我们获得了双根平面树与自由Dyck路径之间的一一对应关系，这意味着加泰罗尼亚数与中心二项式系数之间关系的简单推导。我们还建立了叶色双根平面树与自由Schroder路径之间的一对一对应关系。蝴蝶分解迅速地遵循了经典的Chung-Feller定理以及一些概括和变化。接下来，我们在自由的Dyck路径和自由的Schroder路径上获得两次对合，从而导致奇偶校验结果和组合身份。我们还使用蝴蝶分解对平面树中链数的克拉扎尔生成函数进行组合处理。最后，我们研究了具有n条边的平面树中链的总大小，并显示出这种链的平均大小渐近趋于（n + 9）/ 6。 （C）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号