
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 nonnegative 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 117133
\mathnet{http://mi.mathnet.ru/dm180}
\crossref{https://doi.org/10.4213/dm180}
\mathscinet{http://www.ams.org/mathscinetgetitem?mr=2141150}
\zmath{https://zbmath.org/?q=an:1103.60015}
\transl
\jour Discrete Math. Appl.
\yr 2004
\vol 14
\issue 6
\pages 603618
\crossref{https://doi.org/10.1515/1569392043272494}
Linking options:
http://mi.mathnet.ru/eng/dm180https://doi.org/10.4213/dm180 http://mi.mathnet.ru/eng/dm/v16/i4/p117
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:

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

Number of views: 
This page:  339  Full text:  113  References:  46  First page:  1 
