|
This article is cited in 2 scientific papers (total 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.
Received: 19.12.2008
Citation:
A. N. Timashov, “Asymptotic expansions for the distribution of the number of components in random mappings and partitions”, Diskr. Mat., 23:2 (2011), 66–75; Discrete Math. Appl., 21:3 (2011), 291–301
Linking options:
https://www.mathnet.ru/eng/dm1142https://doi.org/10.4213/dm1142 https://www.mathnet.ru/eng/dm/v23/i2/p66
|
Statistics & downloads: |
Abstract page: | 520 | Full-text PDF : | 211 | References: | 45 | First page: | 21 |
|