Decomposition of Triply Rooted Trees
William Y.C. Chen, Janet F.F. Peng and Harold R.L. Yang
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 |