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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

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/dm1142
  • https://doi.org/10.4213/dm1142
  • http://mi.mathnet.ru/eng/dm/v23/i2/p66

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  elib
    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  crossref  mathscinet  zmath  isi  scopus
  • Дискретная математика
    Number of views:
    This page:283
    Full text:81
    References:28
    First page:21

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019