An insertion algorithm and leaders of rooted trees. (April 2016)

• Record Type: Journal Article
• Authors: Hou, Qing-Hu
• Is Part Of: European journal of combinatorics. Volume 53(2016:Apr.)
• Page Start: 35
• Page End: 44
• Publication Date: 2016-04
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2015.10.008
• Languages: English
• ISSNs: 0195-6698

Abstract

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.