A recursive algorithm for trees and forests

详细信息    查看全文

• 作者：Song Guo ^{guosong77@hytc.edu.cn} ; Victor J.W. Guo ; ^{jwguo@hytc.edu.cn}
• 关键词：Forests ; Rooted trees ; Bipartite trees ; Tripartite trees ; Plane trees ; kk-edge colored trees
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：340
• 期：4
• 页码：695-703
• 全文大小：449 K
• 卷排序：340

文摘

Trees or rooted trees have been generously studied in the literature. A forest is a set of trees or rooted trees. Here we give recurrence relations between the number of some kind of rooted forest with kk roots and that with k+1k+1 roots on {1,2,…,n}{1,2,…,n}. Classical formulas for counting various trees such as rooted trees, bipartite trees, tripartite trees, plane trees, kk-ary plane trees, kk-edge colored trees follow immediately from our recursive relations.