RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2011 Volume 23, Issue 2, Pages 66–75 (Mi dm1142)

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


 English version:
Discrete Mathematics and Applications, 2011, 21:3, 291–301

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025