%%%%%%% Generic paper macros
\magnification 1200
\hsize = 6truein
\vsize = 9truein
\normalbaselines
\overfullrule=0pt
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1
{\smcp the electronic journal of combinatorics 7 (2000), \#R33
\hfill\folio} \fi}
\magnification1200
\overfullrule=0pt
\def\itemskip{\smallskip}
\def\betweenskip{\medskip}
\newcount\eqcount \eqcount=0
\def\equno#1{\global\advance\eqcount by 1
\xdef#1{(\the\eqcount)}
(\the\eqcount)}
\def\eqlabel{\eqno\equno}
\newcount\seccount
\def\section#1\par{\vskip 30pt
\advance\seccount by 1
\centerline{\bf\the\seccount. #1}
\vskip12pt\noindent}
\def\labelsection#1{\edef#1{\the\seccount}}
\def\nonumsection#1\par{\vskip 30pt%
\centerline{\bf #1}
\vskip12pt\noindent}
\newcount\thmcount \thmcount=0
\newcount\corcount
\newcount\conjcount \conjcount=0
\def\thmfont{\it}
\def\theorem #1{\advance\thmcount by 1
\edef#1{\the\thmcount}
\betweenskip\noindent
{\bf Theorem~\the\thmcount}.\thmfont~~}
\def\theoremname#1#2{\advance\thmcount by 1 \corcount=0
\edef#2{\the\thmcount}
\betweenskip\noindent
{\bf Theorem~\the\thmcount} \rm(#1).\thmfont~~}
\newcount\lemmacount \lemmacount=0
\def\corollary{\advance\corcount by 1
\betweenskip\noindent
{\bf Corollary~\the\thmcount.\the\corcount}.\thmfont~~}
\def\lemma #1{\advance\lemmacount by 1
\edef#1{\the\lemmacount}
\betweenskip\noindent
{\bf Lemma~\the\lemmacount}.\thmfont~~}
\def\conjecture #1{\advance\conjcount by 1
\edef#1{\the\conjcount}
\betweenskip\noindent
{\bf Conjecture~\the\conjcount}.\thmfont~~}
\def\endthing{\rm}
\def\Endthing{\rm\betweenskip}
\def\proof{\betweenskip\noindent
{\bf Proof}: }
\def\Proof #1{\betweenskip\noindent
{\bf Proof} (#1): }
\def\disqed{~~\lower.3ex\vbox{\hrule height2ex width1.5ex}}
\def\qed{\disqed\smallskip}
\def\Item{\itemskip\item}
\def\Bitem{\Item{$\bullet$}}
\def\Itemitem{\itemskip\itemitem}
\def\Bitemitem{\Itemitem{$\bullet$}}
\def\smallstrut{{\vrule height4pt depth0pt width0pt}}
\def\vec#1{{\bf #1}}
\def\pclim{\rho}
\def\pc#1{\pclim_{#1}}
\def\pcsup{{\pclim_{\hskip.5pt\rm sup}}}
\def\pcinf{{\pclim_{\hskip.7pt\rm inf}}}
\def\boxitat#1#2{\vbox % from TeXbook Ex.21.3
{\hrule\hbox{\vrule\kern#1%
\vbox{\kern #1\hbox{#2}\kern#1}\kern#1\vrule}\hrule}}
%%%%%%%%%%%%%%%%% references
\newcount\refcount \refcount=0
\def\reference#1{\advance\refcount by 1
\edef#1{\the\refcount}}
\reference\ArratiaBT
\reference\Beissinger
\reference\Bell
\reference\Bender
\reference\BenderCOR
\reference\Burris
\reference\BurrisCOR
\reference\BurrisS
\reference\Cameron
\reference\Compton
\reference\Embrechts
\reference\FlajoletN
\reference\FlajoletS
\reference\Gourdon
\reference\HararyRS
\reference\Hayman
\reference\Hwang
\reference\KnopfK
\reference\MeirM
\reference\Odlyzko
\reference\Promel
\reference\RichmondW
\reference\Rudin
\reference\Stam
\reference\WrightL
\reference\WrightU
\reference\WrightG
\reference\Zvonkin
\centerline{\bf Asymptotics for the Probability of Connectedness}
\centerline{\bf and the Distribution of Number of Components}
\bigskip
\centerline{Jason P. Bell}
\centerline{Department of Mathematics}
\centerline{University of California, San Diego}
\centerline{La Jolla, CA 92903-0112, USA}
\centerline{(email: {\tt jbell@math.ucsd.edu})}
\medskip
\centerline{Edward A. Bender}
\centerline{Department of Mathematics}
\centerline{University of California, San Diego}
\centerline{La Jolla, CA 92903-0112, USA}
\centerline{(email: {\tt ebender@ucsd.edu})}
\medskip
\centerline{Peter J. Cameron}
\centerline{School of Mathematical Sciences}
\centerline{Queen Mary and Westfield College}
\centerline{Mile End Road}
\centerline{London E1 4NS, England}
\centerline{(email: {\tt p.j.cameron@qmw.ac.uk})}
\medskip
\centerline{L. Bruce Richmond}
\centerline{Department of Combinatorics and Optimization}
\centerline{University of Waterloo}
\centerline{Waterloo, Ontario N2L 3G1, Canada}
\centerline{(email: {\tt lbrichmond@math.uwaterloo.ca})}
\medskip
\centerline{Submitted: January 21, 2000}
\centerline{Accepted: May 30, 2000}
\nonumsection Abstract
Let $\pc{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\pc{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
\hbox{$(\liminf\pc{n},\;\limsup\pc{n})$} in these cases.
Only in the convergent case can one have $0<\lim\pc{n}<1$.
We study the existence of $\lim\pc{n}$ in this case.
\vfill
\noindent
AMS-MOS Subject Classification (1990): 05A16; Secondary: 05C30, 05C40
\eject
\footline={}
\section Introduction
Throughout, $A_n$ will denote the number of structures of size $n$,
$C_n$ will denote the number that are connected, and
$\pc{n}=C_n/A_n$ whenever $A_n\ne0$.
We consider two situations: either
the objects are labeled and the exponential generating functions are
related by
$$
A(x)=\exp\Bigl(C(x)\Bigr)
\eqlabel\eqLexp
$$
or the objects are unlabeled and the ordinary generating functions
are related by
$$
A(x)=\exp\biggl(\sum_{k\ge1}C(x^k)/k\biggr).
\eqlabel\eqUexp
$$
Perhaps the most interesting omissions are
\Bitem
objects with ``noncrossing'' parts, which lead to functional
equations as in Beissinger [\Beissinger] and Flajolet and
Noy~[\FlajoletN], and
\Bitem
multiplicative objects, which lead to Dirichlet series.
\itemskip
We are interested in the three asymptotic probabilities
$$
\pcinf=\liminf\pc{n},\qquad
\pcsup=\limsup\pc{n},\qquad
{\rm and}\qquad
\pclim=\lim\pc{n},
$$
where the limits are taken through those $n$ for which $A_n\ne0$ and
$\pclim$ is defined only when that limit exists.
$$
{\hsize=.65\hsize
\vcenter{\noindent
When $C(x)$ is a polynomial, we immediately have $\pclim=0$.
Therefore we assume that $C(x)$ is not a polynomial.}}
\eqlabel\eqNotPoly
$$
Information on possible values for $\pcinf$ and $\pcsup$ are given in
Theorem~1.
Various authors have obtained results about when $\pclim$ exists.
See the papers by Compton~[\Compton], Knopfmacher and
Knopfmacher~[\KnopfK] and Bender, Cameron, Odlyzko and
Richmond~[\BenderCOR].
Related to this is the question of whether first-order limit laws
exist~[\Burris--\BurrisS,\thinspace\Promel].
If $\pclim$ exists, one may ask about various limiting probability
distributions.
Perhaps the three most interesting questions are as follows.
\Bitem
What, if any, is the limiting behavior of probability distribution of
the number of components when objects of size $n$ are selected
uniformly at random?
More on this shortly.
\Bitem
What, if any, is the limiting behavior of the joint distribution of
objects of various sizes?
We do not discuss this.
See Arratia, Barbour, and Tavar\'e~[\ArratiaBT] for some results.
\Bitem
What, if any, is the limiting behavior of probability distribution of
the size of the largest component when objects of size $n$ are selected
uniformly at random?
We do not discuss this.
See Gourdon~[\Gourdon] for some results.
\itemskip\noindent
The limiting distribution of the number of components, when
it exists, has four common behaviors.
Let $0\le R\le\infty$ be the radius of convergence of $C(x)$.
If $R=0$, the mass of the distribution is concentrated at 1 because
$C_n/A_n\to1$ by Theorem~1.
If $C(R)$ diverges, the distribution is often normal.
Arguments for normality usually rely on analytic properties of the
generating function as in Flajolet and Soria~[\FlajoletS].
When there is a logarithmic singularity on the circle of convergence,
Hwang~[\Hwang] obtained refinements which are similar to what happens
when $C(R)$ converges:
The labeled case leads to a shifted Poisson and unlabeled case is
more complicated.
Compton~[\Compton] obtained some results in these cases, and we present
additional ones in Theorem~2.
In contrast to the analytic approaches for normality, our method
relies on direct estimations of sums.
\medskip
We thank A. Meir for helpful comments and references.
\section Results and Discussion
It is useful to consider cases depending on $R$ and the convergence
of $C(R)$.
With L for labeled and U for unlabeled:
$$
\vbox{\tabskip=0pt%
\halign{#\hfill~or~&#\hfill\quad{means}\quad&#\hfill\cr
L0&U0 & $R=0$,\cr
LD&UD & $R>0$ and $C(R)$ diverges,\cr
LC&UC & $R>0$ and $C(R)$ converges.\cr}}
$$
For case LD we may have $R=\infty$.
Since $C_n$ counts objects, it is an integer and so, in the unlabeled
case, $R\le1$ and $C(1)$ diverges.
{From} \eqNotPoly\ and the fact that $C_n$ is an integer, we have
$R<1$ for case UC.
\theorem\ThmInfSup
The following three cases completely describe all possibilities for
the pair $\pcinf,\;\pcsup$, subject to the obvious constraint that
$0\le\pcinf\le\pcsup\le1$.
\Item{(a)}
For L0 and U0, $\pcsup=1$ and all values are possible for $\pcinf$.
\Item{(b)}
For LD and UD, $\pcinf=0$ and all values are possible for $\pcsup$.
\Item{(c)}
For LC and UC, all values are possible for the pair $(\pcinf,\pcsup)$
except $(0,0)$ and $(1,1)$.
\itemskip\noindent
These results still hold if we also require that $C_n\ne0$ for all
sufficiently large $n$.
\Endthing
\noindent
``All values are possible'' means that for each possible $R$ in each
of the six cases and for any possible value, there exist nonnegative
integers $C_n$ so that the value occurs.
We immmediately have the following corollaries.
\corollary
Only $(\pcinf,\pcsup)=(0,1)$ can occur in all six cases.
\endthing
\corollary
If $\pclim$ exists, then
\Item{(a)}
for L0 and U0 $\pclim=1$,
\Item{(b)}
for LD and UD $\pclim=0$,
\Item{(c)}
for LC and UC any value in the interval $(0,1)$ is possible.
\Endthing
For any power series $F(x)$, let $f_n=[x^n]\,F(x)$.
(Thus $c_n=C_n/n!$ in the labeled case and $c_n=C_n$ in the
unlabeled case.)
Let $c_n^{(k)}=[x^n]\,C(x)^k$.
There is a close relation between the existence of $\pclim$ and the
statement $\lim_{n\to\infty} c_n^{(2)}/c_n=2C(R)$:
\Bitem
Suppose $R=0$.
We know by Theorem~1(a) that $\pclim=1$ if it exists.
Wright~[\WrightL,\thinspace\WrightU] proved that $\pclim=1$ if and
only if $c_n^{(2)}/c_n\to0$.
Since $R=0$, $C(R)=0$.
\Bitem
When $C(R)$ diverges, the conditions are not equivalent.
Cameron~[\Cameron] proved that $c_n^{(2)}/c_n\to\infty$ implies
$\pclim=0$, but the converse is false.
To see this for LD (UD is similar), let $C_n=n!2^n$ if $n$ is a
perfect square and $C_n=1$ otherwise.
If $p$ is a prime congruent to 3 modulo 4 and $n=p^2$, then $n$ is
not the sum of two nonzero squares and so at most one of $c_k$ and
$c_{n-k}$ exceeds 1.
Thus
$$
c_n^{(2)}
\le n + 2\sum_{k^20$ and $C(R)$ converges.
Let $A(x,y)$ enumerate structures by size and number of
components.
Thus
$$
A(x,y) = \cases{
\exp(yC(x))\phantom{{}_{\bigl(}} & for labeled structures,\cr
\exp\Bigl(\sum_{k\ge1} y^kC(x^k)/k\Bigr)& for unlabeled structures.\cr}
$$
Suppose that
\Item{(a)}
$c_n > 0$ for all sufficiently large $n$ and
\Item{(b)}
$\lim c_{n-1}/c_n$ exists (it will be $R$).
\itemskip\noindent
Then the following statements are equivalent:
\Item{(c)}
$\sum c_kc_{n-k} \sim 2C(R)c_n$.
\Item{(d)}
If $\omega=\omega(n)\to\infty$, then
$\sum_{k=\omega}^{n-\omega} c_kc_{n-k} = o(c_n)$.
\Item{(e)}
$\pclim$ exists.
(By Theorem~\ThmInfSup, we then have $\pclim>0$.)
\Item{(f)}
If the number of components in a random structure is $X_n$, then
for each fixed $d>0$
$$
\Pr(X_n=d) \sim {[y^{d-1}]\,A(R,y)\over A(R,1)}
\eqlabel\eqXnValue
$$
and
$$
{\rm E}(X_n) \sim 1
+ \left.{\partial A(R,y)\over A(r,1)\;\partial y}\right|_{y=1}.
\eqlabel\eqXnMean
$$
In particular, with $d=1$ in \eqXnValue, we have
$\pclim=1/A(R,1)=1/A(R)$.
\Endthing
\noindent
It may be possible to improve the theorem.
In particular, we make the following conjectures.
\conjecture\ConjaRatio
Theorem~\ThmLCandUC(b) can be replaced by
\Item{(b')}
$\lim a_{n-1}/a_n$ exists (it will be $R$).
\conjecture\ConjRhoImplies
The existence of $\rho$ implies (b).
\Endthing
\break
Some comments on the conditions in the theorem are in order:
\Bitem
The equivalence of (c) and (e) in the labeled case was given by
Embrechts~[\Embrechts] in a more general context involving probability
measures.
(A subexponential measure satisfying (b) and (c) is said to belong to $SD(R)$.)
\Bitem
In the labeled case, (f) asserts that $X_n-1$ is asymptotically Poisson
with $\lambda=C(R)$.
\Bitem
Conditions (a) and~(b) are not sufficient to deduce the existence of
$\pclim$.
To see this, define
$$
c_n = [2^n/n^{d(n)}]
\quad{\rm where}\quad
d(n)=2+9\min_k|n-2^k|/n.
\eqlabel\counterexample
$$
Then $c_{n-1}/c_n\sim1/2$ and $c_n=O(2^n/n^2)$.
Hence $R=1/2$ and $C(R)$ converges.
Let $m=2^k$ and note that
$c_m\sim 2^m/m^2$, $c_{2m}\sim 2^{2m}/(2m)^2$, and
$c_{3m}\sim 2^{3m}/(3m)^5$.
Hence $c_{3m} = o(c_mc_{2m})$ in violation of~(d).
Rudin~[\Rudin,~p.990] constructs a log-convex counterexample.
\Bitem
When $\lim c_{n-1}/c_n$ exists, perturbing the $c_n$'s by $o(c_n)$
does not affect the existence of $\pclim$.
To see this, note that the perturbations do not affect the validity
of (b) or~(d) in the theorem.
\itemskip
Knopfmacher and Knopfmacher's~[\KnopfK] abstract prime number theorem
for additive semigroups follows from case UC of Theorem~\ThmLCandUC\
since (a), (b), and~(d) are easily verified.
Compton~[\Compton] dealt with LC and UC in his Theorems~10
and~11, respectively.
He allowed either (a)~$c_{n-1}/c_n\to R$ or (b)~$a_{n-1}/a_n\to R$.
Our theorem is stronger than Compton's~(a) and would be stronger than
his~(b) if Conjecture~\ConjaRatio{} is true.
To see that our theorem is stronger than Compton's~(a), first note
that our theorem applies to
$$
a_n = \left[{x(n)\over R^n n^{\ln n}}\right]
~~\hbox{where $x(n)=1$ for UC and $x(n)=n!$ for LC,}
$$
but his does not.
Second, note that our (c) and hence his Theorems~10 and~11 follow
{from} the last sentence in his Lemma~9 by setting
$\alpha(x)=\beta(x)=\delta(x)=C(x)$.
Although some of Compton's results are weaker than ours, they may be
easier to apply since verifying (c) or (d) in our theorem may be
difficult.
In this connection, it should be noted that Lemma~2.4 of
Embrechts~[\Embrechts], which follows from Compton's result, also has
conditions that may be easier to verify.
\itemskip
Forests of various sorts provide easy examples for the application of
Theorem~\ThmLCandUC.
These and other graphical examples are discussed by
Compton~[\Compton] and by Knopfmacher and Knopfmacher~[\KnopfK] in
their interesting papers.
Inevitably, our examples overlap with these papers.
\medskip\noindent
{\bf Example 1}:~~
For forests of trees, $C(x)$ enumerates trees and $A(x)$ enumerates
forests.
The verification of (a) is trivial.
Crude asymptotic results on the number of trees are sufficient to
prove convergence, (b), and~(d); however, more refined asymptotics
are usually available.
Thus, when $C(R)$ converges, (a), (b), and (d) are easily verified
and so a nonvanishing fraction of the forests consist of a single
tree.
Here are some observations about certain types of trees.
\Bitem
{\bf Unlabeled Trees}:~~
Let $T_n$ (resp.\ $t_n$) be the number of unlabeled, $n$-vertex,
rooted (resp.\ unrooted) trees of some type.
See Harary, Robinson, and Schwenk~[\HararyRS] for information on
estimating $T_n$ and $t_n$.
In many cases, it can be shown that $T_n\sim An^{-3/2}R^{-n}$ and
$t_n\sim bn^{-5/2}R^{-n}$ and so our theorem applies.
\Bitem
{\bf Labeled Trees}:~~
In a variety of cases the exponential generating function for the
rooted enumerator satisfies $T(x)=x\varphi(T(x))$.
Under reasonable conditions on $\varphi$, one obtains
$T_n\sim An^{-3/2}R^{-n}n!$ and so the theorem applies.
Meir and Moon~[\MeirM] have strengthened (f) by showing that, when
$0\le\alpha<1$ and $d-\alpha n \sim \lambda n^{1/2}$, we have
$$
\Pr(X_n=d) \sim B_1e^{\lambda^2/2B_2}B_3^dB_4^n,
$$
where the $B_i$ depend on $\varphi$ and $\alpha$.
Compton~[\Compton,\thinspace p.\thinspace76] points out that the
generating functions need not be well behaved and gives the example
of rooted trees where the root must not be the centroid of a tree with
$2^k+1$ vertices.
In this case, the circle of convergence is a natural boundary for
$T(x)$, but Theorem~\ThmLCandUC\ and Compton's Theorem~10 still
apply.
\Bitem
{\bf Plane Trees}:~~
Again, the theorem applies in many cases, but there are interesting
cases that fall under UD.
Then one can show that $c_n/c_n^{(2)}\to0$ and so, by the result of
Cameron~[\Cameron] noted before Theorem~\ThmLCandUC, almost all
forests of such trees contain more than one tree.
We mention two examples.
Various people have studied achiral trees; that is, rooted plane
trees that are the same as their mirror images.
In this case, $t_n\sim 2^n/\sqrt{\pi n}$.
Odlyzko~[\Odlyzko] studied the asymptotics of 2,3-trees, that is,
trees in which each nonleaf node has 2 or 3 successors and all leaves
are at the same depth.
(The depth condition holds for each tree in the forest---not for the
forest as a whole.)
In this case, the asymptotics is more complicated:
$$
t_n \sim R^{-n}u(\ln n)/n,~~
\hbox{where $R<1$ and $u$ is periodic.}\disqed
$$
\medskip\noindent
{\bf Example 2}:~~
A {\it map\/} is an unlabeled graph embedded in a compact,
boundaryless surface so that all faces are homeomorphic to discs.
(The disc requirement implies that the graph is connected.)
Various types of maps have been studied; e.g., all maps, 2-connected
maps, Eulerian maps, and triangulations.
A rooting procedure destroys symmetries.
In many cases, it is known that the number of $n$-edged such maps is
asymptotic to
$$
A\,B^n/n^{1+5\chi/4}~~\hbox{(unrooted case)~~or~~}
4A\,B^n/n^{5\chi/4}~~\hbox{(rooted case)}
\eqlabel\eqMaps
$$
where $\chi$ is the Euler characteristic of the surface, $B$ depends
on the type of map, and $A$ depends on both the type of map and the
surface.
See~[\RichmondW] for a proof of \eqMaps\ for the unrooted case and
for further references.
Zvonkin~[\Zvonkin,~p.\thinspace290] remarks that it is sometimes
necessary in physics to consider maps which are not connected.
In that case, each component is embedded in a separate surface.
Since generating functions are often not available, analytic methods
cannot be applied; however, \eqMaps\ allows us to apply
Theorem~\ThmLCandUC\ when the surfaces are all spheres.
We omit details.
The result can be extended to surfaces whose genuses have some
fixed arbitrary sum:
There are only finitely many combinations of nonspherical surfaces
whose genuses add up to some fixed value.
These can then be combined with an arbitrary number of spheres.
For the nonspherical surfaces, we must consider sums of products of
series whose asymptotics have the form \eqMaps.
Consider a single term.
If it is a product of $k$ series where the $i$th has Euler
characteristic $\chi_i$, then $2+\sum(\chi_i-2)$ is the same for all
terms.
Since $2-\chi_i>0$, $\sum n_i=n$, and
$$
\prod n_i^{-5\chi_i/4}
= \biggl(\prod n_i^{5(2-\chi_i)/4}\biggr)
\biggl(\prod {1\over n_i}\biggr)^{10/4},
$$
it is straightforward to show that the coefficients will grow fastest
for the product containing only one factor.
This result can then be convolved with the result for the all-spheres
case.
Again, we omit details.\qed
\medskip
We conclude with some observations that may be of interest but are
not worth being called separate theorems.
The bound in (b) is the value of $\pclim$ in Theorem~\ThmLCandUC.
\theorem\ThmMisc
Suppose that $C_n>0$ for all sufficiently large $n$.
\Item{(a)}
If $\limsup_n c_n^{(2)}/c_n < \infty$, then $C(R)$ converges.
\Item{(b)}
If $\lim c_{n-1}/c_n = R$, then $\pcsup\le 1/A(R)$.
In particular, if $\lim c_{n-1}/c_n = R$ and $A(R)=\infty$, then
$\pclim=0$.
\Item{(c)}
In the labeled cases, $\sup_n c^{(2)}_n/c_n \le M$ implies that
$\pcinf\ge M/(e^M-1)$.
\Item{(d)}
Monotonicity is not very informative:
$C_n\ge1$ for all $n$ makes $A_n$ monotonic and, even if $C_n$ is
monotonic, $\pclim$ may not exist, as \counterexample\ shows.
\endthing
\section
Proof of Theorem \ThmInfSup{} Part I: Only Listed Values Can Occur
In this section we prove that only the values listed in
Theorem~\ThmInfSup{} for $(\pcinf,\pcsup)$ can occur.
The proof that these values actually do occur is deferred to the last
section because it involves a series of fairly lengthy constructions
and is not needed for the proof of the other theorems.
The case $R=0$ of Theorem \ThmInfSup{} was done by Bell~[\Bell], who
also showed that $\pclim=1$ implies $R=0$, from which it follows that
$\pcinf<1$ when $R\ne0$.
To show that only the claimed values can occur, it suffices to prove
the following lemma.
\lemma\LemmaOnlyValues
When $C(R)$ diverges, $\pcinf=0$.
When $R>0$ and $C(R)$ converges, $\pcsup>0$.
\Endthing
We require Theorem~3 of Stam~[\Stam]:
\theoremname{Stam}\ThmStam
Let $g(x)$ be a power series with nonnegative coefficients, $g(0)=0$,
and radius of convergence $R>0$.
Let $\sum q_n(y)x^n/n! = \exp\{yg(x)\}$.
Then
\Itemitem{(i)}
If $g(R)$ converges,
then $\limsup q_n(y)/q_n(1) >0$ for all $y>0$.
\Itemitem{(ii)}
If $R=\infty$ or $g(R)$ diverges,
then $\liminf q_n(y)/q_n(1) = 0$ for $0\le y<1$.
\endthing
\Proof{when $C(R)$ diverges}
We prove $\pcinf=0$ even when the $C_n$ are only required to be
nonnegative real numbers.
With the same values of $c_n$, the unlabeled $a_n$ is at least as
large as the labeled value because the exponential in
\eqUexp\ contains more terms than in \eqLexp.
Hence $\pcinf=0$ for the unlabeled case will follow from the labeled.
Apply Theorem~\ThmStam(ii) with
$g(x)=C(x)$.
We have $q_n(1)=A_n$ and
$$
q_n(y)
= n!\;[x^n]\,\Bigl(\exp(yC(x))\Bigr)
= n!\;[x^n]\,\Bigl(yC(x) + \ldots\Bigr)
= yC_n + \ldots.
$$
Thus $q_n(y)/q_n(1)\ge yC_n/A_n = y\pc{n}$.
By Theorem~\ThmStam(ii), the liminf of the left side is zero and so
$\pcinf=0$.\qed
\Proof{when $C(R)$ converges}
It suffices to prove that $\pclim=0$ is impossible.
We begin with the labeled case.
Apply Theorem~\ThmStam(i) with $g(x)=2C(x)$ and $y=1/2$ to conclude
that $\limsup q_n(1/2)/q_n(1)>0$.
We proceed by contradiction, assuming that $\pclim=0$.
{From} $xA'(x) = xC'(x)A(x)$, we have
$$
\eqalign{
q_n(1/2) = a_n
&= {1\over n} \sum_{k=0}^n k c_k a_{n-k}
= \sum_{k=0}^n {kc_k\over na_k} a_ka_{n-k}\cr
&< \sum_{k < n^{1/2}} n^{-1/2} a_ka_{n-k}
+ \sum_{k\ge n^{1/2}} (c_k/a_k) a_ka_{n-k}\cr
&= o(1)\sum_{k=0}^n a_ka_{n-k}
= o(1)\,q_n(1),\cr}
$$
contradicting $\limsup q_n(1/2)/q_n(1)>0$.
We now consider the unlabeled case.
Since the coefficients of $C(x)$ are nonnegative integers, $0z$ whenever
$n>N(z)$.
Let
$$
H(x) = \sum_{k=1}^\infty{C(x^k)\over k}
\quad{\rm so}\quad
h_n = \sum_{d|n}{c_{n/d}\over d}.
$$
One easily has that $H(x)$ converges on the circle of convergence
since $C(x)$ does.
By case LC, $\pcsup>0$.
Hence there is an $\epsilon>0$ and an infinite set $\cal N$ of
positive integers such that $h_n/a_n>\epsilon$ for $n\in\cal N$.
Suppose that $n\in\cal N$ and $n>2N(z)$.
Using $A'(x) = H'(x)A(x)$ we have
$$
a_n
= {1\over n}\sum_{k=1}^n kh_k a_{n-k}
\ge h_n
+ \sum_{\textstyle{d|n\atop d>1}} {h_{n/d} a_{n-n/d}\over d}
\ge h_n
+ z\sum_{\textstyle{d|n\atop d>1}} {h_{n/d}\over d}.
$$
Since $n\in\cal N$, it follows that $a_n1}} {h_{n/d}\over d}
1}}{\mu(d)h_{n/d}\over d}.
$$
Since $|\mu(d)|\le1$, $c_n-h_n=o(h_n)$ as $n\to\infty$ through
$\cal N$.
Hence $c_n/a_n\ge\epsilon$ for all sufficiently large
$n\in\cal N$.\qed
\section Proof of Theorem \ThmLCandUC
We will show
$$
\hbox{(c)}\Longleftrightarrow
\hbox{(d)}\Longrightarrow
\hbox{(f)}\Longrightarrow
\hbox{(e)}\Longrightarrow
\hbox{(c)}.
$$
Since (e) is contained in the last part of (f), the proof that (f)
implies (e) is trivial.
\Proof{of (c) and (d) equivalence}
Note that for fixed $\omega$
$$
\sum_{k\le\omega}c_kc_{n-k}
\sim \sum_{k\le\omega} c_k R^k c_n
= (C(R)-E(\omega))c_n,
$$
where $E(\omega)\to0$ as $\omega\to\infty$.
By a diagonal argument, it follows that for
all sufficiently slowly growing $\omega=\omega(n)$ we have
$$
\sum_{k\le\omega}c_kc_{n-k} \sim C(R) c_n.
$$
Since, for fixed $n$, the sum in (d) is monotonic decreasing
in $\omega$, the equivalence of (c) and (d) follows.\qed
\Proof{that (d) implies (f)}
We begin by proving the implication for case LC in three steps:
\Item{(i)}
$c_n^{(d)} < K^{d-1} c_n$ for some $K$ and all sufficiently large $n$.
\Item{(ii)}
$c_n^{(d)} \sim dC(R)^{d-1}c_n$ uniformly for $d\le D(n)$, where
$D(n)\to\infty$ suffciently slowly.
\Item{(iii)} $a_n\sim A(R,1)c_n$.
\itemskip
\noindent
Equation \eqXnValue\ will then follow:
\Bitem
$[y^d]\;A(x,y)=C(x)^d/d!$ counts the number of structures having
exactly $d$ components,
\Bitem
(ii) tells us that
$[x^n]\,\left({C(x)^d\over d!}\right)
\sim {C(R)^{d-1}c_n\over(d-1)!}$, which equals
$[y^{d-1}]\;A(r,y)c_n$, and
\Bitem
(iii) tells us that $c_n/a_n\sim A(R,1)$.
\itemskip\noindent
We also obtain \eqXnMean:
$$
\eqalignno{
a_n{\rm E}(X_n)
&= [x^n]\,\left.{\partial A(x,y)\over\partial y}\right|_{y=1}
= [x^n]\;C(x)e^{C(x)}
= \sum [x^n]\,\left({C(x)^{d+1}\over d!}\right)\cr
&\sim \sum_{0\le d0$ and $b_n=1$ if $c_n=0$.
Since $c_n>0$ when $n>N$, it follows that (b) and (d) hold for the
$b_n$'s.
Hence (c) holds and so, since $b_n>0$ for all $n$, we have
$$
b_n^{(2)} < K b_n
~~\hbox{for some $K$ and all $n\ge0$.}
$$
Inducting on $d$, we have $b_n^{(d+1)} < K^d b_n$ because
$$
b_n^{(d+1)} = \sum_{k=0}^n b_k\,b_{n-k}^{(d)}
< \sum_{k=0}^n b_k K^{d-1} b_{n-k}
= K^{d-1} \sum_{k=0}^n b_k b_{n-k}
< K^db_n.
$$
Since $b_k\ge c_k$ and $c_n=b_n$ for $n>N$, (i) is proved.
By a diagonal argument, is suffices to prove (ii) for fixed $d$,
which we now do by induction on $d$.
The case $d=1$ is trivial.
By definition
$$
c_n^{(d+1)} = \sum_{k=0}^n c_k^{(d)} c_{n-k}.
$$
We split the sum into three pieces for $n\to\infty$ and
fixed large $\omega$:
$$
\eqalignno{
\sum_{k<\omega} c_k^{(d)} c_{n-k}
&\sim \sum_{k<\omega} c_k^{(d)} R^k c_n
&\hbox{by (b)},\cr
\sum_{k<\omega} c_{n-k}^{(d)} c_k
&\sim \sum_{k<\omega} dC(R)^{d-1}c_{n-k} c_k
&\hbox{by induction}\cr
&\sim dC(R)^{d-1} \sum_{k<\omega} c_n R^k c_k
&\hbox{by (b)},\cr
\sum_{k=\omega}^{n-\omega} c_k^{(d)} c_{n-k}
& \le K^{d-1} \sum_{k=\omega}^{n-\omega} c_k c_{n-k}
&\hbox{by (i)}.\cr}
$$
By a diagonal argument, if $\omega=\omega(n)\to\infty$
sufficiently slowly, the three sums
are asymptotically $C(R)^d c_n$, $dC(R)^{d-1}C(R)c_n$ and $o(c_n)$,
respectively.
(The first two since $C(R)$ converges and the last by (d).)
This completes the induction.
Step (iii) is simple:
Since $A(x) = \sum C(x)^d/d!$, we can apply (ii) to those $d1}C(x^d)A(x,1).\cr}
$$
By \LCMean, $[x^n]\;C(x)e^{C(x)} \sim c_ne^{C(R)}(C(R)+1)$.
Since $U(x,1)$ and $\sum_{d>1} C(x^d)$ converge for $x1}C(R^d)a_n.
$$
Since $c_ne^{C(R)}U(R,1) = c_nA(R,1)\sim c_n$, the proof is
complete.\qed
\Proof{that (e) implies (c)}
We first prove (c) for case LC.
Throughout, $\omega$ denotes of function of $n$ that goes to infinity
in a sufficiently slow manner.
{From} $A'(x) = C'(x) A(x)$ and the fact that $\pclim\ne0$ we have
$$
na_n = \sum_{k=0}^n kc_k a_{n-k}
\sim \sum_{k>\omega} kc_k a_{n-k}
\sim \sum_{k>\omega} k\pclim a_k a_{n-k},
$$
where we could neglect the terms less that $\omega$ as long as
$\omega=o(n)$ because for $k\le\omega$ and $n$ large
$$
kc_ka_{n-k} \le \omega a_ka_{n-k} = o((n-k)a_{n-k}a_k)
$$
and $(n-k)a_{n-k}a_k$ is included in the second sum over $k>\omega$.
Similarly, we can restore such terms to obtain
$$
\eqalign{
na_n
&\sim \pclim \sum_{k=0}^n ka_k a_{n-k}\cr
&={\pclim\over2}\biggl(
\sum_{k=0}^n ka_k a_{n-k}
+ \sum_{k=0}^n (n-k)a_{n-k}a_k\biggr)\cr
&= {n\pclim\over2}\sum_{k=0}^n a_k a_{n-k}.\cr}
$$
Hence
$$
a_n
\sim {\pclim\over2}\sum_{k=0}^n a_k a_{n-k}
= {\pclim\, a_n^{(2)}\over2}.
\eqlabel\eqatwo
$$
{From} \eqatwo\ and a ``diagonal'' argument,
$$
\eqalign{c_n
&\sim \pclim a_n
\sim {\pclim^2 a_n^{(2)}\over 2}\cr
&= \pclim c_n \sum_{k<\omega} a_k {c_{n-k}\over c_n}\,
{\pclim a_{n-k}\over c_{n-k}}
+ {1\over2} \sum_{k=\omega}^{n-\omega}c_kc_{n-k}{\pclim a_k\over c_k}\,
{\pclim a_{n-k}\over c_{n-k}}\cr
&\sim \pclim c_n \sum_{k<\omega} a_kR^k
+ {1\over2} \sum_{k=0}^n c_kc_{n-k}
- c_n\sum_{k<\omega}c_k{c_{n-k}\over c_n}\cr
&\sim \pclim c_n A(R) + L_n c_n - c_n C(R),\cr}
$$
where $L_n$ is defined by $\sum c_kc_{n-k} = 2L_n c_n$.
Factoring out $c_n$, we see that
$$
1 \sim \pclim A(R) + L_n - C(R)
~~\hbox{and so}~~
L_n\sim L = 1+C(R)-\pclim A(R).
$$
Solving for $\pclim A(R)$ gives
$$
\pclim A(R) = 1 + C(R) - L.
\eqlabel\eqACLrho
$$
Now consider replacing $c_n$ by $2c_n$ and $a_n$ by $a_n^{(2)}$.
{From} \eqatwo, the hypotheses of the theorem are still valid provided we
replace $\pclim$ by $\pclim^2$.
Hence \eqACLrho\ still holds with the appropriate values for $A(R)$,
$C(R)$, and $L$, namely $A(R)^2$, $2C(R)$ and $2L$.
Thus
$$
\pclim^2A(R)^2 = 1 + 2C(R) - 2L.
$$
Equating this to the square of \eqACLrho\ we obtain
$(1+\delta)^2 = 1+2\delta$ where $\delta = C(R)-L$.
Hence $\delta=0$.
We now prove the implication for the case UC.
Since $\pclim$ exists and is nonzero, it follows from (a) that
$a_{n-1}/a_n\sim R$.
Let $U(x,y)$ be as in \eqUdef\ and recall that $U(x,1)$ converges for
$x0$ for
sufficiently large $n$.\qed
\Proof{of (b)}
Since $A(0)=1$, there is nothing to prove when $R=0$.
We now show that it suffices to deal with the labeled cases.
In case UD, $A(R)=\infty$.
Hence the result for case LD implies the result for case UD.
In case UC, let
$$
b_n = \min\Bigl([x^n]\,e^{C(x)},\; e^{C(R)}c_n\Bigr).
$$
It follows from case LC that
$\limsup\bigl(c_n/[x^n]\,e^{C(x)}\bigr)\le 1/e^{C(R)}$.
Hence $b_n\sim e^{C(R)}c_n$.
{From} Theorem~\ThmSchur,
$$
[x^n]\Bigl(B(x)\exp\Bigl\{
{\textstyle\sum_{k\ge2} C(x^k)/k}\Bigr\}\Bigr)
\sim \exp\Bigl\{
{\textstyle\sum_{k\ge2} C(R^k)/k}\Bigr\} b_n
\sim A(R)c_n.
$$
Since $C(x^k)$ has nonnegative coefficients and
$0\le b_n\le [x^n]\,e^{C(x)}$,
$$
[x^n]\Bigl(B(x)\exp\Bigl\{
{\textstyle\sum_{k\ge2} C(x^k)/k}\Bigr\}\Bigr)
\le a_n.
$$
Combining the last two displayed equations gives
$\limsup c_n/a_n\le 1/A(R)$.
We now prove the labeled cases.
Fix $00$.
Our proof consists of a variety of constructions which are dealt with
in a series of lemmas.
All our constructions produce integers $C_n\ge0$ which are nonzero for
sufficiently large $n$.
Here is how the lemmas deal with the various parts:
\Bitem
Lemma 2 proves all cases when $\pcinf=0$ and $\pcsup=1$.
\Bitem
Lemma 5 proves the convergent case for $0\le\pcinf\le\pcsup<1$.
\Bitem
Lemma 6 proves the convergent case for $0<\pcinf<\pcsup=1$.
\Bitem
Lemma 7 proves the divergent case when $\pcsup<1$.
\itemskip
\noindent
As always, assume that $C(x)$ and $A(x)$ are related by \eqLexp{}
and~\eqUexp.
Define
$$
\tau(n) = \cases{
1,& in the unlabeled case,\cr
n!,& in the labeled case.\cr}
$$
\lemma\LemmaZeroOne
Fix $R>0$ subject to the constraints discussed at the beginning of
Section~2.
In all four cases LC, UC, LD and UD, there are positive integers
$C_n$ such that $C(R)$ has radius of convergence $R$, $\pcinf=0$, and
$\pcsup=1$.
\endthing
\proof
Set
$$
\def\downer{\vphantom{{}_{\textstyle)}}}
E_n = \cases{
[\tau(n)/n^2R^n]\downer & for the convergent cases,\cr
[n!/(\ln n)^{1/4}]\downer& for the $R=\infty$ case,\cr
[\exp(n^{3/4})]\downer & for the unlabeled $R=1$ case,\cr
[\tau(n)/R^n] & for the remaining divergent cases.\cr
}
$$
We will set $C_n=1$ for most values of $n$.
For the exceptional values of $n$ (which will be specified later), we
set $C_n=E_n$.
Since $C_n\ge1$, it follows that $A_n\to\infty$.
Because there will be infinitely many nonexceptional indices, we have
$\pcinf=0$.
We prove that, if only finitely many values of $n$ are
exceptional, then $A_n/E_n\to0$.
Let $K$ be an integer such that $C_n\le K$ for all $n$.
In the labeled case with $r=1/\ln n$,
$$
A_n/n!
\le [x^0]\,\bigl(x^{-n}e^{K(e^x-1)}\bigr)
< r^{-n}e^{Ke^r}
= (e^K/\ln n)^n,
\eqlabel\eqBellNos
$$
and so $A_n/E_n\to0$ in this case.
In the unlabeled case, $A_n$ is bounded by the $K$-fold convolution
of the partition function $p_n=\exp\bigl(O(n^{1/2})\bigr)$ with
itself.
This convolution is bounded by
$(n+1)^{K-1}p_n^K = \exp\bigl(O(n^{1/2})\bigr)$, and so
$A_n/E_n\to0$.
Denote the indices of the exceptional $C_n$ by $n_1,n_2,\ldots$.
Set $n_1=3$.
Suppose $n_i$ has been chosen for $in_{k-1}+1$ so that
$\tilde A_n/E_n<1/k$.
Choose such an $n$ for $n_k$ and note that, for $n=n_k$,
the new value of $A_n$ is $E_n-1$ larger than $\tilde A_n$ since the
only change to $C(x)$ was to increase it by $(E_n-1)x^n/\tau(n)$.
Thus
$$
{C_n\over A_n} = {E_n\over A_n} = {E_n\over(E_n-1)+\tilde A_n}
> {1\over1+1/k}.
$$
Since we make no more changes in $C_j$ for $j\le n_k$, it follows
that $C_n/A_n$ will not change and so $\pcsup=1$.\qed
\lemma\LemmaCOne
Suppose that $\alpha>0$, $\xi>1$, $p>1$, $R>0$, and that $\cal A$ is an
infinite set of positive integers forming an arithmetic progression.
Then there are nonnegative integers $C_n$ such that
\Itemitem{(i)}
$C_n=0$ for $n\not\in\cal A$,
\Itemitem{(ii)}
$C_n\sim\alpha\,\tau(n)/n^pR^n$ for $n\in\cal A$, and
\Itemitem{(iii)}
$A(R) = \xi$.
\endthing
\proof
Find an $N\in\cal A$ such that setting
$$
C_n =\cases{
\alpha\,\tau(n)/n^pR^n, & if $n\ge N$ and $n\in\cal A$,\cr
0, & otherwise,\cr}
$$
leads to $A(R)\le\xi$.
Increase $C_N$ so that $A(R)=\xi$.
Call this sequence $C_n^{[N]}$.
Let $l0} \delta R^{ik}/k = -\delta\,\ln(1-R^i).
$$
Hence
$$
x_k = \{C_l^{[l]}\} {\ln(1-R^l)\over\ln(1-R^k)} = O(R^{l-k}) = O(1).
$$
Thus $x_k = o\left(C_k^{[k]}\right)$.
Note that $C_n^{[m]}$ changes for at most two values of $m$:
once for $m=n$ and once for the preceding element in $\cal A$.
Let $C_n$ be value of $C_n^{[m]}$ for $m>n$.\qed
\lemma\LemmaCTwo
Suppose $a,\,b,\,d,\,\alpha,\,R$ are all greater than zero, $p,\,q$
are greater than one, and $a^2+2a > b^2$.
Then there are nonnegative integers $C_n$ with
$$
C_n\sim\cases{
\displaystyle{\alpha\,\tau(n)\over n^p R^n}_{\vphantom)},
& if $n$ is even,\cr
\displaystyle{\alpha d\,\tau(n)\over n^q R^n}^{\vphantom)},
& if $n$ is odd,\cr}
$$
$$
\sum_{n\ge0} {A_{2n}R^{2n}\over\tau(2n)} = 1 + a,
\quad{\rm and}\quad
\sum_{n\ge0} {A_{2n+1}R^{2n+1}\over\tau(2n+1)} = b,
$$
where $A(x)$ is given by \eqLexp\ or \eqUexp.
\endthing
\proof
The last displayed equations are equivalent to
$$
A(R) = 1 + a + b
\quad{\rm and}\quad
A(-R) = 1 + a - b.
$$
Call these values $A^+$ and $A^-$, respectively.
Since
$$
A^+A^- = (1+a+b)(1+a-b) = (1+a)^2-b^2 > 1,
$$
it follows by Lemma~\LemmaCOne{} that we can find
$\tilde C_n$ vanishing at odd $n$ and asymptotic to
$\alpha\,\tau(n)/n^pR^n$ at even $n$ such that
$\tilde A(R)=\sqrt{A^+A^-}$.
Since $A^+/A^->1$, it again follows that we can find
$\hat C_n$ vanishing at even $n$ and asymptotic to
$\alpha d\,\tau(n)/n^qR^n$ at odd $n$ such that
$\hat A(R)=\sqrt{A^+/A^-}$.
Let $C_n=\tilde C_n+\hat C_n$.
Then $A(x)=\tilde A(x)\hat A(x)$ and so
$$
A(R) = \tilde A(R)\hat A(R) = A^+
\quad{\rm and}\quad
A(-R) = \tilde A(-R)\hat A(-R) = \tilde A(R)/\hat A(R) = A^-.
\disqed
$$
\lemma\LemmaCMost
Suppose $R>0$, $1>\pcsup\ge\pcinf\ge0$ and $\pcsup>0$.
In the unlabeled case, also suppose $R<1$.
Then there are integers $C_n$ such that function $C(x)$ has radius of
convergence $R$, $C(R)$ converges,
$\liminf_{n\to\infty}C_n/A_n=\pcinf$, and
\hbox{$\limsup_{n\to\infty}C_n/A_n=\pcsup$}.
\endthing
\proof
We begin by choosing values to use in Lemma~\LemmaCTwo, according as
whether $\pcinf=0$ or not.
Suppose $\pcinf=0$.
Let $d=1$, $a=(1/\pcsup)-1$, $\alpha=1$, $p=2$, $q=3$ and $b=a$.
Now suppose $\pcinf>0$.
Let $\alpha=1$, $p=q=2$, $\mu=(1/\pcsup)-1$ and $\nu=(1/\pcinf)-1$.
Note that $\nu\ge\mu>0$.
If $\mu=\nu$, let $d=1$ and $a=b=\mu/2$; otherwise, we claim that for
sufficiently small $d$ there exist $a,\,b>0$ such that $a(a+2) > b^2$
and
$$
\pmatrix{1&d\cr1&1/d\cr}\pmatrix{a\cr b\cr}
= \pmatrix{\mu\cr\nu\cr}.
$$
To see this, solve and note that, as $d\to0$, we have
$a\sim\mu$ and $b\sim(\nu-\mu)d$.
Choose such a small $d$.
Using the values in the preceding two paragraphs, apply Lemma~\LemmaCTwo.
Choose $k$ such that $a_k>0$, and $a_{k-1}>0$ and suppose $n>2k$.
Let $H(x)=\ln A(x)$.
{From} $A'(x)=H'(x)A(x)$, we have
$$
na_n = \sum (n-k) h_{n-k} a_k.
\eqlabel\eqAandH
$$
Hence
$$
na_n = \sum (n-i)h_{n-i}a_i
\ge (n/2)(a_kc_{n-k} + a_{k-1}c_{n-k+1})
=\Theta(1/nR^n).
\eqlabel\eqAnLowerBound
$$
Replacing $C_n$ with larger values that are asymptotic to
$\alpha\max(1,d)\tau(n)/n^2R^n$ increases the value of $a_n$ and
allows us to use Theorem~\ThmLCandUC\ to conclude that the new $a_n$,
and hence the old $a_n$, are $O(1/n^2R^n)$.
Combining this with \eqAnLowerBound, we have
$$
A_n=\Theta(\tau(n)/n^2R^n).
\eqlabel\eqThetaA
$$
In the labeled case, $h_n=c_n$ and in the unlabeled case
$$
h_n = \sum_{d|n}{c_d\over n/d}
= c_n + O\biggl(\sum_{d\le n/2} R^{-d}\biggr)
= c_n + O(R^{-n/2}),
$$
and so $h_n\sim c_n$.
{From} this and \eqAandH, it follows easily that
$$
a_n
\sim c_n\sum_{k~{\rm even}}a_kR^k
+ c_{n-1}\sum_{k~{\rm odd}}a_kR^{k-1}
= c_n(1+a) + c_{n-1}{b\over R}.
\eqlabel\eqSplitSum
$$
We now use this, treating $\pcinf>0$ and $\pcinf=0$ separately.
For $\pcinf>0$
$$
{a_{2n}\over c_{2n}}
\sim (1+a) + {c_{2n-1}b\over Rc_{2n}}
\sim 1 + a + {b\over d} = 1 + \mu = {1\over\pcinf}
$$
and, similarly, $a_{2n+1}/c_{2n+1}\sim 1/\pcsup$.
For $\pcinf=0$, we have $a_{2n}/c_{2n} \sim 1 + a = 1/\pcsup$ from
\eqSplitSum, and, from \eqThetaA{} and the
asymptotics for $C_{2n+1}$, $C_{2n+1}/A_{2n+1}\to0$.\qed
\lemma\LemmaCRest
In both the labeled and unlabeled convergent cases, if $0<\lambda<1$,
there are integers $C_n$ tending to infinity such that $C(x)$ has
radius of convergence $R$, $\pcinf=\lambda$, and $\pcsup=1$.
\endthing
\proof
Let $\zeta_n=\tau(n)R^{-n}/n^{\nu(n)}$ where
$$
\nu(n) = 3-\sum_{i=1}^{\log_3(\log_3 n)}2^{-i}.
$$
Find an $N>0$ such that setting
$$
C_n = \cases{
\zeta_n,& for $n\ge N$,\cr
0,& otherwise,\cr}
$$
leads to $A(R)\le 1/\lambda$.
Increase $C_N$ so that $A(R)=1/\lambda$.
Call this sequence $C_n^{[N]}$.
Proceed as in the proof of Lemma~\LemmaCOne{} so as to obtain a
sequence of integers $C_n$ with $C_n\sim\zeta_n$ and $A(R)=1/\lambda$.
Clearly $C(x)$ has radius of convergence $R$ and converges at $R$.
We now show that $\pcinf=1/A(R)$.
Let $H(x)=\ln A(x)$.
As in the proof of Lemma~\LemmaCMost, $h_n\sim c_n$.
Let $\hat h_k = h_k k^{\nu(k)-\nu(n)}$.
{From} $na_n=\sum kh_ka_{n-k}$, we have
$$
na_n
\le \sum k \hat h_k a_{n-k}
\sim n \hat h_n A(R)
\sim n c_n A(R).
$$
Hence $\pcinf\ge1/A(R)$.
Letting $n\to\infty$ through $n=3^{3^k}-1$, one easily sees that
$na_n\sim h_nA(R)$ and so $\pcinf=1/A(R)$.
We now show that $\pcsup=1$.
Let $n\to\infty$ through $n=3^{3^k}$.
For such an $n$, let $\tilde c_n=c_n/n^{\nu(n-1)-\nu(n)}$ and let
$\tilde a_n$ be the value of $a_n$ obtained when $c_n$ is replaced by
$\tilde c_n$.
By the argument in the preceding paragraph,
$\tilde c_n/\tilde a_n\to\pcinf$.
Since $A(x)=e^{H(x)}$ and since $H(x)$ and
$\tilde H(x) + (c_n-\tilde c_n)x^n$ agree through terms of degree $n$,
we have $a_n = \tilde a_n + (c_n-\tilde c_n)$.
Thus
$$
{c_n\over a_n} = {1\over1+(\tilde a_n/\tilde c_n-1)\tilde c_n/c_n}
\sim{1\over1+(1-1/\pcinf)\tilde c_n/c_n}.
$$
Since $n=3^{3^k}$ and $\nu(n)-\nu(n-1)=2^{-k}$, we have
$$
{\tilde c_n\over c_n} \sim (3^{3^k})^{-2^{-k}}
= 3^{-(3/2)^k} \to 0.
$$
Thus $\lim_{k\to\infty}c_n/a_n=1$ where $n=3^{3^k}$.\qed
\lemma\LemmaDNotOne
Suppose $R>0$ and $0<\alpha<1$.
In the the labeled and unlabeled cases, there are integers $C_n>0$
such that the function $C(x)$ has radius of convergence $R$, $C(R)$
diverges, and $\pcsup=\alpha$.
\endthing
\proof
Define $\beta=(1-1/\alpha)^{-1}$ and
$$
R_n = \cases{
(\ln n)^{n/2},& if $R=\infty$,\cr
\exp(-n^{-1/3})\vphantom{\Bigl(}, & if unlabeled and $R=1$,\cr
R,& otherwise.\cr
}
$$
Let $C_n^{[1]}=1$ for all $n>1$ and let $C_1^{[1]}$ be any integer
greater than $1/\alpha R$.
If $C_n^{[k-1]}$ has been defined for all $n$, let $A_n^{[k-1]}$ be
the corresponding $A(x)$ sequence and let
$$
C_n^{[k]} = \cases{
C_n^{[k-1]}, & if $n\ne k$,\cr
C_k^{[k-1]},\vphantom{\Bigl(} &
if $n=k$ and $A_k^{[k-1]}\ge\tau(k)/R_k^k$,\cr
\left\lceil\beta\tau(k)A_k^{[k-1]}\right\rceil, & otherwise.\cr
}
\eqlabel\eqCnkDefn
$$
Since $C_n^{[k]}$ is unchanging for $k>n$, we define $C_n=C_n^{[n+1]}$.
Let $\cal K$ be the set of $k$ for which the third alternative is used.
We will show that
\Item{(a)}
$\cal K$ is infinite.
\Item{(b)}
The radius of convergence of $C(x)$ is at least $R$.
\Item{(c)}
$\lim_{n\to\infty}C_n/A_n=\alpha$, where the limit is taken through
$n\in\cal K$.
\Item{(d)}
$C(R)=\infty$.
\itemskip\noindent
The lemma follows immediately from these claims.
To prove (a), it suffices to show that
$\lim_{n\to\infty} A_n^{[k]}R_n^n/\tau(n)=0$.
In the labeled case, $A^{[k]}(x) =\exp(p(x)+e^x-1)$, where $p(x)$ is
a polynomial with no constant term.
Proceeding as in \eqBellNos, we obtain
$$
A_n^{[k]}/n! < \exp\bigl(p(\ln n)\bigr)\times(e/\ln n)^n
= o\bigl(1/(\ln n)^{n/2}\bigr).
$$
By the definition of $R_n$, this completes the proof of (a) for the
labeled case.
In the unlabeled case,
$A^{[k]}(x)$ equals the partition generating function $p(x)$ times
finitely many factors of the form $(1-x^i)^{-b_i}$.
Hence there are constants $B$ and $l$ depending on the $b_i$ such that
$$
\eqalign{
A_n^{[k]}
&\le [x^n]\;\left({p(x)\over(1-x)^l}\right)
\le [x^n]\;\left({1\over(1-x)^l}\,{p_n\over1-x}\right)\cr
&\le n^{l+1}p_n
= o\bigl(\exp(n^{2/3})\bigr)
= O\Bigl(\bigl(\exp(-n^{-1/3})\bigr)^{-n}\Bigr).\cr
}
$$
This completes the proof of (a).
{From} the definition of $C_n^{[k]}$, it follows that
$C_n^{[k]}<1+\beta\tau(n)/R_n^n$ for all $k$ and $n$.
This proves (b).
To prove (c) we use
$A_k^{[k]} = A_k^{[k-1]} - C_k^{[k-1]} + C_k^{[k]}$.
When $k\in\cal K$, $C_k^{[k-1]}=1/\tau(k)$ and
$C_k^{[k]}$ differs from $\beta A_k^{[k]}$ by less than 1.
Hence $C_k^{[k]}/A_k^{[k]}\sim\beta/(1+\beta)=\alpha$.
Finally, we prove that $C(R)=\infty$.
It suffices to show that the middle condition in \eqCnkDefn{} holds
infinitely often.
Suppose not.
It follows from (c) that $\pclim$ exists and equals $\alpha$.
With $H(x)=\ln A(x)$ we have $A'(x)=H'(x)A(x)$ and so
$$
na_n = \sum_{k=1}^nkh_ka_{n-k} \ge (n-1)h_{n-1}a_1
\ge (n-1)c_{n-1}a_1 = (n-1)c_{n-1}C_1.
$$
Hence $a_n/c_n \ge C_1(1-1/n)c_{n-1}/c_n$ and so
$$
{1\over\alpha} = \lim_{n\to\infty}{a_n\over c_n}
\ge C_1\limsup_{n\to\infty}{c_{n-1}\over c_n}.
$$
Since $\limsup_{n\to\infty}|b_{n-1}/b_n|$ is at least the radius of
convergence of a power series $\sum b_nx^n$ and since
$C_1>1/(\alpha R)$, we have
$1/\alpha > (1/(\alpha R))R$, a contradiction.\qed
\break
\frenchspacing
\nonumsection References
\item{[\ArratiaBT]}
R. Arratia, A. D. Barbour, and S. Tavar\'e,
{\it Notices AMS\/} {\bf 44} (1997) 903--910.
\Item{[\Beissinger]}
J. S. Beissinger, The enumeration of irreducible combinatorial
objects, {\it J. Combin. Theory, Ser.~A\/} {\bf 38} (1985)
143--169.
\Item{[\Bell]}
J. P. Bell, When structures are almost surely connected,
{\it Electron. J. Combin.} submitted.
\Item{[\Bender]}
E. A. Bender, Asymptotic methods in enumeration,
{\it SIAM Rev.} {\bf 16} (1974), 485-515.
\Item{[\BenderCOR]}
E. A. Bender, P. J. Cameron, A. M. Odlyzko, and L. B. Richmond,
Connectedness, classes and cycle index, {\it Combin., Probab. and
Comput.} {\bf 8} (1999) 31--43.
\Item{[\Burris]}
S. Burris, Spectrally determined first-order limit laws,
{\it DIMACS Series in Discrete Math.\ and Theoret.\ Comput.\ Science}
{\bf 33} (1997)33--52.
\Item{[\BurrisCOR]}
S. Burris, K. Compton, A. Odlyzko, and B. Richmond,
Fine spectra and limit laws II. First-order 0-1 laws,
{\it Canad. J. Math.} {\bf 49} (1997) 641--652.
\Item{[\BurrisS]}
S. Burris and A. S\'ark\"ozy,
Fine spectra and limit laws I. First-order laws,
{\it Canad. J. Math.} {\bf 49} (1997) 468--498.
\Item{[\Cameron]}
P. J. Cameron, On the probability of connectedness,
{\it Discrete Math.} {\bf 167/168} (1997) 175--187.
\Item{[\Compton]}
K. J. Compton, Some methods for computing component distribution
probabilities in relational structures, {\it Discrete Math.} {\bf 66}
(1987) 59--77.
\Item{[\Embrechts]}
P. Embrechts, The asymptotic behaviour of series and power series
with positive coefficients,
{\it Med. Konink. Acad. Wetensch. (Brussels)\/} {\bf 45} (1983)
41--61.
\Item{[\FlajoletN]}
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing
partitions, {\it INRIA\/} Rpt. No.~3196 (1997).
\Item{[\FlajoletS]}
P. Flajolet and M. Soria, Gaussian limiting distributions for the
number of components in combinatorial structures, {\it J. Combin.
Theory, Ser.~A\/} {\bf 53} (1990) 165--182.
\Item{[\Gourdon]}
X. Gourdon, Largest component in random combinatorial structures,
{\it Discrete Math.} {\bf 180} (1998) 185--209.
\Item{[\HararyRS]}
F. Harary, R. W. Robinson, and A. J. Schwenk, Twenty-step algorithm
for determining the asymptotic number of trees of various species,
{\it J. Austral. Math. Soc., Ser.~A\/} {\bf 20} (1975) 483--503.
\Item{[\Hayman]}
W. K. Hayman, A generalisation of Stirling's formula, {\it J. Reine
Angew. Math.} {\bf 196} (1956) 67--95.
\Item{[\Hwang]}
H.-K. Hwang, A Poisson * geometric convolution law for the number of
components in unlabelled combinatorial structures, {\it Combin.,
Probab. and Comput.} {\bf 7} (1998) 89--110.
\Item{[\KnopfK]}
A. Knopfmacher and J. Knopfmacher, Arithmetical semigroups related to
trees and polyhedra, {\it J. Combin. Theory, Ser.~A\/} {\bf 86}
(1999) 85--102.
\Item{[\MeirM]}
A. Meir and J. W. Moon, The asymptotic behaviour of coefficients of
certain generating functions, {\it Europ. J. Combin.} {\bf 11}
(1990) 581--587.
\Item{[\Odlyzko]}
A. M. Odlyzko, Periodic oscillations of coefficients of power series
that satisfy functional equations, {\it Adv. Math.} {\bf 44} (1982)
180--205.
\Item{[\Promel]}
H. J. Pr\"omel, Counting unlabeled structures, {\it J. Combin.
Theory, Ser.~A\/} {\bf 44} (1987) 83--93.
\Item{[\RichmondW]} L.B. Richmond and N.C. Wormald,
Almost all maps are asymmetric, {\it J. Combin. Theory, Ser.~B\/}
{\bf 63} (1995) 1--7.
\Item{[\Rudin]}
W. Rudin, Limits of ratios of tails of measures, {\it Ann. Probab.}
{\bf 1} (1973) 982--994.
\Item{[\Stam]}
A.J. Stam, Polynomials of binomial type and compound Poisson
Processes, {\it J. Math. Anal. Appl.} {\bf 130} (1988) 493--508.
\Item{[\WrightL]} E. M. Wright, A relationship between two sequences,
{\it Proc. London Math. Soc.} (iii) {\bf 17} (1967) 296--304.
\Item{[\WrightU]} E. M. Wright, A relationship between two sequences
III, {\it J. London Math. Soc.} {\bf 43} (1968) 720--724.
\Item{[\WrightG]} E. M. Wright, Asymptotic relations between
enumerative functions in graph theory, {\it Proc. London Math. Soc.}
(iii) {\bf 20} (1970) 558--572.
\Item{[\Zvonkin]} A. Zvonkin, Matrix integrals and map enumeration:
An accessible introduction, {\it Mathl. Comput. Modeling\/} {\bf 26}
(1997) 281--304.
\bye