Limiting Distributions for the Number of Distinct Component Sizes in Relational Structures

AbstractWe investigate from probabilistic point of view the asymptotic behavior of the number of distinct component sizes in general classes of combinatorial structures of sizenasn→∞. Mild restrictions of admissibility type are imposed on the corresponding generating functions and asymptotic expressions of the mean and variance of that number are obtained. Then we establish weak convergence to a convolution of two distributions, where one of them is always Gaussian. As an illustration we consider three typical generating function examples: partitions of a finite set, partitions of a positive integer and mappings of a finite set into itself