Asymptotic number of forests from unrooted trees (Q909669)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic number of forests from unrooted trees |
scientific article |
Statements
Asymptotic number of forests from unrooted trees (English)
0 references
1988
0 references
This article gives an asymptotic formula for the number of labelled forests on n vertices with N components (trees). The formula breaks up into four cases, determined by the behaviour of N as n goes to infinity. The proof makes good use of local limit theorems for sums of independent, identically distributed random variables, along with a good deal of analysis. It extends the formula of \textit{A. Renyi} [``Some remarks on the theory of trees'', Publ. Math. Inst. Hung. Acad. Sci. 4, No.1, 73-83 (1959)], which was for fixed N. In particular, it follows that Renyi's formula, \(n^{(n-2)}/((N-1)!2^{(N-1)}),\) holds if and only if \(N=o(n)\).
0 references
asymptotic formula
0 references
number of labelled forests on n vertices
0 references