Séminaire Lotharingien de Combinatoire, B57a (2007), 14 pp.
Markus Kuba and Stephan Wagner
Perfect Matchings and k-Decomposability of Increasing Trees
Abstract.
A tree is called k-decomposable if it has a spanning forest whose
components are all of size k. In this paper, we study the number of
k-decomposable trees in families of increasing trees, i.e. labeled
trees in which the unique path from the root to an arbitrary vertex
forms an increasing sequence. Functional equations for the
corresponding counting series are provided, yielding asymptotic or
even exact formulas for the proportion of k-decomposable trees. In
particular, the case k=2 (trees with a perfect matching) and the
case of recursive trees are treated. For two cases, bijections to
alternating permutations and permutations with only odd-length cycles can be
given, thus providing alternative proofs for the respective counting
formulas. Furthermore, it turns out that k-decomposable recursive
trees become more numerous as k grows to infinity, a behavior that
has also been observed for simply generated families of trees.
Received: December 14, 2006.
Accepted: July 20, 2007.
Final Version: August 15, 2007.
The following versions are available: