This article is cited in
2 papers
Asymptotic expansions for the distribution of the number of components in random mappings and partitions
A. N. Timashov
Abstract:
We consider the class of all
$n^n$ single-valued mappings of an
$n$-element set into itself. Assuming that all such mappings have the same probabilities equal to
$n^{-n}$, we investigate the distribution of the random variable
$\nu_n$ equal to the number of connected components in such random mapping. We obtain asymptotic estimates of the probability
$\mathbf P\{\nu_n=M\}$ as
$n$,
$N\to\infty$ in such a way that the ratio
$N/\ln n$ does not tend to 0 and infinity. In the case where
$N=\frac12\ln n+o(\ln n)$ as
$n\to\infty$, we obtain a complete asymptotic expansion of this probability.
A similar expansion is obtained for the probability
$\mathbf P\{\xi_n=N\}$, where
$\xi_n$ is the random variable equal to the number of cycles in a permutation randomly and equiprobably chosen from the set of all
$n!$ permutations of degree
$n$, and also for the probability
$\mathbf P\{\theta_n=N\}$, where
$\theta_n$ is the number of blocks in a random partition of a set with
$n$ elements.
UDC:
519.24 Received: 19.12.2008
DOI:
10.4213/dm1142