On the enumeration of tanglegrams and tangled chains

详细信息    查看全文

• 作者：Sara C. Billey^a ; ; Matjaž Konvalinka^b ; ^{matjaz.konvalinka@fmf.uni-lj.si" class="auth_mail" title="E-mail the corresponding author} ; ; Frederick A. Matsen IV^c ;
• 关键词：Tanglegrams ; Enumeration ; Binary trees ; Binary partitions
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：146
• 期：Complete
• 页码：239-263
• 全文大小：485 K

文摘

Tanglegrams are a class of graphs arising in computer science and in biological research on cospeciation and coevolution. They are formed by identifying the leaves of two rooted binary trees. We give an explicit formula to count the number of distinct binary rooted tanglegrams with n matched leaves, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This includes a new formula for the number of binary trees with n leaves. We also give a conjecture for the expected number of cherries in a large randomly chosen binary tree and an extension of this conjecture to other types of trees.