Decomposition of Triply Rooted Trees

Abstract

In this paper, we give a decomposition of triply rooted trees into three doubly rooted trees. This leads to a combinatorial interpretation of an identity conjectured by Lacasse in the study of the PAC-Bayesian machine learning theory, and proved by Younsi by using the Hurwitz identity on multivariate Abel polynomials. We also give a bijection between the set of functions from [n+1] to [n] and the set of triply rooted trees on [n], which leads to the refined enumeration of functions from [n+1] to [n] with respect to the number of elements in the orbit of n+1 and the number of periodic points.