Order statistics for decomposable combinatorial structures
Jennie C. Hansen · Random Structures and Algorithms · 1994
Abstract In this paper we consider the component structure of decomposable combinatorial objects, both labeled and unlabeled, from a probabilistic point of view. In both cases we show that when the generating function for the components of a structure is a logarithmic function, then the joint distribution of the normalized order statistics of the component sizes of a random object of size n coverges to the Poisson–Dirichlet distribution on the simplex ∇{{ x i }: Σ x i = 1 x 1 ⩾ x 2 ⩾ …︁ ⩾ 0}. This result complements recent results obtained by Flajolet and Soria on the total number of components in a random combinatorial structure. © 1994 John Wiley & Sons, Inc.