RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2004 Volume 16, Issue 4, Pages 117–133 (Mi dm180)

This article is cited 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.

UDC: 519.2

Received: 10.07.2003
Revised: 24.09.2004

DOI: 10.4213/dm180


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

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024