Golomb and Gaal [15] study the number of permutations on n objects with largest cycle length equal to k. They give explicit expressions on ranges n/(i + 1)< k ≤ n/i for i = 1,2,..., derive a general recurrence for the number of permutations of size n with largest cycle length equal to k, and provide the contribution of the ranges (n/(i + 1), n/i] for i = 1,2,..., to the expected length of the largest cycle. We view a cycle of a permutation as a component. We provide exact counts for the number of decomposable combinatorial structures with largest and smallest components of a given size. These structures include permutations, polynomials over finite fields, and graphs among many others (in both the labelled and unlabelled cases). The contribution of the ranges (n/(i + 1), n/i] for i = 1,2,..., to the expected length of the smallest and largest component is also studied.

Additional Metadata
Keywords Exponential class, Largest and smallest components, Random decomposable combinatorial structures
Journal Algorithmica (New York)
Citation
Panario, D, & Richmond, B. (2001). Exact largest and smallest size of components. Algorithmica (New York), 31(3), 413–432.