Asymptotics of the number of forests consisting of unrooted trees (Q1824626): Difference between revisions

It follows from the Cayley formula that the number of forests with n nodes and N trees are \[ a_{n,N}=\frac{n!}{N!}\sum_{k_ 1+...+k_ N=n}\prod^{N}_{j=1}\frac{k_ j^{k_ j-2}}{k_ j!}. \] It was shown by A. Renyi (1959) that the following asymptotics holds for fixed N \[ a_{n,N}\sim \frac{n^{n-2}}{2^{N-1}(N-1)!},\quad as\quad n\to \infty. \] In the paper the asymptotics of the \(a_{n,N}\) as \(n\to \infty\) and various behaviours of N are obtained. Let \(T=n-N\) be the number of edges in the forest, \(\nu =N^{1/3}(\frac{n}{N}-2)\). Theorem. Let \(n\to \infty\). Then the following statements hold: 1. If T is bounded, \[ a_{n,N}\sim \left( \begin{matrix} n\\ T\end{matrix}\right) (\frac{N}{2})^ T \] 2. If \(T\to \infty\) and \(\nu\) \(\to -\infty\), \[ a_{n,N}\sim \frac{n^{2T}}{2^ TT!}(1-\frac{2T}{n})^{1/2} \] 3. If T is bounded, \[ a_{n,N}\sim \frac{n^{n-2}N^{5/6}}{2^{N-3}(N- 1)!\sqrt{\pi}}\int^{\infty}_{0}e^{-4t^{3/2}}\cos (\nu t+4/3t^{3/2})dt. \] 4. If \(\nu\) \(\to \infty\), \[ a_{n,N}\sim \frac{n^{n-2}}{2^{N-1}(N-1)!}(\frac{2T}{n}-1)^{-5/2}. \]