|
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.
DOI:
https://doi.org/10.4213/dm1142
Full text:
PDF file (112 kB)
References:
PDF file
HTML file
English version:
Discrete Mathematics and Applications, 2011, 21:3, 291–301
Bibliographic databases:
UDC:
519.24 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
Citation in format AMSBIB
\Bibitem{Tim11}
\by A.~N.~Timashov
\paper Asymptotic expansions for the distribution of the number of components in random mappings and partitions
\jour Diskr. Mat.
\yr 2011
\vol 23
\issue 2
\pages 66--75
\mathnet{http://mi.mathnet.ru/dm1142}
\crossref{https://doi.org/10.4213/dm1142}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2865908}
\elib{http://elibrary.ru/item.asp?id=20730385}
\transl
\jour Discrete Math. Appl.
\yr 2011
\vol 21
\issue 3
\pages 291--301
\crossref{https://doi.org/10.1515/DMA.2011.018}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79961085874}
Linking options:
http://mi.mathnet.ru/eng/dm1142https://doi.org/10.4213/dm1142 http://mi.mathnet.ru/eng/dm/v23/i2/p66
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
This publication is cited in the following articles:
-
Tsitsiashvili G.Sh., Osipova M.A., Markova N.V., “Rekurrentnaya posledovatelnost parallelno-posledovatelnykh soedinenii”, Vestn. Tikhookeanskogo gos. un-ta, 2012, no. 3, 027–032
-
Berlinkov M.V., “On the Probability of Being Synchronizable”, Algorithms and Discrete Applied Mathematics, Lecture Notes in Computer Science, 9602, eds. Govindarajan S., Maheshwari A., Springer Int Publishing Ag, 2016, 73–84
|
Number of views: |
This page: | 283 | Full text: | 81 | References: | 28 | First page: | 21 |
|