Limiting distributions for the number of inversions in labelled tree families

2011/01/25 by Alois Panholzer, Panholzer, Alois, Georg Seitz +1
Computer Science · Mathematics · #05A16 #05C05 #60F05 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05A16 #msc:05C05 #msc:60F05

paper · pdf · doi:10.48550/arxiv.1101.4790

18 pages, 1 figure

arxiv created 2011/01/25 · openalex publication_date 2011/01/25 · arxiv updated 2011/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider so-called simple families of labelled trees, which contain, e.g., ordered, unordered, binary and cyclic labelled trees as special instances, and study the global and local behaviour of the number of inversions. In particular we obtain limiting distribution results for the total number of inversions as well as the number of inversions induced by the node labelled j in a random tree of size n.

Citations

• Singularity Analysis of Generating Functions

Related

• Sorting Index and Mahonian-Stirling Pairs for Labeled Forests
• Subtrees of a random tree
• Some Distributions on Finite Rooted Binary Trees
• The Distribution of Patterns in Random Trees
• Local limits of descent-biased permutations and trees