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., 2004, Volume 16, Issue 4, Pages 117–133 (Mi dm180)  

This article is cited in 1 scientific paper (total in 1 paper)

Random free trees and forests with constraints on the multiplicities of vertices

A. N. Timashev


Abstract: We consider free (not rooted) trees with $n$ labelled vertices whose multiplicities take values in some fixed subset $A$ of non-negative integers such that $A$ contains zero, $A\ne\{0\}$, ${A\ne\{0,1\}}$, and the greatest common divisor of the numbers $\{k\mid k\in A\}$ is equal to one. We find the asymptotic behaviour of the number of all these trees as $n\to\infty$. Under the assumption that the uniform distribution is defined on the set of these trees, for the random variable $\mu_r^{(A)}$, $r\in A$, which is equal to the number of vertices of multiplicity $r$ in a randomly chosen tree, we find the asymptotic behaviour of the mathematical expectation and variance as $n\to\infty$ and prove local normal and Poisson theorems for these random variables. For the case $A=\{0,1\}$, we obtain estimates of the number of all forests with $n$ labelled vertices consisting of $N$ free trees as $n\to\infty$ under various constraints imposed on the function $N=N(n)$. We find the asymptotic behaviour of the number of all forests of free trees with $n$ vertices of multiplicities at most one. We prove local normal and Poisson theorems for the number of trees of given size and for the total number of trees in a random forest of this kind. We obtain limit distribution of the random variable equal to the size of the tree containing the vertex with given label.

DOI: https://doi.org/10.4213/dm180

Full text: PDF file (1077 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2004, 14:6, 603–618

Bibliographic databases:

UDC: 519.2
Received: 10.07.2003
Revised: 24.09.2004

Citation: A. N. Timashev, “Random free trees and forests with constraints on the multiplicities of vertices”, Diskr. Mat., 16:4 (2004), 117–133; Discrete Math. Appl., 14:6 (2004), 603–618

Citation in format AMSBIB
\Bibitem{Tim04}
\by A.~N.~Timashev
\paper Random free trees and forests with constraints on the multiplicities of vertices
\jour Diskr. Mat.
\yr 2004
\vol 16
\issue 4
\pages 117--133
\mathnet{http://mi.mathnet.ru/dm180}
\crossref{https://doi.org/10.4213/dm180}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2141150}
\zmath{https://zbmath.org/?q=an:1103.60015}
\transl
\jour Discrete Math. Appl.
\yr 2004
\vol 14
\issue 6
\pages 603--618
\crossref{https://doi.org/10.1515/1569392043272494}


Linking options:
  • http://mi.mathnet.ru/eng/dm180
  • https://doi.org/10.4213/dm180
  • http://mi.mathnet.ru/eng/dm/v16/i4/p117

    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. A. V. Kolchin, V. F. Kolchin, “On transition of distributions of sums of independent identically distributed random variables from one lattice to another in the generalised allocation scheme”, Discrete Math. Appl., 16:6 (2006), 527–540  mathnet  crossref  crossref  mathscinet  zmath  elib
  • Дискретная математика
    Number of views:
    This page:339
    Full text:113
    References:46
    First page:1

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