Counting Leaders of Labeled Rooted Trees

William Y. C. Chen and Qing-Hu Hou
Center for Combinatorics, Nankai University, Tianjin 300071, P. R. China


Abstract     Full Text  PDF

A leader of a labeled rooted tree is a vertex that has no smaller descendants. We present a bijection between labeled rooted trees and integer sequences $a_{1}, \cdots, a_{n-1}$ with $a_{i} \in \{1, 2, \ldots, n\}$ such that the number of leaders is exactly one more than that of $i$'s satisfying $a_{i}\le i$ in the corresponding sequence.