The smallest size of components in random decomposable combinatorial structures is studied in a general framework. Our results include limit distribution and local theorems for the size of the rth smallest component of an object of size n. Expectation, variance and higher moments of the rth smallest component are also derived. The results apply to several combinatorial structures in the exp-log class for both labelled and unlabelled objects. We exemplify with several combinatorial structures like permutations and polynomials over finite fields.

Additional Metadata
Keywords Buchstab function, Exp-log class, Random decomposable combinatorial structures, Smallest components
Journal Algorithmica
Citation
Panario, D, & Richmond, B. (2001). Smallest components in decomposable structures: Exp-log class. Algorithmica, 29(1-2), 205–226.