摘要：We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. Then we consider X_n, the normalized version of I(T_n), for a sequence of trees T_n. For fixed T_n's, we prove a sufficient condition for X_n to converge in distribution. For T_n being split trees [Devroye, 1999], we show that X_n converges to the unique solution of a distributional equation. Finally, when T_n's are conditional Galton-Watson trees, we show that X_n converges to a random variable defined in terms of Brownian excursions. Our results generalize and extend previous work by Panholzer and Seitz [Panholzer and Seitz, 2012].
关键词：inversions; random trees; split trees; Galton-Watson trees; permutation; cumulant
Loading...
