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

Diskr. Mat., 2006 Volume 18, Issue 3, Pages 77–84 (Mi dm60)

This article is cited in 1 paper

Large deviations for the number of trees of a given size and for the maximum size of a tree in a random forest

A. N. Timashev


Abstract: We consider the set of all forests consisting of $N$ rooted trees such that the roots (and the corresponding trees) are labelled by the numbers $1,\dots,N$, and the remaining $n$ vertices of the forest are labelled by the numbers $1,\dots,n$. Under the assumption that the uniform distribution is defined on this set and $n,N\to\infty$, we prove local limit theorems for the distributions of the random variables equal to the number of trees of a given size and the maximum size of a tree, which permit to estimate the corresponding local probabilities with accuracy of known order, including the probability of large deviations.

UDC: 519.2

Received: 09.06.2004

DOI: 10.4213/dm60


 English version:
Discrete Mathematics and Applications, 2006, 16:6, 555–561

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025