Asymptotics of the number of forests consisting of unrooted trees
type: Item
instance of: scholarly article
title: Asymptotics of the number of forests consisting of unrooted trees
zbMATH Open document ID: 0683.05017
DOI: 10.1007/BF01158847
author: V. E. Britikov
published in: Mathematical Notes
publication date: 1988-01-01T00:00:00Z
review text: 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}. \]
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 4118389
zbMATH Keywords: Cayley formula
zbMATH Keywords: number of forests
MaRDI profile type: Publication
cites work: Q5535438
description: scientific article; zbMATH DE number 4118389