Asymptotic number of forests from unrooted trees (Q909669): Difference between revisions

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