Decomposition of Triply Rooted Trees

  • William Y.C. Chen
  • Janet F.F. Peng
  • Harold R.L. Yang
Keywords: doubly rooted tree, triply rooted tree, bijection


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.
Article Number