Order statistics for decomposable combinatorial structures
- 11 October 1994
- journal article
- Published by Wiley in Random Structures & Algorithms
- Vol. 5 (4) , 517-533
- https://doi.org/10.1002/rsa.3240050404
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 sizencoverges to the Poisson–Dirichlet distribution on the simplex ∇{{xi}: Σxi= 1x1⩾x2⩾ …︁ ⩾ 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.Keywords
This publication has 18 references indexed in Scilit:
- Riffle shuffles, cycles, and descentsCombinatorica, 1995
- On random polynomials over finite fieldsMathematical Proceedings of the Cambridge Philosophical Society, 1993
- Gaussian limiting distributions for the number of components in combinatorial structuresJournal of Combinatorial Theory, Series A, 1990
- Continuity and weak convergence of ranked and size-biased permutations on the infinite simplexStochastic Processes and their Applications, 1989
- A Functional Central Limit Theorem for Random MappingsThe Annals of Probability, 1989
- Some methods for computing component distribution probabilities in relational structuresDiscrete Mathematics, 1987
- Random permutations and Brownian motionPacific Journal of Mathematics, 1985
- École d'Été de Probabilités de Saint-Flour XIII — 1983Published by Springer Nature ,1985
- Central and local limit theorems applied to asymptotic enumerationJournal of Combinatorial Theory, Series A, 1973
- On the field of combinatory analysisAmerican Mathematical Society Translations: Series 2, 1962