Premium
Order statistics for decomposable combinatorial structures
Author(s) -
Hansen Jennie C.
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050404
Subject(s) - simplex , mathematics , combinatorics , poisson distribution , point process , order statistic , logarithm , dirichlet distribution , component (thermodynamics) , generating function , joint probability distribution , distribution (mathematics) , probabilistic logic , discrete mathematics , statistics , mathematical analysis , physics , thermodynamics , boundary value problem
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.