Geodesic
Random free trees and forests with constraints on the multiplicities of vertices
Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 117-133.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2004_16_4_a10,
     author = {A. N. Timashev},
     title = {Random free trees and forests with constraints on the multiplicities of vertices},
     journal = {Diskretnaya Matematika},
     pages = {117--133},
     publisher = {mathdoc},
     volume = {16},
     number = {4},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_4_a10/}
}
TY  - JOUR
AU  - A. N. Timashev
TI  - Random free trees and forests with constraints on the multiplicities of vertices
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 117
EP  - 133
VL  - 16
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_4_a10/
LA  - ru
ID  - DM_2004_16_4_a10
ER  - 
%0 Journal Article
%A A. N. Timashev
%T Random free trees and forests with constraints on the multiplicities of vertices
%J Diskretnaya Matematika
%D 2004
%P 117-133
%V 16
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2004_16_4_a10/
%G ru
%F DM_2004_16_4_a10
A. N. Timashev. Random free trees and forests with constraints on the multiplicities of vertices. Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 117-133. http://geodesic.mathdoc.fr/item/DM_2004_16_4_a10/

[1] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, Moskva, 1982 | MR | Zbl

[2] Holst L., “On numbers related to partition of unlike objects and occupancy problems”, European J. Comb., 2 (1981), 231–237 | MR | Zbl

[3] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P., Sluchainye razmescheniya, Nauka, Moskva, 1976 | MR | Zbl

[4] Britikov V. E., “Asimptotika chisla lesov iz nekornevykh derevev”, Matem. zametki, 43:5 (1988), 672–684 | MR

[5] Britikov V. E., “Predelnoe povedenie chisla derevev zadannogo ob'ema v sluchainom lese iz nekornevykh derevev”, Veroyatnostnye zadachi diskretnoi matematiki, MIEM, Moskva, 1988, 7–12 | MR

[6] Kolchin V. F., Sluchainye otobrazheniya, Nauka, Moskva, 1984 | MR

[7] Fedoryuk M. V., Metod perevala, Nauka, Moskva, 1977 | MR

[8] Timashev A. N., “Sluchainye lesa s izvestnym chislom svobodnykh derevev”, Obozrenie prikladnoi i promyshlennoi matem, 8:2 (2001), 804–806 | MR