On an Identity for the Cycle Indices of Rooted Tree Automorphism Groups

Abstract

This note deals with a formula due to G. Labelle for the summed cycle indices of all rooted trees, which resembles the well-known formula for the cycle index of the symmetric group in some way. An elementary proof is provided as well as some immediate corollaries and applications, in particular a new application to the enumeration of $k$-decomposable trees. A tree is called $k$-decomposable in this context if it has a spanning forest whose components are all of size $k$.