Geodesic
Asymptotic expansions for the distribution of the number of components in random mappings and partitions
Diskretnaya Matematika, Tome 23 (2011) no. 2, pp. 66-75 
A. N. Timashov. Asymptotic expansions for the distribution of the number of components in random mappings and partitions. Diskretnaya Matematika, Tome 23 (2011) no. 2, pp. 66-75. http://geodesic.mathdoc.fr/item/DM_2011_23_2_a5/
@article{DM_2011_23_2_a5,
     author = {A. N. Timashov},
     title = {Asymptotic expansions for the distribution of the number of components in random mappings and partitions},
     journal = {Diskretnaya Matematika},
     pages = {66--75},
     year = {2011},
     volume = {23},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_2_a5/}
}
TY  - JOUR
AU  - A. N. Timashov
TI  - Asymptotic expansions for the distribution of the number of components in random mappings and partitions
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 66
EP  - 75
VL  - 23
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_2_a5/
LA  - ru
ID  - DM_2011_23_2_a5
ER  - 
%0 Journal Article
%A A. N. Timashov
%T Asymptotic expansions for the distribution of the number of components in random mappings and partitions
%J Diskretnaya Matematika
%D 2011
%P 66-75
%V 23
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2011_23_2_a5/
%G ru
%F DM_2011_23_2_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Timashëv A. N., “Sluchainye otobrazheniya konechnykh mnozhestv s izvestnym chislom komponent”, Teoriya veroyatnostei i ee primeneniya, 48:4 (2003), 818–828 | MR | Zbl

[2] Kolchin V. F., Sluchainye otobrazheniya, Nauka, Moskva, 1984 | MR | Zbl

[3] Harris B., “Probability distributions related to random mappings”, Ann. Math. Statist., 31:4 (1960), 1045–1062 | DOI | MR | Zbl

[4] Pavlov Yu. L., “Predelnye raspredeleniya odnoi kharakteristiki sluchainogo otobrazheniya”, Teoriya veroyatnostei i ee primeneniya, 26:4 (1981), 841–847 | MR | Zbl

[5] Cheplyukova I. A., “Ob odnoi kharakteristike sluchainogo otobrazheniya s izvestnym chislom tsiklov”, Diskretnaya matematika, 18:3 (2006), 43–60 | MR | Zbl

[6] Volynets L. M., “Otsenka skorosti skhodimosti k predelnomu raspredeleniyu dlya chisla tsiklov v sluchainoi podstanovke”, Veroyatnostnye zadachi diskretnoi matematiki, MIEM, Moskva, 1987, 40–46 | MR

[7] Kolchin V. F., Sluchainye grafy, Nauka, Moskva, 2000 | MR

[8] Timashëv A. N., “Ob asimptoticheskikh razlozheniyakh dlya raspredeleniya chisla tsiklov v sluchainoi podstanovke”, Diskretnaya matematika, 15:3 (2003), 117–127 | MR | Zbl

[9] Sachkov V. N., Veroyatnostnye metody v kombinatornom analize, Nauka, Moskva, 1978 | MR | Zbl

[10] Moser L. M., Wyman M., “An asymptotic for the Bell numbers”, Trans. Royal Soc. Canada, 49 (1955), 49–54 | MR | Zbl

[11] Medvedev Yu. I., Ivchenko G. I., “Asimptoticheskie predstavleniya konechnykh raznostei stepennoi funktsii v proizvolnoi tochke”, Teoriya veroyatnostei i ee primeneniya, 10:1 (1965), 151–156 | MR | Zbl