Perfect Matchings and k-Decomposability of Increasing Trees

Markus Kuba ; Stephan Wagner

Séminaire lotharingien de combinatoire, Tome 57 (2007-2010)

Résumé

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.