A tree is called $k$-decomposable if it has a spanning forest whose components are all of size $k$. Analogously, a tree is called $T$-decomposable for a fixed tree $T$ if it has a spanning forest whose components are all isomorphic to $T$. In this paper, we use a generating functions approach to derive exact and asymptotic results on the number of $k$-decomposable and $T$-decomposable trees from a so-called simply generated family of trees - we find that there is a surprisingly simple functional equation for the counting series of $k$-decomposable trees. In particular, we will study the limit case when $k$ goes to $\infty$. It turns out that the ratio of $k$-decomposable trees increases when $k$ becomes large.
Discrete Mathematics & Theoretical Computer Science