期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：1990
卷号：87
期号：24
页码：9635-9639
DOI：10.1073/pnas.87.24.9635
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：Trees are combinatorial structures that arise naturally in diverse applications. They occur in branching decision structures, taxonomy, computer languages, combinatiorial optimization, parsing of sentences, and cluster expansions of statistical mechanics. Intuitively, a tree is a collection of branches connected at nodes. Formally, it can be defined as a connected graph without cycles. Schroder trees, introduced in this paper, are a class of trees for which the set of subtrees at any vertex is endowed with the structure of ordered partitions. An ordered partition is a partition of a set in which the blocks are linearly ordered. Labeled rooted trees and labeled planed trees are both special classes of Schroder trees. The main result gives a bijection between Schroder trees and forests of small trees--namely, rooted trees of height one. Using this bijection, it is easy to encode a Schroder tree by a sequence of integers. Several classical algorithms for trees, including a combinatorial proof of the Lagrange inversion formula, are immediate consequences of this bijection.
