Asymptotics for the Probability of Connectedness and the Distribution of Number of Components

Abstract

Let $\rho _n$ be the fraction of structures of "size" $n$ which are "connected"; e.g., (a) the fraction of labeled or unlabeled $n$-vertex graphs having one component, (b) the fraction of partitions of $n$ or of an $n$-set having a single part or block, or (c) the fraction of $n$-vertex forests that contain only one tree. Various authors have considered $\lim \rho _n$, provided it exists. It is convenient to distinguish three cases depending on the nature of the power series for the structures: purely formal, convergent on the circle of convergence, and other. We determine all possible values for the pair $(\liminf \rho _{n},\;\limsup \rho _{n})$ in these cases. Only in the convergent case can one have $0 < \lim \rho _{n} < 1$. We study the existence of $\lim \rho _{n}$ in this case.