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.

10 pages, 5 figures

References in corpus (1)

• Proof of a Combinatorial Conjecture Coming from the PAC-Bayesian Machine Learning Theory

Cited by in corpus (1)

• An identity conjectured by Lacasse via the tree function