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

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
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} 

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

 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. 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