کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653318 | 1632764 | 2016 | 10 صفحه PDF | دانلود رایگان |
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.
Journal: European Journal of Combinatorics - Volume 53, April 2016, Pages 35–44