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

Jason P. Bell Department of Mathematics University of California, San Diego La Jolla, CA 92903-0112, USA

                        (email: jbell@math.ucsd.edu)

Edward A. Bender Department of Mathematics University of California, San Diego La Jolla, CA 92903-0112, USA

                          (email: ebender@ucsd.edu)

Peter J. Cameron School of Mathematical Sciences Queen Mary and Westfield College Mile End Road London E1 4NS, England

                       (email: p.j.cameron@qmw.ac.uk)

L. Bruce Richmond Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario N2L 3G1, Canada

                    (email: lbrichmond@math.uwaterloo.ca)

Submitted: January 21, 2000 Accepted: May 30, 2000

Abstract

Let ρ_{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 ρ_{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 (lim inf ρ_{n}, lim sup ρ_{n}) in these cases. Only in the convergent case can one have 0 < lim ρ_{n} < 1. We study the existence of lim ρ_{n} in this case.

AMS-MOS Subject Classification (1990): 05A16; Secondary: 05C30, 05C40

1. Introduction

Throughout, A_{n} will denote the number of structures of size n, C_{n} will denote the number that are connected, and ρ_{n} = C_{n}/A_{n} whenever A_{n} ≠ 0. We consider two situations: either the objects are labeled and the exponential generating functions are related by

A(x) = exp(C(x))  (1)

or the objects are unlabeled and the ordinary generating functions are related by

A(x) = exp(∑_{k≥1} C(x^{k})/k).  (2)

Perhaps the most interesting omissions are

• objects with “noncrossing” parts, which lead to functional equations as in Beissinger [2] and Flajolet and Noy [12], and

• multiplicative objects, which lead to Dirichlet series.

We are interested in the three asymptotic probabilities

ρ_{inf} = lim inf ρ_{n},  ρ_{sup} = lim sup ρ_{n},  and  ρ = lim ρ_{n},

where the limits are taken through those n for which A_{n} ≠ 0 and ρ is defined only when that limit exists.

When C(x) is a polynomial, we immediately have ρ = 0. Therefore we assume that C(x) is not a polynomial.

(3)

Information on possible values for ρ_{inf} and ρ_{sup} are given in Theorem 1.

Various authors have obtained results about when ρ exists. See the papers by Compton [10], Knopfmacher and Knopfmacher [18] and Bender, Cameron, Odlyzko and Richmond [5]. Related to this is the question of whether first-order limit laws exist [6–8, 21].

If ρ exists, one may ask about various limiting probability distributions. Perhaps the three most interesting questions are as follows.

• 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.

• 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é [1] for some results.

• 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 [14] for some results.

The limiting distribution of the number of components, when it exists, has four common behaviors.

Let 0 ≤ R ≤ ∞ 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} → 1 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 [13]. When there is a logarithmic singularity on the circle of convergence, Hwang [17] 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 [10] 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.

We thank A. Meir for helpful comments and references.

2. 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:

L0 or U0 means R = 0,
LD or UD means R > 0 and C(R) diverges,
LC or UC means R > 0 and C(R) converges.

For case LD we may have R = ∞. Since C_{n} counts objects, it is an integer and so, in the unlabeled case, R ≤ 1 and C(1) diverges. From (3) and the fact that C_{n} is an integer, we have R < 1 for case UC.

Theorem 1. The following three cases completely describe all possibilities for the pair ρ_{inf}, ρ_{sup}, subject to the obvious constraint that 0 ≤ ρ_{inf} ≤ ρ_{sup} ≤ 1.

(a) For L0 and U0, ρ_{sup} = 1 and all values are possible for ρ_{inf}.

(b) For LD and UD, ρ_{inf} = 0 and all values are possible for ρ_{sup}.

(c) For LC and UC, all values are possible for the pair (ρ_{inf}, ρ_{sup}) except (0, 0) and (1, 1). These results still hold if we also require that C_{n} ≠ 0 for all sufficiently large n.

“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 1.1. Only (ρ_{inf}, ρ_{sup}) = (0, 1) can occur in all six cases.

Corollary 1.2. If ρ exists, then

(a) for L0 and U0 ρ = 1,

(b) for LD and UD ρ = 0,

(c) for LC and UC any value in the interval (0, 1) is possible.

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 ρ and the statement lim_{n→∞} c_{n}^{(2)}/c_{n} = 2C(R):

• Suppose R = 0. We know by Theorem 1(a) that ρ = 1 if it exists. Wright [25, 26] proved that ρ = 1 if and only if c_{n}^{(2)}/c_{n} → 0. Since R = 0, C(R) = 0.

• When C(R) diverges, the conditions are not equivalent. Cameron [9] proved that c_{n}^{(2)}/c_{n} → ∞ implies ρ = 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)} ≤ n + 2 ∑_{k^{2}<n} 2^{k^{2}} ≤ n + 2n2^{(p−1)^{2}} = o(c_{n}).

If σ_{k}(n) is the number of ways to write n as a sum of k nonzero squares, then k!a_{n} ≥ c_{n}^{(k)} ≥ σ_{k}(n)c_{n}. Since lim inf_{n→∞} σ_{k}(n) = ∞ for sufficiently large k, we have ρ = 0.

• In cases LC and UC, the next theorem proves the equivalence of the conditions under

the additional assumption that lim c_{n−1}/c_{n} exists. Theorem 2. Suppose that R > 0 and C(R) converges. Let A(x, y) enumerate structures by size and number of components. Thus

A(x, y) = \{ \begin{matrix}exp(yC(x)) & for labeled structures, \\ exp(∑_{k≥1} y^{k}C(x^{k})/k) & for unlabeled structures. \end{matrix}

Suppose that

(a) c_{n} > 0 for all sufficiently large n and

(b) lim c_{n−1}/c_{n} exists (it will be R). Then the following statements are equivalent:

(c) ∑ c_{k}c_{n−k} ∼ 2C(R)c_{n}.

(d) If ω = ω(n) → ∞, then ∑_{k=ω}^{n−ω} c_{k}c_{n−k} = o(c_{n}).

(e) ρ exists. (By Theorem 1, we then have ρ > 0.)

(f) If the number of components in a random structure is X_{n}, then for each fixed d > 0

Pr(X_{n} = d) ∼ \frac{[y^{d−1}] A(R, y)}{A(R, 1)}  (4)

and

E(X_{n}) ∼ 1 + \frac{∂A(R, y)}{A(r, 1) ∂y} |_{y=1} .  (5)

In particular, with d = 1 in (4), we have ρ = 1/A(R, 1) = 1/A(R). It may be possible to improve the theorem. In particular, we make the following conjectures. Conjecture 1. Theorem 2(b) can be replaced by (b’) lim a_{n−1}/a_{n} exists (it will be R). Conjecture 2. The existence of ρ implies (b).

Some comments on the conditions in the theorem are in order:

• The equivalence of (c) and (e) in the labeled case was given by Embrechts [11] in a more general context involving probability measures. (A subexponential measure satisfying (b) and (c) is said to belong to SD(R).)

• In the labeled case, (f) asserts that X_{n} − 1 is asymptotically Poisson with λ = C(R).

• Conditions (a) and (b) are not sufficient to deduce the existence of ρ. To see this,

define

c_{n} = [2^{n}/n^{d(n)}] where d(n) = 2 + 9 min_{k} |n − 2^{k}|/n.  (6)

Then c_{n−1}/c_{n} ∼ 1/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} ∼ 2^{m}/m^{2}, c_{2m} ∼ 2^{2m}/(2m)^{2}, and c_{3m} ∼ 2^{3m}/(3m)^{5}. Hence c_{3m} = o(c_{m}c_{2m}) in violation of (d). Rudin [23, p.990] constructs a log-convex counterexample.

• When lim c_{n−1}/c_{n} exists, perturbing the c_{n}’s by o(c_{n}) does not affect the existence of ρ. To see this, note that the perturbations do not affect the validity of (b) or (d) in the theorem.

Knopfmacher and Knopfmacher’s [18] abstract prime number theorem for additive semigroups follows from case UC of Theorem 2 since (a), (b), and (d) are easily verified.

Compton [10] dealt with LC and UC in his Theorems 10 and 11, respectively. He allowed either (a) c_{n−1}/c_{n} → R or (b) a_{n−1}/a_{n} → R. Our theorem is stronger than Compton’s (a) and would be stronger than his (b) if Conjecture 1 is true. To see that our theorem is stronger than Compton’s (a), first note that our theorem applies to

a_{n} = [\frac{x(n)}{R^{n}n^{ln n}} ] 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 α(x) = β(x) = δ(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 [11], which follows from Compton’s result, also has conditions that may be easier to verify.

Forests of various sorts provide easy examples for the application of Theorem 2. These and other graphical examples are discussed by Compton [10] and by Knopfmacher and Knopfmacher [18] in their interesting papers. Inevitably, our examples overlap with these papers.

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.

• 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 [15] for information on estimating T_{n} and t_{n}. In many cases, it can be shown that T_{n} ∼ An^{−3/2}R^{−n} and t_{n} ∼ bn^{−5/2}R^{−n} and so our theorem applies.

• Labeled Trees: In a variety of cases the exponential generating function for the rooted enumerator satisfies T (x) = xφ(T (x)). Under reasonable conditions on φ, one obtains T_{n} ∼ An^{−3/2}R^{−n}n! and so the theorem applies. Meir and Moon [19] have strengthened (f) by showing that, when 0 ≤ α < 1 and d − αn ∼ λn^{1/2}, we have

Pr(X_{n} = d) ∼ B_{1}e^{λ^{2}/2B_{2}}B_{3}^{d}B_{4}^{n},

where the B_{i} depend on φ and α. Compton [10, p. 76] 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 2 and Compton’s Theorem 10 still apply.

• 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)} → 0 and so, by the result of Cameron [9] noted before Theorem 2, 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} ∼ 2^{n}/\sqrt{πn}. Odlyzko [20] 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} ∼ R^{−n}u(ln n)/n, where R < 1 and u is periodic.

Example 2: A 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χ/4} (unrooted case) or 4A B^{n}/n^{5χ/4} (rooted case)  (7)

where χ 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 [22] for a proof of (7) for the unrooted case and for further references.

Zvonkin [28, p. 290] 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, (7) allows us to apply Theorem 2 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 (7). Consider a single term. If it is a product of k series where the ith has Euler characteristic χ_{i}, then 2 + ∑(χ_{i} − 2) is the same for all terms. Since 2 − χ_{i} > 0, ∑ n_{i} = n, and

∏ n_{i}^{−5χ_{i}/4} = (∏ n_{i}^{5(2−χ_{i})/4})(∏ \frac{1}{n_{i}} )^{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.

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 ρ in Theorem 2.

Theorem 3. Suppose that C_{n} > 0 for all sufficiently large n.

(a) If lim sup_{n} c_{n}^{(2)}/c_{n} < ∞, then C(R) converges.

(b) If lim c_{n−1}/c_{n} = R, then ρ_{sup} ≤ 1/A(R). In particular, if lim c_{n−1}/c_{n} = R and A(R) = ∞, then ρ = 0.

(c) In the labeled cases, sup_{n} c_{n}^{(2)}/c_{n} ≤ M implies that ρ_{inf} ≥ M/(e^{M} − 1).

(d) Monotonicity is not very informative: C_{n} ≥ 1 for all n makes A_{n} monotonic and, even if C_{n} is monotonic, ρ may not exist, as (6) shows.

3. Proof of Theorem 1 Part I: Only Listed Values Can Occur

In this section we prove that only the values listed in Theorem 1 for (ρ_{inf}, ρ_{sup}) 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 1 was done by Bell [3], who also showed that ρ = 1 implies R = 0, from which it follows that ρ_{inf} < 1 when R ≠ 0. To show that only the claimed values can occur, it suffices to prove the following lemma.

Lemma 1. When C(R) diverges, ρ_{inf} = 0. When R > 0 and C(R) converges, ρ_{sup} > 0.

We require Theorem 3 of Stam [24]:

Theorem 4 (Stam). Let g(x) be a power series with nonnegative coefficients, g(0) = 0, and radius of convergence R > 0. Let ∑ q_{n}(y)x^{n}/n! = exp{yg(x)}. Then

(i) If g(R) converges, then lim sup q_{n}(y)/q_{n}(1) > 0 for all y > 0.

(ii) If R = ∞ or g(R) diverges, then lim inf q_{n}(y)/q_{n}(1) = 0 for 0 ≤ y < 1.

Proof (when C(R) diverges): We prove ρ_{inf} = 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 (2) contains more terms than in (1). Hence ρ_{inf} = 0 for the unlabeled case will follow from the labeled. Apply Theorem 4(ii) with g(x) = C(x). We have q_{n}(1) = A_{n} and

q_{n}(y) = n! [x^{n}] (exp(yC(x))) = n! [x^{n}] (yC(x) + …) = yC_{n} + ….

Thus q_{n}(y)/q_{n}(1) ≥ yC_{n}/A_{n} = yρ_{n}. By Theorem 4(ii), the liminf of the left side is zero and so ρ_{inf} = 0.

Proof (when C(R) converges): It suffices to prove that ρ = 0 is impossible.

We begin with the labeled case. Apply Theorem 4(i) with g(x) = 2C(x) and y = 1/2 to conclude that lim sup q_{n}(1/2)/q_{n}(1) > 0. We proceed by contradiction, assuming that ρ = 0. From xA′(x) = xC′(x)A(x), we have

q_{n}(1/2) = a_{n} = \frac{1}{n} ∑_{k=0}^{n} kc_{k}a_{n−k} = ∑_{k=0}^{n} \frac{kc_{k}}{na_{k}} a_{k}a_{n−k}

< ∑_{k<n^{1/2}} n^{−1/2}a_{k}a_{n−k} + ∑_{k≥n^{1/2}}(c_{k}/a_{k})a_{k}a_{n−k}

= o(1) ∑_{k=0}^{n} a_{k}a_{n−k} = o(1) q_{n}(1),

contradicting lim sup q_{n}(1/2)/q_{n}(1) > 0.

We now consider the unlabeled case. Since the coefficients of C(x) are nonnegative integers, 0 < R < 1. Replacing c_{n} with c_{n} + 1 for all n multiplies A(x) by the partition generating function and so increases a_{n} by at least the partition function p_{n} and so does not increase ρ_{inf}. Hence we can assume that a_{n} ≥ p_{n} for all n. It follows that there is a function N(z) such that a_{n} > z whenever n > N(z).

Let

H(x) = ∑_{k=1}^{∞} \frac{C(x^{k})}{k} so h_{n} = ∑_{d|n} \frac{c_{n/d}}{d} .

One easily has that H(x) converges on the circle of convergence since C(x) does. By case LC, ρ_{sup} > 0. Hence there is an ϵ > 0 and an infinite set N of positive integers such that h_{n}/a_{n} > ϵ for n ∈ N. Suppose that n ∈ N and n > 2N(z). Using A′(x) = H′(x)A(x) we have

a_{n} = \frac{1}{n} ∑_{k=1}^{n} kh_{k}a_{n−k} ≥ h_{n} + ∑_{{d|n \atop d>1}} \frac{h_{n/d}a_{n−n/d}}{d} ≥ h_{n} + z ∑_{{d|n \atop d>1}} \frac{h_{n/d}}{d} .

Since n ∈ N, it follows that a_{n} < h_{n}/ϵ and so

∑_{{d|n \atop d>1}} \frac{h_{n/d}}{d} < h_{n}(1/ϵ − 1)/z = o(h_{n}) as n → ∞ through N.

By Möbius inversion,

c_{n} − h_{n} = ∑_{{d|n \atop d>1}} \frac{μ(d)h_{n/d}}{d} .

Since |μ(d)| ≤ 1, c_{n}−h_{n} = o(h_{n}) as n → ∞ through N. Hence c_{n}/a_{n} ≥ ϵ for all sufficiently large n ∈ N.

4. Proof of Theorem 2

We will show

(c) ⟺ (d) ⟹ (f) ⟹ (e) ⟹ (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 ω

∑_{k≤ω} c_{k}c_{n−k} ∼ ∑_{k≤ω} c_{k}R^{k}c_{n} = (C(R) − E(ω))c_{n},

where E(ω) → 0 as ω → ∞. By a diagonal argument, it follows that for all sufficiently slowly growing ω = ω(n) we have

∑_{k≤ω} c_{k}c_{n−k} ∼ C(R)c_{n}.

Since, for fixed n, the sum in (d) is monotonic decreasing in ω, the equivalence of (c) and (d) follows.

Proof (that (d) implies (f)): We begin by proving the implication for case LC in three steps:

(i) c_{n}^{(d)} < K^{d−1}c_{n} for some K and all sufficiently large n.

(ii) c_{n}^{(d)} ∼ dC(R)^{d−1}c_{n} uniformly for d ≤ D(n), where D(n) → ∞ suffciently slowly. (iii) a_{n} ∼ A(R, 1)c_{n}. Equation (4) will then follow:

• [y^{d}] A(x, y) = C(x)^{d}/d! counts the number of structures having exactly d components,

• (ii) tells us that [x^{n}] (\frac{C(x)^{d}}{d!} ) ∼ \frac{C(R)^{d−1}c_{n}}{(d−1)!} , which equals [y^{d−1}] A(r, y)c_{n}, and

• (iii) tells us that c_{n}/a_{n} ∼ A(R, 1). We also obtain (5):

a_{n}E(X_{n}) = [x^{n}] \frac{∂A(x, y)}{∂y}|_{y=1} = [x^{n}] C(x)e^{C(x)} = ∑[x^{n}] (\frac{C(x)^{d+1}}{d!} )

∼ ∑_{0≤d<D(n)} \frac{(d + 1)C(R)^{d}c_{n}}{d!} + O( ∑_{d≥D(n)} \frac{K^{d}c_{n}}{d!} )

∼ c_{n} ∑_{d≥0} \frac{(d + 1)C(R)^{d}}{d!} = c_{n}e^{C(R)}(C(R) + 1)

∼ a_{n}(C(R) + 1)  (8)

and ∂A(R, y)/∂y = C(R)A(R, y).

We now prove (i). Let b_{n} = c_{n} if c_{n} > 0 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)} < Kb_{n} for some K and all n ≥ 0.

Inducting on d, we have b_{n}^{(d+1)} < K^{d}b_{n} because

b_{n}^{(d+1)} = ∑_{k=0}^{n} b_{k} b_{n−k}^{(d)} < ∑_{k=0}^{n} b_{k}K^{d−1}b_{n−k} = K^{d−1} ∑_{k=0}^{n} b_{k}b_{n−k} < K^{d}b_{n}.

Since b_{k} ≥ 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)} = ∑_{k=0}^{n} c_{k}^{(d)}c_{n−k}.

We split the sum into three pieces for n → ∞ and fixed large ω:

∑_{k<ω} c_{k}^{(d)}c_{n−k} ∼ ∑_{k<ω} c_{k}^{(d)}R^{k}c_{n}  by (b),
∑_{k<ω} c_{n−k}^{(d)}c_{k} ∼ ∑_{k<ω} dC(R)^{d−1}c_{n−k}c_{k}  by induction
∼ dC(R)^{d−1} ∑_{k<ω} c_{n}R^{k}c_{k}  by (b),

∑_{k=ω}^{n−ω} c_{k}^{(d)}c_{n−k} ≤ K^{d−1} ∑_{k=ω}^{n−ω} c_{k}c_{n−k}  by (i).

By a diagonal argument, if ω = ω(n) → ∞ 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) = ∑ C(x)^{d}/d!, we can apply (ii) to those d < D(n) and (i) to those d ≥ D(n) to obtain a_{n} ∼ A(R)c_{n} = A(R, 1)c_{n}.

In proving the implication for case UC, we shall need Schur’s Theorem:

Theorem 5 (Schur). If F (x) and G(x) are power series such that f_{n−1}/f_{n} → R, G(x) has larger radius of convergence than R, and G(R) ≠ 0, then

[x^{n}] (F (x)G(x)) ∼ G(R)f_{n}.

A proof is given in Theorem 2 of [4].

Let

L(x, y) = ∑ C(x)^{k}y^{k}/k! = e^{yC(x)}

and

U(x, y) = ∑ U_{k}(x)y^{k} = A(x, y)/L(x, y).  (9)

Note that U_{k}(x) is finite sum of weighted finite products and the factors in the products are of the form C(x^{d})/d with d ≥ 2. It follows that U_{k}(x) has radius of convergence at least R^{1/2}. This exceeds R since 0 < R < 1. The generating function for structures with exactly d components is

[y^{d}] (L(x, y)U(x, y)) = ∑_{k=1}^{d}(C(x)^{k}/k!)U_{d−k}(x) + U_{d}(x).

From (f) for case LC,

[x^{n}] (C(x)^{k}/k!) ∼ (C(R)^{k−1}/(k − 1)!)c_{n}.

By (b), the ratio of consecutive coefficients of C(x)^{k}/k! approaches R and so, by Theorem 5,

[x^{n}] ((C(x)^{k}/k!)U_{d−k}(x)) ∼ (U_{d−k}(R)C(R)^{k−1}/(k − 1)!)c_{n}.

Choose S such that R < S < R^{1/2}. Since U_{d}(x) has radius of convergence at least R^{1/2}, its coefficients are o(S^{−n}) whereas, by (b), c_{n} grows faster than S^{−n}. It follows that

\begin{aligned}[x^{n}] (∑_{k=1}^{d}(C(x)^{k}/k!)U_{d−k}(x) + U_{d}(x)) & ∼ c_{n} ∑_{k=1}^{d} U_{d−k}(R)C(R)^{k−1}/(k − 1)! \\ & = c_{n}[y^{d−1}] (U(R, y)e^{C(R)y}) = c_{n}[y^{d−1}] A(R, y). \end{aligned}

To complete the proof of (4), we estimate a_{n}. We have A(x) = A(x, 1) = L(x, 1)U(x, 1). From LC, the coefficients of L(x, 1) are asymptotic to e^{C(R)}c_{n}. The radius of convergence of U(x, 1) exceeds R since, for x < R^{1/2},

∑_{k≥2} \frac{C(x^{k})}{k} = ∑_{k≥2} (\frac{C(x^{k})}{x^{k}}) (\frac{x^{k}}{k} ) < ∑_{k≥2} (\frac{C(R)}{R}) (\frac{R^{k/2}}{k} ) < ∞.

Apply Theorem 5 to conclude that a_{n} ∼ c_{n}A(R) = c_{n}A(R, 1). The claim concerning ρ is immediate:

ρ_{n} = Pr(X_{n} = 1) ∼ 1/A(R, 1) = 1/A(R).

We now prove (5). Note that

\begin{aligned}a_{n}E(X_{n}) & = [x^{n}] \frac{∂A(x, y)}{∂y}|_{y=1} \\ & = [x^{n}] C(x)e^{C(x)}U(x, 1) + [x^{n}] ∑_{d>1} C(x^{d})A(x, 1). \end{aligned}

By (8), [x^{n}] C(x)e^{C(x)} ∼ c_{n}e^{C(R)}(C(R) + 1). Since U(x, 1) and ∑_{d>1} C(x^{d}) converge for x < R^{1/2}, it follows from Theorem 5 that

a_{n}E(X_{n}) ∼ c_{n}e^{C(R)}(C(R) + 1)U(R, 1) + ∑_{d>1} C(R^{d})a_{n}.

Since c_{n}e^{C(R)}U(R, 1) = c_{n}A(R, 1) ∼ c_{n}, the proof is complete.

Proof (that (e) implies (c)): We first prove (c) for case LC. Throughout, ω 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 ρ ≠ 0 we have

na_{n} = ∑_{k=0}^{n} kc_{k}a_{n−k} ∼ ∑_{k>ω} kc_{k}a_{n−k} ∼ ∑_{k>ω} kρa_{k}a_{n−k},

where we could neglect the terms less that ω as long as ω = o(n) because for k ≤ ω and n large

kc_{k}a_{n−k} ≤ ωa_{k}a_{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 > ω. Similarly, we can restore such terms to obtain

na_{n} ∼ ρ ∑_{k=0}^{n} ka_{k}a_{n−k}

= \frac{ρ}{2}(∑_{k=0}^{n} ka_{k}a_{n−k} + ∑_{k=0}^{n}(n − k)a_{n−k}a_{k})

= \frac{nρ}{2} ∑_{k=0}^{n} a_{k}a_{n−k}.

Hence

a_{n} ∼ \frac{ρ}{2} ∑_{k=0}^{n} a_{k}a_{n−k} = \frac{ρ a_{n}^{(2)}}{2} .  (10)

From (10) and a “diagonal” argument,

c_{n} ∼ ρa_{n} ∼ \frac{ρ^{2}a_{n}^{(2)}}{2}

= ρc_{n} ∑_{k<ω} a_{k} \frac{c_{n−k}}{c_{n}} \frac{ρa_{n−k}}{c_{n−k}} + \frac{1}{2} ∑_{k=ω}^{n−ω} c_{k}c_{n−k} \frac{ρa_{k}}{c_{k}} \frac{ρa_{n−k}}{c_{n−k}}

∼ ρc_{n} ∑_{k<ω} a_{k}R^{k} + \frac{1}{2} ∑_{k=0}^{n} c_{k}c_{n−k} − c_{n} ∑_{k<ω} c_{k} \frac{c_{n−k}}{c_{n}}

∼ ρc_{n}A(R) + L_{n}c_{n} − c_{n}C(R),

where L_{n} is defined by ∑ c_{k}c_{n−k} = 2L_{n}c_{n}. Factoring out c_{n}, we see that

1 ∼ ρA(R) + L_{n} − C(R) and so L_{n} ∼ L = 1 + C(R) − ρA(R).

Solving for ρA(R) gives

ρA(R) = 1 + C(R) − L.  (11)

Now consider replacing c_{n} by 2c_{n} and a_{n} by a_{n}^{(2)}. From (10), the hypotheses of the theorem are still valid provided we replace ρ by ρ^{2}. Hence (11) still holds with the appropriate values for A(R), C(R), and L, namely A(R)^{2}, 2C(R) and 2L. Thus

ρ^{2}A(R)^{2} = 1 + 2C(R) − 2L.

Equating this to the square of (11) we obtain (1+δ)^{2} = 1+2δ where δ = C(R)−L. Hence δ = 0.

We now prove the implication for the case UC. Since ρ exists and is nonzero, it follows from (a) that a_{n−1}/a_{n} ∼ R. Let U(x, y) be as in (9) and recall that U(x, 1) converges for x < R^{1/2}. Applying Theorem 5 to e^{C(x)} = A(x)/U(x, 1), we conclude that [x^{n}] e^{C(x)} ∼ a_{n}/U(R, 1). Hence

lim_{n→∞} (\frac{c_{n}}{[x^{n}] e^{C(x)}} ) exists.

Regarding C(x) as a generating function for labeled structures, we have just shown that (e) holds and so, case LC implies (c).

5. Proof of Theorem 3

Proof (of (a)): If R = 0, there is nothing to prove. Otherwise, the hypothesis asserts that [x^{n}] C(x)^{2} ≤ [x^{n}] MC(x) for some M < ∞ and n sufficiently large. Thus, for some polynomial p, C(r)^{2} ≤ MC(r) + p(r) for 0 < r < R. Divide by C(r). We claim p(r)/C(r) is bounded as r → R. This is obvious if R < ∞. When R = ∞, it follows from the assumption that C_{n} > 0 for sufficiently large n.

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) = ∞. Hence the result for case LD implies the result for case UD. In case UC, let

b_{n} = min([x^{n}] e^{C(x)}, e^{C(R)}c_{n}).

It follows from case LC that lim sup(c_{n}/[x^{n}] e^{C(x)}) ≤ 1/e^{C(R)}. Hence b_{n} ∼ e^{C(R)}c_{n}. From Theorem 5,

[x^{n}](B(x) exp{∑_{k≥2} C(x^{k})/k}) ∼ exp{∑_{k≥2} C(R^{k})/k}b_{n} ∼ A(R)c_{n}.

Since C(x^{k}) has nonnegative coefficients and 0 ≤ b_{n} ≤ [x^{n}] e^{C(x)},

[x^{n}](B(x) exp{∑_{k≥2} C(x^{k})/k}) ≤ a_{n}.

Combining the last two displayed equations gives lim sup c_{n}/a_{n} ≤ 1/A(R).

We now prove the labeled cases. Fix 0 < r < R. Let K = K(n) < n/2 be such that (i) c_{n−k}/c_{n} ≥ r^{k} for 0 ≤ k ≤ K and (ii) K(n) → ∞. This is possible since c_{n−1}/c_{n} ∼ R. For every nonnegative integer d

[x^{n}] C(x)^{d+1} ≥ (d + 1) ∑_{i_{1}+···+i_{d}≤K}c_{i_{1}} ⋯ c_{i_{d}}r^{i_{1}+···+i_{d}}c_{n} ∼ (d + 1)C(r)^{d}c_{n}.

Hence

lim inf [x^{n}] ( ∑_{d<D} \frac{C(x)^{d+1}}{c_{n}(d + 1)!}) ≥ ∑_{d<D} \frac{C(r)^{d}}{d!} .

Since D is arbitrary, it follows that lim inf [x^{n}] e^{C(x)}/c_{n} ≥ e^{C(r)}. Now let r → R.

Proof (of (c)): If M = ∞, there is nothing to prove since \frac{M}{e^{M} −1} = 0. Suppose M is finite and regard C(x) as a formal power series. We have C(x)^{2} ≤ MC(x), with the inequality understood coefficientwise. By induction on k and the fact that c_{n} ≥ 0, it follows that C(x)^{k} ≤ M^{k−1}C(x) and so

A(x) = ∑_{k=0}^{∞} C(x)^{k}/k! ≤ 1 + \frac{e^{M} − 1}{M}C(x).

The result follows.

Proof (of (d)): Define new enumerators for connected structures by C_{n}^{∗} = C_{n} − 1 and let A_{n}^{∗} be the associated enumerators for all structures. In the labeled case, A(x) = e^{x}A^{∗}(x) and so

A_{n} = ∑_{k=0}^{n} \binom{n}{k}A_{k}^{∗}.

Since \binom{n}{k} is an increasing function of n, we are done. In the unlabeled case,

A_{n} = ∑_{k=0}^{n} p_{n−k}A_{k}^{∗}

where p_{n−k}, the number of partitions of n − k, is an increasing function of n.

Equation (6) can be used to construct a monotonic C_{n} for which ρ does not exist. It is easily shown that c_{n} is eventually monotonic. By changing enough initial values of c_{n}, we can guarantee that C_{n} is monotonic for all n.

6. Proof of Theorem 1 Part II: All Listed Values Do Occur

As already noted, Bell [3] proved the R = 0 case, so we assume R > 0. Our proof consists of a variety of constructions which are dealt with in a series of lemmas. All our constructions produce integers C_{n} ≥ 0 which are nonzero for sufficiently large n. Here is how the lemmas deal with the various parts:

• Lemma 2 proves all cases when ρ_{inf} = 0 and ρ_{sup} = 1.

• Lemma 5 proves the convergent case for 0 ≤ ρ_{inf} ≤ ρ_{sup} < 1.

• Lemma 6 proves the convergent case for 0 < ρ_{inf} < ρ_{sup} = 1.

• Lemma 7 proves the divergent case when ρ_{sup} < 1. As always, assume that C(x) and A(x) are related by (1) and (2). Define

τ(n) = \{ \begin{matrix}1, & in the unlabeled case, \\ n!, & in the labeled case. \end{matrix}

Lemma 2. 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, ρ_{inf} = 0, and ρ_{sup} = 1.

Proof: Set

E_{n} = \{ \begin{matrix}[τ(n)/n^{2}R^{n}] & for the convergent cases, \\ [n!/(ln n)^{1/4}] & for the R = ∞ case, \\ [exp(n^{3/4})] & for the unlabeled R = 1 case, \\ [τ(n)/R^{n}] & for the remaining divergent cases. \end{matrix}

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} ≥ 1, it follows that A_{n} → ∞. Because there will be infinitely many nonexceptional indices, we have ρ_{inf} = 0.

We prove that, if only finitely many values of n are exceptional, then A_{n}/E_{n} → 0. Let K be an integer such that C_{n} ≤ K for all n. In the labeled case with r = 1/ ln n,

A_{n}/n! ≤ [x^{0}] (x^{−n}e^{K(e^{x}−1)}) < r^{−n}e^{Ke^{r}} = (e^{K}/ ln n)^{n},  (12)

and so A_{n}/E_{n} → 0 in this case. In the unlabeled case, A_{n} is bounded by the K-fold convolution of the partition function p_{n} = exp(O(n^{1/2})) with itself. This convolution is bounded by (n + 1)^{K−1}p_{n}^{K} = exp(O(n^{1/2})), and so A_{n}/E_{n} → 0.

Denote the indices of the exceptional C_{n} by n_{1}, n_{2}, . . .. Set n_{1} = 3. Suppose n_{i} has been chosen for i < k. Let Ã_{n} be the values of A_{n} computed using those exceptional values and C_{n} = 1 otherwise. By the preceding paragraph, there is an n > n_{k−1} +1 so that Ã_{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 Ã_{n} since the only change to C(x) was to increase it by (E_{n} −1)x^{n}/τ(n). Thus

\frac{C_{n}}{A_{n}} = \frac{E_{n}}{A_{n}} = \frac{E_{n}}{(E_{n} − 1) + Ã_{n}} > \frac{1}{1 + 1/k} .

Since we make no more changes in C_{j} for j ≤ n_{k}, it follows that C_{n}/A_{n} will not change and so ρ_{sup} = 1.

Lemma 3. Suppose that α > 0, ξ > 1, p > 1, R > 0, and that A is an infinite set of positive integers forming an arithmetic progression. Then there are nonnegative integers C_{n} such that

(i) C_{n} = 0 for n ∉ A,

(ii) C_{n} ∼ α τ(n)/n^{p}R^{n} for n ∈ A, and
(iii) A(R) = ξ.

Proof: Find an N ∈ A such that setting

C_{n} = \{ \begin{matrix}α τ(n)/n^{p}R^{n}, & if n ≥ N and n ∈ A, \\ 0, & otherwise, \end{matrix}

leads to A(R) ≤ ξ. Increase C_{N} so that A(R) = ξ. Call this sequence C_{n}^{[N]}. Let l < k be two consecutive elements of A and suppose the sequence C_{n}^{[l]} has been defined. Define the sequence C_{n}^{[k]} by

C_{n}^{[k]} = \{ \begin{matrix}C_{n}^{[l]}, & for n ≠ l, k, \\ ⌊C_{l}^{[l]}⌋ , & for n = l, \\ C_{k}^{[l]} + x_{l}, & for n = k, \end{matrix}

where x_{k} is chosen so that A(R) will be unchanged. Thus 0 ≤ x_{k} and, in the labeled case

x_{k} = \{C_{l}^{[l]}\} \frac{R^{l}/l!}{R^{k}/k!} = o(k!/k^{p}R^{k}) = o(C_{k}^{[k]}),

where {z} is the fractional part of z. In the unlabeled case, changing C_{i} by δ changes ln A(R) by

∑_{k>0} δR^{ik}/k = −δ ln(1 − R^{i}).

Hence

x_{k} = \{C_{l}^{[l]}\}\frac{ln(1 − R^{l})}{ln(1 − R^{k})} = O(R^{l−k}) = O(1).

Thus x_{k} = o (C_{k}^{[k]}). Note that C_{n}^{[m]} changes for at most two values of m: once for m = n

and once for the preceding element in A. Let C_{n} be value of C_{n}^{[m]} for m > n.

Lemma 4. Suppose a, b, d, α, 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} ∼ \{ \begin{matrix}\frac{α τ(n)}{n^{p}R^{n}} , & if n is even, \\ \frac{αd τ(n)}{n^{q}R^{n}} , & if n is odd, \end{matrix}

∑_{n≥0} \frac{A_{2n}R^{2n}}{τ(2n)} = 1 + a, and ∑_{n≥0} \frac{A_{2n+1}R^{2n+1}}{τ(2n + 1)} = b,

where A(x) is given by (1) or (2).

Proof: The last displayed equations are equivalent to

A(R) = 1 + a + b and 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 3 that we can find C̃_{n} vanishing at odd n and asymptotic to α τ(n)/n^{p}R^{n} at even n such that Ã(R) = \sqrt{A^{+}A^{−}}. Since A^{+}/A^{−} > 1, it again follows that we can find Ĉ_{n} vanishing at even n and asymptotic to αd τ(n)/n^{q}R^{n} at odd n such that Â(R) = \sqrt{A^{+}/A^{−}}. Let C_{n} = C̃_{n} + Ĉ_{n}. Then A(x) = Ã(x)Â(x) and so

A(R) = Ã(R)Â(R) = A^{+} and A(−R) = Ã(−R)Â(−R) = Ã(R)/Â(R) = A^{−}.

Lemma 5. Suppose R > 0, 1 > ρ_{sup} ≥ ρ_{inf} ≥ 0 and ρ_{sup} > 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, lim inf_{n→∞} C_{n}/A_{n} = ρ_{inf}, and lim sup_{n→∞} C_{n}/A_{n} = ρ_{sup}.

Proof: We begin by choosing values to use in Lemma 4, according as whether ρ_{inf} = 0 or not.

Suppose ρ_{inf} = 0. Let d = 1, a = (1/ρ_{sup}) − 1, α = 1, p = 2, q = 3 and b = a.

Now suppose ρ_{inf} > 0. Let α = 1, p = q = 2, μ = (1/ρ_{sup}) − 1 and ν = (1/ρ_{inf}) − 1. Note that ν ≥ μ > 0. If μ = ν, let d = 1 and a = b = μ/2; otherwise, we claim that for sufficiently small d there exist a, b > 0 such that a(a + 2) > b^{2} and

( \begin{matrix}1 & d \\ 1 & 1/d \end{matrix} ) ( \begin{matrix}a \\ b \end{matrix} ) = ( \begin{matrix}μ \\ ν \end{matrix} ) .

To see this, solve and note that, as d → 0, we have a ∼ μ and b ∼ (ν − μ)d. Choose such a small d.

Using the values in the preceding two paragraphs, apply Lemma 4. 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} = ∑(n − k)h_{n−k}a_{k}.  (13)

Hence

na_{n} = ∑(n − i)h_{n−i}a_{i} ≥ (n/2)(a_{k}c_{n−k} + a_{k−1}c_{n−k+1}) = Θ(1/nR^{n}).  (14)

Replacing C_{n} with larger values that are asymptotic to α max(1, d)τ(n)/n^{2}R^{n} increases the value of a_{n} and allows us to use Theorem 2 to conclude that the new a_{n}, and hence the old a_{n}, are O(1/n^{2}R^{n}). Combining this with (14), we have

A_{n} = Θ(τ(n)/n^{2}R^{n}).  (15)

In the labeled case, h_{n} = c_{n} and in the unlabeled case

h_{n} = ∑_{d|n} \frac{c_{d}}{n/d} = c_{n} + O( ∑_{d≤n/2} R^{−d}) = c_{n} + O(R^{−n/2}),

and so h_{n} ∼ c_{n}. From this and (13), it follows easily that

a_{n} ∼ c_{n} ∑_{k even} a_{k}R^{k} + c_{n−1} ∑_{k odd} a_{k}R^{k−1} = c_{n}(1 + a) + c_{n−1} \frac{b}{R}.  (16)

We now use this, treating ρ_{inf} > 0 and ρ_{inf} = 0 separately. For ρ_{inf} > 0

\frac{a_{2n}}{c_{2n}} ∼ (1 + a) + \frac{c_{2n−1}b}{Rc_{2n}} ∼ 1 + a + \frac{b}{d} = 1 + μ = \frac{1}{ρ_{inf}}

and, similarly, a_{2n+1}/c_{2n+1} ∼ 1/ρ_{sup}. For ρ_{inf} = 0, we have a_{2n}/c_{2n} ∼ 1 + a = 1/ρ_{sup} from (16), and, from (15) and the asymptotics for C_{2n+1}, C_{2n+1}/A_{2n+1} → 0.

Lemma 6. In both the labeled and unlabeled convergent cases, if 0 < λ < 1, there are integers C_{n} tending to infinity such that C(x) has radius of convergence R, ρ_{inf} = λ, and ρ_{sup} = 1.

Proof: Let ζ_{n} = τ(n)R^{−n}/n^{ν(n)} where

ν(n) = 3 − ∑_{i=1}^{log_{3}(log_{3} n)} 2^{−i}.

Find an N > 0 such that setting

C_{n} = \{ \begin{matrix}ζ_{n}, & for n ≥ N, \\ 0, & otherwise, \end{matrix}

leads to A(R) ≤ 1/λ. Increase C_{N} so that A(R) = 1/λ. Call this sequence C_{n}^{[N]}. Proceed as in the proof of Lemma 3 so as to obtain a sequence of integers C_{n} with C_{n} ∼ ζ_{n} and A(R) = 1/λ. Clearly C(x) has radius of convergence R and converges at R.

We now show that ρ_{inf} = 1/A(R). Let H(x) = ln A(x). As in the proof of Lemma 5, h_{n} ∼ c_{n}. Let ĥ_{k} = h_{k}k^{ν(k)−ν(n)}. From na_{n} = ∑ kh_{k}a_{n−k}, we have

na_{n} ≤ ∑ kĥ_{k}a_{n−k} ∼ nĥ_{n}A(R) ∼ nc_{n}A(R).

Hence ρ_{inf} ≥ 1/A(R). Letting n → ∞ through n = 3^{3^{k}} − 1, one easily sees that na_{n} ∼ h_{n}A(R) and so ρ_{inf} = 1/A(R).

We now show that ρ_{sup} = 1. Let n → ∞ through n = 3^{3^{k}}. For such an n, let c̃_{n} = c_{n}/n^{ν(n−1)−ν(n)} and let ã_{n} be the value of a_{n} obtained when c_{n} is replaced by c̃_{n}. By the argument in the preceding paragraph, c̃_{n}/ã_{n} → ρ_{inf}. Since A(x) = e^{H(x)} and since H(x) and H̃(x)+(c_{n} −c̃_{n})x^{n} agree through terms of degree n, we have a_{n} = ã_{n} +(c_{n} −c̃_{n}). Thus

\frac{c_{n}}{a_{n}} = \frac{1}{1 + (ã_{n}/c̃_{n} − 1)c̃_{n}/c_{n}} ∼ \frac{1}{1 + (1 − 1/ρ_{inf})c̃_{n}/c_{n}} .

Since n = 3^{3^{k}} and ν(n) − ν(n − 1) = 2^{−k}, we have

\frac{c̃_{n}}{c_{n}} ∼ (3^{3^{k}})^{−2^{−k}} = 3^{−(3/2)^{k}} → 0.

Thus lim_{k→∞} c_{n}/a_{n} = 1 where n = 3^{3^{k}}.

Lemma 7. Suppose R > 0 and 0 < α < 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 ρ_{sup} = α.

Proof: Define β = (1 − 1/α)^{−1} and

R_{n} = \{ \begin{matrix}(ln n)^{n/2}, & if R = ∞, \\ exp(−n^{−1/3}), & if unlabeled and R = 1, \\ R, & otherwise. \end{matrix}

Let C_{n}^{[1]} = 1 for all n > 1 and let C_{1}^{[1]} be any integer greater than 1/α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]} = \{ \begin{matrix}C_{n}^{[k−1]}, & if n ≠ k, \\ C_{k}^{[k−1]}, & if n = k and A_{k}^{[k−1]} ≥ τ(k)/R_{k}^{k}, \\ ⌈βτ(k)A_{k}^{[k−1]}⌉ , & otherwise. \end{matrix}  (17)

Since C_{n}^{[k]} is unchanging for k > n, we define C_{n} = C_{n}^{[n+1]}. Let K be the set of k for which the third alternative is used. We will show that (a) K is infinite.

(b) The radius of convergence of C(x) is at least R.

(c) lim_{n→∞} C_{n}/A_{n} = α, where the limit is taken through n ∈ K.

(d) C(R) = ∞.

The lemma follows immediately from these claims.

To prove (a), it suffices to show that lim_{n→∞} A_{n}^{[k]}R_{n}^{n}/τ(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 (12), we obtain

A_{n}^{[k]}/n! < exp(p(ln n)) × (e/ ln n)^{n} = o(1/(ln n)^{n/2}).

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

\begin{aligned}A_{n}^{[k]} & ≤ [x^{n}] (\frac{p(x)}{(1 − x)^{l}} ) ≤ [x^{n}] (\frac{1}{(1 − x)^{l}} \frac{p_{n}}{1 − x}) \\ & ≤ n^{l+1}p_{n} = o(exp(n^{2/3})) = O((exp(−n^{−1/3}))^{−n}). \end{aligned}

This completes the proof of (a).

From the definition of C_{n}^{[k]}, it follows that C_{n}^{[k]} < 1 + βτ(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 ∈ K, C_{k}^{[k−1]} = 1/τ(k) and C_{k}^{[k]} differs from βA_{k}^{[k]} by less than 1. Hence C_{k}^{[k]}/A_{k}^{[k]} ∼ β/(1 + β) = α.

Finally, we prove that C(R) = ∞. It suffices to show that the middle condition in (17) holds infinitely often. Suppose not. It follows from (c) that ρ exists and equals α. With H(x) = ln A(x) we have A′(x) = H′(x)A(x) and so

na_{n} = ∑_{k=1}^{n} kh_{k}a_{n−k} ≥ (n − 1)h_{n−1}a_{1} ≥ (n − 1)c_{n−1}a_{1} = (n − 1)c_{n−1}C_{1}.

Hence a_{n}/c_{n} ≥ C_{1}(1 − 1/n)c_{n−1}/c_{n} and so

\frac{1}{α} = lim_{n→∞} \frac{a_{n}}{c_{n}} ≥ C_{1} lim sup_{n→∞} \frac{c_{n−1}}{c_{n}} .

Since lim sup_{n→∞} |b_{n−1}/b_{n}| is at least the radius of convergence of a power series ∑ b_{n}x^{n} and since C_{1} > 1/(αR), we have 1/α > (1/(αR))R, a contradiction.

References

[1] R. Arratia, A. D. Barbour, and S. Tavaré, Notices AMS 44 (1997) 903–910.

[2] J. S. Beissinger, The enumeration of irreducible combinatorial objects, J. Combin. Theory, Ser. A 38 (1985) 143–169.

[3] J. P. Bell, When structures are almost surely connected, Electron. J. Combin. submitted.

[4] E. A. Bender, Asymptotic methods in enumeration, SIAM Rev. 16 (1974), 485-515.

[5] E. A. Bender, P. J. Cameron, A. M. Odlyzko, and L. B. Richmond, Connectedness, classes and cycle index, Combin., Probab. and Comput. 8 (1999) 31–43.

[6] S. Burris, Spectrally determined first-order limit laws, DIMACS Series in Discrete Math. and Theoret. Comput. Science 33 (1997)33–52.

[7] S. Burris, K. Compton, A. Odlyzko, and B. Richmond, Fine spectra and limit laws II. First-order 0-1 laws, Canad. J. Math. 49 (1997) 641–652.

[8] S. Burris and A. Sárközy, Fine spectra and limit laws I. First-order laws, Canad. J. Math. 49 (1997) 468–498.

[9] P. J. Cameron, On the probability of connectedness, Discrete Math. 167/168 (1997) 175–187.

[10] K. J. Compton, Some methods for computing component distribution probabilities in relational structures, Discrete Math. 66 (1987) 59–77.

[11] P. Embrechts, The asymptotic behaviour of series and power series with positive coefficients, Med. Konink. Acad. Wetensch. (Brussels) 45 (1983) 41–61.

[12] P. Flajolet and M. Noy, Analytic combinatorics of non-crossing partitions, INRIA Rpt. No. 3196 (1997).

[13] P. Flajolet and M. Soria, Gaussian limiting distributions for the number of components in combinatorial structures, J. Combin. Theory, Ser. A 53 (1990) 165–182.

[14] X. Gourdon, Largest component in random combinatorial structures, Discrete Math. 180 (1998) 185–209.

[15] F. Harary, R. W. Robinson, and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Ser. A 20 (1975) 483–503.

[16] W. K. Hayman, A generalisation of Stirling’s formula, J. Reine Angew. Math. 196 (1956) 67–95.

[17] H.-K. Hwang, A Poisson * geometric convolution law for the number of components in unlabelled combinatorial structures, Combin., Probab. and Comput. 7 (1998) 89–110.

[18] A. Knopfmacher and J. Knopfmacher, Arithmetical semigroups related to trees and polyhedra, J. Combin. Theory, Ser. A 86 (1999) 85–102.

[19] A. Meir and J. W. Moon, The asymptotic behaviour of coefficients of certain generating functions, Europ. J. Combin. 11 (1990) 581–587.

[20] A. M. Odlyzko, Periodic oscillations of coefficients of power series that satisfy functional equations, Adv. Math. 44 (1982) 180–205.

[21] H. J. Prömel, Counting unlabeled structures, J. Combin. Theory, Ser. A 44 (1987) 83–93.

[22] L.B. Richmond and N.C. Wormald, Almost all maps are asymmetric, J. Combin. Theory, Ser. B 63 (1995) 1–7.

[23] W. Rudin, Limits of ratios of tails of measures, Ann. Probab. 1 (1973) 982–994.

[24] A.J. Stam, Polynomials of binomial type and compound Poisson Processes, J. Math. Anal. Appl. 130 (1988) 493–508.

[25] E. M. Wright, A relationship between two sequences, Proc. London Math. Soc. (iii) 17 (1967) 296–304.

[26] E. M. Wright, A relationship between two sequences III, J. London Math. Soc. 43 (1968) 720–724.

[27] E. M. Wright, Asymptotic relations between enumerative functions in graph theory, Proc. London Math. Soc. (iii) 20 (1970) 558–572.

[28] A. Zvonkin, Matrix integrals and map enumeration: An accessible introduction, Mathl. Comput. Modeling 26 (1997) 281–304.