Abstract:   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. Let [n] = {1, 2,..., n}. 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 a symmetry property and a 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.

  AMS Classification:  05A15, 05A19

  Keywords:   doubly rooted tree, triply rooted tree, bijection

  Download:   pdf