An insertion algorithm and leaders of rooted trees. (April 2016) - Hou, Qing-Hu
Abstract: The notion of leaders of labeled rooted trees was introduced by Seo. A vertex in a labeled rooted tree is called a leader if it has no smaller descendants. We present an algorithm which leads to a bijection between labeled rooted trees and integer sequences a 1 ⋯ a n − 1 with a i ∈ { 1, 2, …, n } such that the number of leaders is exactly one more than the number of anti-excedances, namely, the positions i for which a i ≤ i . Our bijection gives a refinement of an identity of Gessel and Seo which takes the degree of 2 into account. By taking the reverse complement of a sequence, we obtain a combinatorial interpretation of a symmetry property on the enumeration of forests by the number of leaders and the number of components. This question was raised by Gessel and Seo. Applying a theorem of Lyapunov, we show that the distribution of the number of leaders of a random rooted tree is asymptotically normal.