Diskretnaya Matematika
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskr. Mat.: Year: Volume: Issue: Page: Find

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

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

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{https://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{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79961085874} 

• http://mi.mathnet.ru/eng/dm1142
• https://doi.org/10.4213/dm1142
• http://mi.mathnet.ru/eng/dm/v23/i2/p66

 SHARE:

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:
1. Tsitsiashvili G.Sh., Osipova M.A., Markova N.V., “Rekurrentnaya posledovatelnost parallelno-posledovatelnykh soedinenii”, Vestn. Tikhookeanskogo gos. un-ta, 2012, no. 3, 027–032
2. 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: 345 Full text: 159 References: 31 First page: 21