An insertion algorithm and leaders of rooted trees

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 a1⋯an−1a1⋯an−1 with ai∈{1,2,…,n}ai∈{1,2,…,n} such that the number of leaders is exactly one more than the number of anti-excedances, namely, the positions ii for which ai≤iai≤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.