Limiting distributions for the number of distinct component sizes in relational structures

摘要

We investigate from probabilistic point of view the asymptotic behavior of the number of distinct component sizes in general classes of combinatorial structures of size n as n --> infinity. 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. (C) 1997 Academic Press.