Admissible Functions and Asymptotics for Labelled Structures by Number of Components

Edward A. Bender Center for Communications Research 4320 Westerra Court San Diego, CA 92121, USA

                           ed@ccrwest.org

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

                   lbrichmo@watdragon.uwaterloo.ca

Submitted: August 19, 1996; Accepted: November 27, 1996

Abstract

Let a(n, k) denote the number of combinatorial structures of size n with k components. One often has ∑_{n,k} a(n, k)x^{n}y^{k}/n! = exp{yC(x)}, where C(x) is frequently the exponential generating function for connected structures. How does a(n, k) behave as a function of k when n is large and C(x) is entire or has large singularities on its circle of convergence? The Flajolet-Odlyzko singularity analysis does not directly apply in such cases. We extend some of Hayman’s work on admissible functions of a single variable to functions of several variables. As applications, we obtain asymptotics and local limit theorems for several set partition problems, decomposition of vector spaces, tagged permutations, and various complete graph covering problems.

1991 AMS Classification Numbers. Primary: 05A16 Secondary: 05A18, 15A03, 41A60

1. Introduction

A variety of combinatorial structures can be decomposed into components so that the generating function for all structures is the exponential of the generating function for components: A(x) = e^{C(x)}. (This is a single variable instance of the exponential formula.) In this case, A(x, y) = e^{yC(x)} is the generating function for structures by number of components and is an ordinary generating function in y. For the present discussion, we assume C(x) is an exponential generating function. One often wishes to study a_{n,k} = [x^{n}y^{k}/n!]A(x, y), the number of k-component structures of size n. In particular, one may ask how a_{n,k} varies with k for fixed large n. From a somewhat different viewpoint, one may want to study the probability distribution for the random variable X_{n} given by Pr(X_{n} = k) = a_{n,k} / ∑_{k} a_{n,k} as n → ∞.

One approach is to observe that k! a_{n,k} = [x^{n}/n!](C(x))^{k}. Such methods are useful for estimating the larger coefficients of (C(x))^{k} as n varies and k is large, which is not the same as studying the larger values of a_{n,k} for fixed n. Consequently, one may find that the method only yields estimates in the tail of the distribution of X_{n}. See Gardy [7] for a discussion of these methods. However, it is sometimes possible to extend the range to include the larger values of a_{n,k}. See Drmota [3], especially Section 3.

Working directly with A(x, y) is likely to provide estimates for the larger coefficients rather than tail probabilities. Unfortunately, multivariate generating functions have proven to be recalcitrant subjects for asymptotic analysis. When A(x, y) has small singularities, methods akin to Darboux’s Theorem may be useful. See Flajolet and Soria [5] and Gao and Richmond [6] for examples. See Odlyzko [12] for an extensive discussion of asymptotic methods.

In order to study a variety of single-variable functions with large singularities, Hayman [10] defined a class of admissible functions in such a way that (a) class members have useful properties and (b) class membership can easily be established for a variety of functions. We refer to his functions as H-admissible. Hayman’s results include:

• If p is a polynomial and the coefficients of e^{p} are eventually strictly positive, then e^{p} is H-admissible.

• If f is H-admissible, so is e^{f}.

• If f and g are H-admissible, so is fg.

In [2] we made a somewhat ill-considered attempt to extend his notions to multivariate generating functions. In this paper we present a simpler alternative definition which has applications to the problems described in the first paragraph and which includes H-admissible functions as a special single variable case.

The next section contains our definition for a class of admissible functions and an estimate for coefficients of such functions. Section 3 provides theorems for establishing the admissibility of a variety of functions, especially those related to counting structures by number of components of various types via the exponential formula. Applications are presented in Section 4. Proofs of the theorems are given in Section 5.

2. Definitions and Asymptotics

Let x be d-dimensional, let ℝ_{+} be the positive reals, and let re^{i0} be the vector whose kth component is r_{k}e^{iθ_{k}}. Suppose f(x) has a power series expansion ∑ a_{n}x^{n} where x^{n} is the product of x_{k}^{n_{k}}. The lattice Λ_{f} ⊆ ℤ^{d} is the ℤ-module spanned by the differences of those n for which a_{n} ≠ 0. We assume that Λ_{f} is d-dimensional. Let d(Λ_{f}) be the absolute value of the determinant of a basis of Λ_{f}. In other words, d(Λ_{f}) is the reciprocal of the density of Λ_{f} in ℤ^{d}. The polar lattice Λ_{f}^{∗} ⊆ ℝ^{d} is the ℤ-module of vectors v such that v · u is an integer for all u ∈ Λ_{f}. If v_{1}, …, v_{d} is a ℤ-basis for Λ_{f}^{∗}, a fundamental region for f is the parallelepiped

Φ(f) = {c_{1}v_{1} + ⋯ + c_{d}v_{d} | −π ≤ c_{k} ≤ π for 1 ≤ k ≤ d}.

Since the basis for a lattice is not unique, neither is Φ(f). If coefficients a_{n} are nonzero for all sufficiently large n, then Λ_{f}^{∗} = Λ_{f} = ℤ^{d}, d(Λ_{f}) = 1, and we may take Φ(f) = [−π, π]^{d}.

We say that f(x) = o_{u(x)}(g(x)) for x in some set S if there is a function λ(t) → 0 as t → ∞ such that |f(x)/g(x)| ≤ λ(|u(x)|) for all x ∈ S. The extension to equations involving little-oh expressions is done in the usual manner.

If B is a square matrix, |B| denotes the determinant of B. We use v′ and S′ to denote the transpose of the vector v and the matrix S.

Definition of Admissibility. Let f be a d-variable function that is analytic at the origin and has a fundamental region Φ(f). When Λ_{f} is d-dimensional, we say that f(x) is admissible in R ⊆ ℝ_{+}^{d} with angles Θ if there are (i) a function Θ from R to open subsets of Φ(f) containing 0 and (ii) functions

a : ℂ^{d} → ℂ^{d} and B : ℂ^{d} → ℂ^{d×d}

such that

(a) f(x) is analytic whenever r ∈ R and |x_{i}| ≤ r_{i} for all i;

(b) B(r) is positive definite for r ∈ R;

(c) the diameter of Θ(r) is o_{u}(1), where u = |B(r)|;

(d) for r ∈ R, u = |B(r)|, and 0 ∈ Θ(r), we have

f(re^{i0}) = f(r)(1 + o_{u}(1)) exp{ia(r)′0 − 0′B(r)0/2};  (1)

(e) For r ∈ R, u = |B(r)|, and 0 in the complement of Θ(r) relative to Φ(f), we

have

f(re^{i0}) = o_{u}(f(r)) / |B(r)|^{1/2}.  (2)

We say f is super-admissible if (2) can be replaced by

f(re^{i0}) = o_{u}(f(r)) / |B(r)|^{t}  (3)

for all t, where o_{u} may depend on t.

Usually one can let a(x) and B(x) be the gradient and Hessian of log f with respect to log x; that is,

a_{i}(x) = \frac{x_{i}∂f}{f∂x_{i}} and B_{i,j} = x_{j} \frac{∂a_{i}}{∂x_{j}} = B_{j,i}.

We call these the gradient a and B.

Since H-admissible functions satisfy b(r) → ∞ as r → R, it is easily verified that this definition includes H-admissible functions. The asymptotic result for Hadmissible functions holds for our admissible functions:

Theorem 1. Suppose f(x) is admissible in R. Let k be any vector such that [x^{k}]f(x) ≠ 0, let u = |B(r)|, and let v = a(r) − n. Then

[x^{n}] f(x) = \frac{d(Λ_{f})f(r)r^{−n}}{(2π)^{d/2}|B(r)|^{1/2}} (exp\{−v^{t}B(r)^{−1}v/2\} + o_{u}(1))  (4)

for r ∈ R and n − k ∈ Λ_{f}.

3. Classes of Admissible Functions

In this section we state various theorems that allow us to establish admissibility for generating functions for a variety of combinatorial structures. We begin with two theorems for multiplying admissible functions: Theorem 2 allows us to combine structures of similar size and Theorem 3 allows us to make (minor) modifications in our structures. Theorem 4 allows us to do simple multisection of admissible functions; that is, limit attention to structures with simple congruence properties. As already remarked H-admissible functions are admissible (with gradient a = a and B = b). In addition, the exponentials of polynomials considered in Theorems 2 and 3 of [2] are superadmissible. The proofs given there suffice, but the notation differs somewhat: Θ(r) is called D(r). It seems likely that one could extend the results in [2] to larger classes of polynomials and/or larger domains R. In Theorems 5–7 we construct a variety of admissible functions of the form exp {yC(x)}.

Suppose f is admissible in R with angles Θ. Suppose there are variables not appearing in f. We extend R and Θ to include these variables by forming the Cartesian product of R with copies of (0, ∞) and the Cartesian product of Θ with copies of [−π, π]. We extend a and B by adding entries of zeroes; however, we ignore the appended coordinates when computing |B| and when determining admissibility.

Theorem 2. We assume the various objects associated with f and g are extended as described above so that they include the same set of variables. Suppose that

• f is super-admissible in R with angles Θ_{f};

• g is super-admissible in R with angles Θ_{g};

• |B_{f}(r) + B_{g}(r)| is unbounded on R;

• there are constants C and k such that

|B_{f}(r) + B_{g}(r)| ≤ C min(|B_{f}(r)|^{k}, |B_{g}(r)|^{k}) for r ∈ R.  (5)

Then fg is super-admissible in R with angles Θ_{fg}(r) = Θ_{f}(r)∩Θ_{g}(r). Furthermore, Λ_{fg} = Λ_{f} + Λ_{g}, the the set of vectors u + v where u ∈ Λ_{f} and v ∈ Λ_{g}, and we may take

a_{fg} = a_{f} + a_{g} and B_{fg} = B_{f} + B_{g},

There are two important observations concerning Theorem 2:

• In using it, one normally chooses R to be as big a subset as possible of R_{f} ∩R_{g} such that (5) holds.

• Hayman shows that, if f(x) is H-admissible, then so is f(x) + p(x) when p(x) is a polynomial. This is not true for admissible functions. For example, if f(x) = g(x^{2}) is admissible, f(x) + x is not. This problem could be avoided if we changed the definition of Λ_{f} to use only sufficiently large n rather than all n. Unfortunately Theorem 2 would fail because, for example e^{x^{2}} and e^{x^{2}} + x would be super-admissible but their product would not be.

Theorem 3. Suppose that f is admissible (resp. super-admissible) in R with angles Θ and that g(re^{i0}) is analytic for r ∈ R. Let u = |B_{f}(r)|. Suppose that there are a_{g} and B_{g} such that

(a) Λ_{g} ⊆ Λ_{f};

(b) for r ∈ R and 0 ∈ Θ(r),

g(re^{i0}) = g(r) exp{ia_{g}(r)′0 − 0′B_{g}(r)0 + o_{u}(1)};  (6)

(c) there is a constant C such that |g(re^{i0})| ≤ Cg(r) for r ∈ R;

(d) there is a constant C such that |B_{f}(r) + B_{g}(r)| ≤ C|B_{f}(r)| for r ∈ R. Then fg is admissible (resp. super-admissible) in R with angles Θ and we may take

a_{fg} = a_{f} + a_{g} and B_{fg} = B_{f} + B_{g},

There are three important observations concerning Theorem 3:

• We do not assume that g is admissible.

• One may need to extend a_{g} and B_{g} as described before Theorem 2. In this case, Λ_{g} should also be extended by adding components containing zeroes to its vectors.

• If a_{g} and B_{g} are so small that (6) reduces to g(re^{i0}) = g(r)(1 + o_{u}(1)), the contribution of g to the asymptotics in Theorem 1 is simply a factor of g(r).

Theorem 4. Let f(x) = ∑ a_{n}x^{n} be a d-variable admissible (resp. super-admissible) function. Let Λ be a sublattice of Λ_{f} and suppose k is such that a_{k} ≠ 0. Define

g(x) = ∑_{n∈Λ} a_{k+n}x^{k+n}.

We may take Φ(g) ⊆ Φ(f). The function g is admissible (resp. super-admissible) with

Λ_{g} = Λ, a_{g} = a_{f}, B_{g} = B_{f}, R_{g} = R_{f}, and Θ_{g} = Θ_{f}.

Theorem 5. Suppose that

• f(x) = ∑ a_{n}x^{n} is an H-admissible function with a_{0} = 0 and (possibly infinite) radius of convergence R;

• K is a subset of {0, 1, …, m − 1};

• λ_{k} are nonnegative reals for 0 ≤ k < m with λ_{k} > 0 if and only if k ∈ K. Define λ_{n} = λ_{k} whenever n ≡ k (mod m),

g(x) = ∑_{n=0}^{∞} λ_{n}a_{n}x^{n},  (7)

and \overline{λ} = (∑_{k=0}^{m−1} λ_{k})/m. Then:

(a) For some R_{0} < R, the function h(x) = e^{g(x)} is super-admissible in R = {r | R_{0} < r < R} with angles

Θ(r) = {θ | |θ| < 1/g(r)^{1/3+ϵ}}

and the gradient a and B, provided ϵ > 0 is sufficiently small. Also

a_{h}(r) ∼ \overline{λ}rf′(r) and B_{h}(r) ∼ \overline{λ}r(rf′(r))′.

If d denotes the greatest common divisor of m and the elements of K, then Λ_{h} is generated by (d); that is, Λ_{h} = ℤ(d).

(b) For some R_{0} < R and all δ > 0, the function h(x, y) = e^{yg(x)} is superadmissible in

R = {(r, s) | R_{0} < r < R and g(r)^{δ−1} < s < g(r)^{1/δ}}.

with angles

Θ(r, s) = {0 | |θ_{k}| < 1/(sg(r))^{1/3+ϵ}}

and the gradient a and B, provided ϵ > 0 is sufficiently small. Also

a_{h}(r, s) ∼ \overline{λ}s ( \begin{matrix}rf′(r) \\ f(r) \end{matrix} ) , B_{h}(r, s) ∼ \overline{λ}s ( \begin{matrix}r(rf′(r))′ & rf′(r) \\ rf′(r) & f(r) \end{matrix} ) ,

and

|B_{h}(r, s)| = \frac{s^{2}}{2} ∑_{n,k}(n − k)^{2}λ_{n}a_{n}λ_{k}a_{k}r^{n+k}.  (8)

If k ∈ K and d denotes the greatest common divisor of m and differences of pairs of elements of K, then Λ_{h} is generated by (k, 1) and (d, 0); that is Λ_{h} = ℤ(d, 0) + ℤ(k, 1).

Theorem 6. Suppose that • f(x) is analytic in |x| < 1 with f(0) = 1 and f(x) ≠ 0 for |x| < 1;

• x^{−k} log f(x) has a power series expansion in powers of x^{m} for some integers k and m with 0 ≤ k < m;

• C(r) is a positive function on (0, 1) with

(1 − r)\frac{C′(r)}{C(r)} → 0 as r → 1;

• there exist positive constants α and β with β < 1 such that

log f(x) ∼ C(|x|)(1 − x)^{−α} as x → 1

uniformly for | arg x| ≤ β(1 − r) and such that

|log f(re^{iθ})| ≤ |log f(re^{iβ(1−r)})| for β(1 − r) ≤ |θ| ≤ π/m.  (9)

Then, with g(r) = log f(r):

(a) For some R_{0} < 1, the function f(x) is super-admissible in R = {r | R_{0} < r < 1}

with angles

Θ(r) = {θ | |θ| < (1 − r)/g(r)^{1/3+ϵ}}

and the gradient a and B, provided ϵ > 0 is sufficiently small. Also Λ_{f} = ℤ(d) where d = gcd(k, m).

(b) For some R_{0} < 1 and all δ > 0, the function h(x, y) = f(x)^{y} is super-admissible

in

R = {(r, s) | R_{0} < r < 1 and g(r)^{δ−1} < s < g(r)^{1/δ}}.

with angles

Θ(r, s) = {(θ, φ) | |θ| < (1 − r)/(sg(r))^{1/3+ϵ} and |φ| < 1/(sg(r))^{1/3+ϵ}}

and the gradient a and B, provided ϵ > 0 is sufficiently small. Also Λ_{h} = ℤ(m, 0) + ℤ(1, k).

Theorem 7. Suppose that f(x) = ∑ a_{n}x^{n} has radius of convergence R > 0 and that a_{n} ≥ 0 for all n. Let ν(r) be the value of n such that a_{n}r^{n} is a maximum. Suppose that, for every ϵ > 0, ν(r) = o(f(r)^{ϵ}) as r → R. Suppose that there exist ρ < 1, A, a function K(m) > 0 and an N depending on ρ, A, and K such that, for all ν = ν(r) > N and all k > 0,

Aρ^{k} ≥ \frac{a_{t}r^{t}}{a_{ν}r^{ν}} where t = ν ± k  (10)

and

K(m) ≤ \frac{a_{j}r^{j}}{a_{ν}r^{ν}} whenever |j − ν| ≤ m.  (11)

Then f(x) is entire and the conclusions of Theorem 5 hold for it.

4. Applications

Admissibility allows one to compute asymptotics for the coefficients of a variety of generating functions, but the accuracy of the method is limited by one’s ability to estimate the solution of a(r) = n and then estimate f(r) and r^{n} accurately. On the other hand, admissibility allows one to establish asymptotic normality rather easily, and obtaining asymptotic estimates for the means and covariances is usually fairly easy: Suppose our generating function is of the form f(x, y) and is ordinary in y. Partition all vectors and matrices into block form according the the two sets of variables x and y. Let a_{n,k} be the coefficients of f. Set a(r, 1) = (n, k^{∗}), solve for r asymptotically in terms of n and use this to compute k^{∗} and B(r, 1) asymptotically as functions of n. Let n go to infinity in a way that (r, 1) ∈ R and |B| → ∞. From Theorem 1 and the formula ([13, pp. 25–26])

( \begin{matrix}B_{1,1} & B_{1,2} \\ B′_{1,2} & B_{2,2} \end{matrix} )^{−1} = ( \begin{matrix}A & C \\ C′ & D^{−1} \end{matrix} ) where D = B_{2,2} − B′_{1,2}(B_{1,1})^{−1}B_{1,2}, (12)

it follows that a_{n,k}/ ∑_{k} a_{n,k} satisfies a local limit theorem with means vector and covariance matrix asymptotic to k^{∗} and D, respectively. When x and y are 1dimensional, D = |B|/B_{1,1}.

Example 1 (Stirling Numbers of the Second Kind). With multivariate situations, it is important to know the range of values of the subscripts of the coefficients (rather than the variables in the generating function) for which the asymptotics applies. We examine exp {y(e^{x} − 1)}, the generating function for S(n, k), the Stirling numbers of the second kind. Let |x| = r and |y| = s. Since f(x) = e^{x} − 1 is H-admissible, we can apply Theorem 5(b) with m = 1 and λ_{0} = 1. (There is no multisection.) Then

a(r, s) = s ( \begin{matrix}re^{r} \\ e^{r} − 1 \end{matrix} ) , B(r, s) = s ( \begin{matrix}(r^{2} + r)e^{r} & re^{r} \\ re^{r} & e^{r} − 1 \end{matrix} ) ,

and

R = {(r, s) | R_{0} < r and e^{r(δ−1)} < s < e^{r/δ}}.

Setting a = (n, k), we obtain

(i) n/k ∼ r and (ii) the value of r lies between the solutions of n = re^{rδ} and n = re^{r(1+1/δ)}. Thus r is between roughly δ log n and log n/δ. It follows from this and (i) that we have admissibility as long as (k log n)/n is bounded away from 0 and ∞. Consequently, for any positive constants c and C, Theorem 1 provides uniform asymptotics for S(n, k) when

\frac{cn}{log n} < k < \frac{Cn}{log n}.  (13)

If, instead, we set a(r, 1) = (n, k^{∗}), we obtain the equations n = re^{r} and k^{∗} = e^{r} − 1. Hence r ∼ log n and k^{∗} ∼ n/ log n. Using (12), we obtain

D = (e^{r} − 1) − (re^{r})^{2}/(r^{2} + r)e^{r} ∼ e^{r}/r ∼ n/(log n)^{2}

and so S(n, k) satisfies a local limit theorem with mean and variance asymptotic to n/ log n and n/(log n)^{2}, respectively, a result obtained by Harper [9].

Example 2 (Other Set Partitions). The coefficient of y_{1}^{k_{1}}y_{2}^{k_{2}} ⋯ x^{n}/n! in

f(x, y) = exp{∑_{k=1}^{∞} y_{k}x^{k}/k!}  (14)

is the number of partitions of an n-set with exactly k_{i} blocks of size i. In the previous example, we set y_{i} = y for all y. Other results are possible, particularly when one is interested in residue classes modulo m. Some illustrative examples follow.

Let K ⊂ {0, 1, …, m − 1} and set y_{i} = 1 when i modulo m is in K and 0 otherwise. Since e^{x} − 1 is H-admissible, g(x) = f(x, y) is admissible by Theorem 5(a). The coefficient of x^{n}/n! is the number of set partitions of a n-set with block sizes congruent modulo m to elements in K.

Suppose, instead, we set y_{i} = y when i modulo m is in K and 0 otherwise. Then Theorem 5(b) applies and the coefficient of x^{n}y^{k}/n! in g(x, y) is the number of partitions of an n-set with exactly k blocks all of whose sizes are congruent modulo m to elements in K. Asymptotic normality follows as it did for the Stirling numbers and the mean and variance are asymptotically the same as we found there.

If all but a finite number of y_{i} = 0 and the rest are equal to y, f(x, y) is the exponential of a polynomial and admissibility follows by the methods in [2] unless the polynomial is a monomial.

Not every choice of which y_{i} are zero leads to an admissible function. For example, it can be shown that f(x) = exp {∑ x^{n_{k}}/(n_{k})!} is not admissible if the n_{k} grow sufficiently rapidly since f(re^{iθ})/f(r) is not sufficiently small when r is near n_{k} and θ is a multiple of 2π/n_{k}.

From (14), [x^{n}y_{e}^{k_{e}}y_{o}^{k_{o}}/n!](exp{y_{e}(cosh x − 1)} exp{y_{o} sinh x}) is the number of partitions of an n-set that have k_{e} blocks of even size and k_{o} blocks of odd size. By Theorem 5(b), f(x, y_{e}) = exp{y_{e}(cosh x − 1)} and g(x, y_{o}) = exp{y_{o} sinh x} are super-admissible and

R_{f} = R_{g} = {(r, s) | R_{0} < r and e^{(δ−1)r} < s < e^{r/δ}}
Θ_{f} = Θ_{g} = {0 | |θ_{k}| < (e^{−r}/s))^{1/3+ϵ}}
B_{f}(r, s_{e}) = s_{e} ( \begin{matrix}r^{2} cosh r + r sinh r & r sinh r \\ r sinh r & cosh r − 1 \end{matrix} )
B_{g}(r, s_{o}) = s_{o} ( \begin{matrix}r^{2} sinh r + r cosh r & r cosh r \\ r cosh r & sinh r \end{matrix} ) .

(15)

Hence

|B_{f}| = s_{e}^{2}r(sinh r − r)(cosh r − 1) ∼ s_{e}^{2}re^{2r}/4

and

|B_{g}| = s_{o}^{2}r(sinh r cosh r − r) ∼ s_{o}^{2}re^{2r}/4.

We now apply Theorem 2. Since

B_{f} + B_{g} = ( \begin{matrix}r(rs_{e} + s_{o}) cosh r + r(rs_{o} + s_{e}) sinh r & rs_{e} sinh r & rs_{o} cosh r \\ rs_{e} sinh r & s_{e}(cosh r − 1) & 0 \\ rs_{o} cosh r & 0 & s_{o} sinh r \end{matrix} ) ,

we have

|B_{f} + B_{g}| = rs_{e}s_{o}(cosh r − 1)(s_{e} sinh r(sinh r − r) + s_{o}(cosh r sinh r − r))
∼ s_{e}s_{o}(s_{e} + s_{o})re^{3r}/8.

It follows that fg is super-admissible in

R = {(r, s_{e}, s_{o}) | R_{0} < r and e^{(δ−1)r} < s_{e}, s_{o} < e^{r/δ}}

with angles

Θ(r, s_{e}, s_{o}) = {0 | |θ_{k}| < (e^{−r}/ max(s_{e}, s_{o})))^{1/3+ϵ}}.

Consequently we obtain asymptotics for the coefficients provided k_{e} log n/n and k_{o} log n/n are bounded away from 0 and ∞.

Suppose we want to count partitions by the number of non-singleton blocks. The generating function is f(x, y)g(x) where

f(x, y) = exp{y(e^{x} − x − 1)} and g(x) = e^{x}.

Apply Theorem 5(b) without multisection to show that f is super-admissible with angles

Θ(r, s) = {0 | |θ_{k}| < (e^{−r}/s)^{1/3+ϵ}}.

Now apply Theorem 3. The conditions on g are easily checked. In particular, one must verify (6) for |θ| < e^{−δr}. In this range

exp {re^{iθ}} = exp{r(1 + O(θ))} ∼ e^{r}.

Unfortunately, the theorems do not allow us to do the complementary problem— count partitions by number of singleton blocks using the generating function e^{xy} exp {e^{x} − 1 − x}.

Fix integers k and m. Let a_{n,j} be the number of partitions of an n-set into j blocks such that the total number of elements in blocks of odd cardinality is congruent to k modulo m. The generating function is fh where

f(x, y) = exp {y(cosh x − 1)} , g(x, y) = exp {y sinh x} ,

and h(x, y) is the sum of those terms in g for which the power of x modulo m is k. By Theorem 5, f and g are super-admissible with the R, Θ and B given by (15). By Theorem 4 with Λ = mℤ × ℤ, h is super-admissible. By Theorem 2, fh is super-admissible and, furthermore, we may take R and B to be as in Example 1. It follows that asymptotics are obtainable for a(n, j) whenever (13) holds.

Example 3 (Decompositions of Vector Spaces). Let D_{n,k}(q) be the number of decompositions of an n-dimensional vector space over GF(q) as a direct sum of k nonzero subspaces where the order of the subspaces is irrelevant. It follows from Example 11 of Bender and Goldman [1] that

h(x, y) = 1 + ∑_{n=1}^{∞} ∑_{k=1}^{n} \frac{D_{n,k}(q)x^{n}y^{k}}{c_{n}} = e^{yf(x)} where f(x) = ∑_{n=1}^{∞} \frac{x^{n}}{c_{n}} (16)

and c_{n} = (q^{n} −1) ⋯ (q^{n} −q^{n−1}). Let C_{i} stand for some positive constant. We apply Theorem 7 without multisection. Note that c_{n} ∼ Qq^{n^{2}} where Q = ∏(1−q^{−k}). The largest term in f(r) is near the solution ν of r = q^{2ν}. If m = ν ± t is a positive integer, then a simple calculation shows that

C_{1}q^{−t^{2}} < \frac{r^{m}/c_{m}}{r^{ν}/Qq^{ν^{2}}} < C_{2}q^{−t^{2}}.

Thus Theorem 7 applies. We obtain n/k ∼ ν = (log_{q} r)/2. Since C_{3}q^{ν^{2}} < f(r) < C_{4}q^{ν^{2}} and the theorem requires f(r)^{δ} < sf(r) < f(r)^{1/δ}, it follows that ϵ(log n)^{1/2} < ν < (log n)^{1/2}/ϵ. Thus asymptotics are obtained when k(log n)^{1/2}/n is bounded away from 0 and ∞.

By solving (n, k^{∗}) = a(r, 1) = (rf′(r), f(r)) for r and k^{∗}, the asymptotic formula gives us a local limit theorem for D_{n,k}(q) as n → ∞. We now study the asymptotic mean and variance. Define ν and δ as functions of r by

ν = [(log_{q} r)/2] = (log_{q} r)/2 − δ.

Using ν → ∞, (10), (11), and (8), we have

f(r) ∼ \frac{1}{Q} ∑_{t=−∞}^{∞} \frac{r^{ν+t}}{q^{(ν+t)^{2}}} = \frac{q^{ν^{2}+2δν}}{Q} ∑_{t=−∞}^{∞} \frac{1}{q^{t^{2}−2δt}}

rf′(r) ∼ \frac{νq^{ν^{2}+2δν}}{Q} ∑_{t=−∞}^{∞} \frac{1}{q^{t^{2}−2δt}} ∼ νf(r)

r(rf′(r))′ ∼ \frac{ν^{2}q^{ν^{2}+2δν}}{Q} ∑_{t=−∞}^{∞} \frac{1}{q^{t^{2}−2δt}} ∼ ν^{2}f(r)

|B(r, 1)| ∼ \frac{q^{2ν^{2}+4δν}}{2Q^{2}} ∑_{t,u=−∞}^{∞} \frac{(t − u)^{2}}{q^{t^{2}+u^{2}−2δ(t+u)}} ∼ \frac{q^{2ν^{2}+4δν}(S_{2}S_{0} − S_{1}^{2})}{Q^{2}},

where

S_{k} = S_{k}(δ, q) = ∑_{t=−∞}^{∞} \frac{t^{k}}{q^{t^{2}−2δt}} .

From n = r′f(r) we have log_{q} n ∼ ν^{2} and so ν ∼ \sqrt{log_{q} n}. Thus the mean k^{∗} is asymptotic to n/\sqrt{log_{q} n}. Since the variance is given by |B|/B_{1,1}, we have

variance ∼ \frac{C(δ, q)n}{(log_{q} n)^{3/2}} where C(δ, q) = \frac{S_{2}S_{0} − S_{1}^{2}}{S_{0}^{2}} .

To evaluate the sums C(δ, q), one needs to know δ and this depends on more detailed knowledge of ν and r than we have obtained. However, we can say something about it:

• We have C(δ + 1, q) = C(δ, q) = C(−δ, q) from which it follows that C(δ, q) is determined by its values on 0 ≤ δ ≤ 1/2.

• By using the t = 0 and ±1 terms in S_{k} we find that,

for fixed δ and q → ∞, C(δ, q) ∼ \{ \begin{matrix}2/q, & if δ = 0 \\ 1/q^{1−2δ}, & if 0 < δ < 1/2 \\ 1/4, & if δ = 1/2. \end{matrix}

• Since r ∼ q^{2ν} and n = rf′(r), which is between Cνq^{ν^{2}} and C′νq^{ν^{2}}, we have r ∼ exp \{2 log q\sqrt{log_{q} n}\}. Hence, as n → ∞, C(δ(n), q) approaches a periodic

function of exp \{2 log q\sqrt{log_{q} n}\}. Since the period of δ as a function of r is 1, its period in terms of n is about

n\sqrt{log_{q} n} exp \{−2 log q\sqrt{log_{q} n}\} .

If we use the Eulerian generating function with c_{n} = (q^{n} − 1) ⋯ (q − 1) in (16), we obtain similar results with q replaced by q^{1/2} and D_{n,k}(q) counts direct sum decompositions into orthogonal subspaces.

Example 4 (Tagged Permutations). A tagged permutation is a permutation written in one-line form together with a distinguished increasing subsequence. Following Flajolet and Sedgewick [4], the generating function is given by

h(x, y) = \frac{1}{1 − x} exp \{\frac{xy}{1 − x}\} ,

where the exponential variable x keeps track of permutation length and the ordinary variable y keeps track of distinguished subsequence length. Lifschitz and Pittel [11] and Flajolet and Sedgewick [4] obtained asymptotics for the coefficients of h(x, 1) using real and complex analysis, respectively. Using Theorem 6(b) with f(x) = \frac{x}{1−x}

and C(r) = 1, we see that f(x, y) = exp \{\frac{xy}{1−x}\} is super-admissible. One easily computes

a_{f}(r, s) = s ( \frac{r}{(1−r)^{2}} ; \frac{r}{1−r} ) , B_{f}(r, s) = s ( \begin{matrix}\frac{r(1+r}{(1−r)^{3}} & \frac{r}{(1−r)^{2}} \\ \frac{r}{(1−r)^{2}} & \frac{r}{1−r} \end{matrix} ) ,

and |B_{f}(r, s)| = \frac{r^{3}s^{2}}{(1−r)^{4}} .

We now apply Theorem 3 with g(x, y) = \frac{1}{1−x} to conclude that h(x, y) is superadmissible. Only (6) requires any effort. For (θ, φ) ∈ Θ_{f}(r, s), where Θ_{f} is given by Theorem 6(b), we have

log(1 − re^{iθ}) = log(1 − r) + O(θ/(1 − r)) = log(1 − r) + O ((\frac{1−r}{s} )^{1/3+ϵ}) .

Using the definition or R in Theorem 6 and the above formula for |B_{f}(r, s)|, one easily verifies that the big-oh is o_{u}(1).

Let t(n, k) be the number of n-long tagged permutations with tags of length k. It follows from the above work that t(n, k) is asymptotically normal as n → ∞, with mean and variance asymptotic to \sqrt{n} and \sqrt{n}/2, respectively. It also follows from the formula for R that asymptotics can be obtained for tagged permutations whenever (1−r)^{1−δ} < s < (1−r)^{−1/δ}. Since k ∼ \frac{s}{1−r} and n ∼ \frac{s}{(1−r)^{2}} , some algebra shows that we can obtain asymptotics whenever n^{δ/(1+δ)} < k < n^{(1+δ)/(1+2δ)}; that is, we can obtain asymptotics for t(n, k) as n → ∞ provided n^{ϵ} < k < n^{1−ϵ} for some ϵ > 0.

Example 5 (Covering Complete Graphs). A cover of the complete graph with graphs of some specified type is simply the number of sets of graphs of that type such that the total number of vertices is n. The exponential formula f(x, y) = e^{yg(x)} applies, where g(x) is the exponential generating function for graphs of the desired type. Here are some examples taken from problems 3.3.5–7 in Goulden and Jackson’s text [8, p. 187].

• The generating function for coverings with complete graphs is exp{y(e^{x} − 1)}, which was studied in Example 1.

• The generating function for coverings with complete bipartite graphs having at least one vertex in each part of the bipartition is exp{y(e^{x} − 1)^{2}/2} and Theorem 5(b) applies.

• The generating function for coverings with star graphs is exp{y(xe^{x} − x^{2}/2)} and Theorem 5(b) applies. (A star graph on k ≥ 1 vertices is a tree consisting of one vertex of degree k−1 to which the remaining k−1 vertices are attached.)

• The generating function for coverings with paths is exp \{\frac{yx(2−x)}{2(1−x)}\} and Theorem 6(b) applies.

5. Proofs of Theorems

Throughout the proofs, ϵ and C stand for positive constants, not necessarily the same at each occurrence. The value of ϵ is intended to be small whereas C need not be. References to results in [10] have an H prefixed as in Theorem H.II.

Proof (of Theorem 1): We follow essentially the same argument as in [10] and [2]. With f(x) = ∑ a_{n}x^{n} and d the dimension of x, we have

a_{n}r^{n} = \frac{1}{(2π)^{d}} ∫ ⋯∫_{[−π,π]^{d}} f(re^{i0}) exp \{−in′0\} d0.

Suppose that a_{n} ≠ 0. Let u ∈ Λ_{f}^{∗}. The integrand is invariant when 0 is replaced by 0 + 2πu because u′(m − n) is an integer whenever a_{m} ≠ 0. It follows that we can restrict the integral to Φ(f) and multiply the result by (2π)^{d}/vol(Φ(f)) = d(Λ_{f}).

Let Θ^{∗}(r) be the largest set of 0 such that c0 ∈ Θ(r) when 0 < c < 1. Note the following:

• The interior of Θ^{∗}(r) is contained in Θ(r).

• exp {−0′B0/2} = o_{u}(1)/|B(r)|^{1/2} on the boundary of Θ^{∗}(r) because no points on the boundary of Θ^{∗}(r) are in Θ(r).

• For every 0, there is an ϵ(r) such that ϵ0 ∈ Θ^{∗}(r) because the origin is in the

interior of Θ(r). Since B is positive definite, replacing 0 by c0 with c > 1 increases 0′B0 and so

exp {−0′B0/2} = o_{u}(1)/|B(r)|^{1/2} for all 0 ∉ Θ^{∗}(r).  (17)

It follows that

a_{n}r^{n} = \frac{d(Λ_{f})}{(2π)^{d}} ∫ ⋯∫_{Θ^{∗}(r)} f(re^{i0}) exp \{−in′0\} d0 + \frac{o_{u}(f(r))}{|B(r)|^{1/2}} .

Using (1) for 0 ∈ Θ^{∗}(r) gives us

f(re^{i0}) exp {−in′0} = f(r)(1 + o_{u}(1)) exp{iv′0 − 0′B(r)0/2}.

Since B is positive definite, we can write B = S′S for some real d × d matrix S. With y = S0 and w^{2} = w′w,

iv′0 − 0′B0/2 = iv′S^{−1}y − y^{2}/2
= −((S′)^{−1}v)^{2}/2 − (y − i(S′)^{−1}v)^{2}/2
= −v′B^{−1}v/2 − (y − i(S′)^{−1}v)^{2}/2.

Hence

∫ ⋯∫_{Θ^{∗}} exp {iv′0 − 0′B(r)0/2} d0

= \frac{exp\{−v′B(r)^{−1}v/2\}}{|B(r)|^{1/2}} ∫ ⋯∫_{SΘ^{∗}} exp\{−(y − i(S′)^{−1}v)^{2}/2\}dy

= \frac{exp\{−v′B(r)^{−1}v/2\}}{|B(r)|^{1/2}} ∫ ⋯∫_{ℝ^{d}} exp\{−(y − i(S′)^{−1}v)^{2}/2\}dy

+ \frac{O(1) exp\{−v′B(r)^{−1}v/2\}}{|B(r)|^{1/2}} ∫ ⋯∫_{T} exp\{−x^{2}/2\}dx,

where, by (17), T is a set of x ∈ ℝ^{d} for which exp {−x^{2}/2} = o_{u}(1)/|B|^{1/2}. It follows that the integral over T is o_{u}(1). The integral over ℝ^{d} is the product of d integrals of the form

∫_{−∞}^{∞} exp {−(y − ic)^{2}/2} dy

and so equals (2π)^{d/2}.

Proof (of Theorem 2): Let h = fg. As already described before Theorem 2, we can extend the R, Θ, a and B values for f and g to include all the variables in h. We can expand Λ as well by adding components which equal 0 to the vectors in Λ. Then Λ^{∗} will no longer be a lattice—the corresponding components of vectors there can be any real numbers since a real number times 0 is 0.

For the function h, we must verify (a)–(d) and (3) in the definition of superadmissibility in Section 2. Property (a) is immediate.

We now prove (b). Since v′B_{h}v = v′B_{f}v + v′B_{g}v and since each summand is nonnegative by the positive semidefiniteness of the extended B_{f} and B_{g}, it follows that B_{h} is positive semidefinite. Suppose that v′B_{h}v = 0. Then v′B_{f}v = 0 and v′B_{g}v = 0. Since the original B_{f} is positive definite, the components of v associated with the variables of f must be 0. Similarly, the components of v associated with the variables of g must be 0. Hence v = 0 and so B_{h} is positive definite.

Using (5) and Θ_{h} = Θ_{f} ∩ Θ_{g}, we obtain (c) and (d).

Before proving (3), we prove the claim concerning Λ_{h}. Clearly Λ_{h} ⊆ Λ_{f} + Λ_{g}, but equality may fail due to cancellation of terms when computing fg. Note that

(Λ_{f} + Λ_{g})^{∗} = Λ_{f}^{∗} ∩ Λ_{g}^{∗}

and the operator ^{∗} reverses inclusion. Hence it suffices to prove that Λ_{h}^{∗} ⊆ Λ_{f}^{∗} ∩ Λ_{g}^{∗}. Suppose to the contrary that v ∈ Λ_{h}^{∗} and v ∉ Λ_{f}^{∗} ∩ Λ_{g}^{∗}, say v ∉ Λ_{f}^{∗}. We may choose r so that |B_{h}| is as large as we wish and hence also |B_{f}| by (5). From (c) in the definition of admissibility, it follows that Θ_{f} +v will be disjoint from Θ_{f} +Λ_{f}^{∗} and so, by (3) for f and (5), we have f(re^{2πiv}) = o_{u}(f(r)). Since v ∈ Λ_{h}^{∗}, h(re^{2πiv}) = h(r), we have the contradiction

f(r)g(r) = h(r) = h(re^{2πiv}) = f(re^{2πiv})g(re^{2πiv}) = o_{u}(1)f(r)g(r).

This proves Λ_{h} = Λ_{f} + Λ_{g} and also

Λ_{h}^{∗} = Λ_{f}^{∗} ∩ Λ_{g}^{∗}.  (18)

We now turn to (3). Since Λ_{f}^{∗} + Λ_{g}^{∗} is a lattice, it follows that, whenever the diameters of Θ_{f}(r) and Θ_{g}(r) are sufficiently small,

(Θ_{f}(r)+2πΛ_{f}^{∗})∩(Θ_{g}(r)+2πΛ_{g}^{∗}) = (Θ_{f}(r)∩Θ_{g}(r))+2π(Λ_{f}^{∗}∩Λ_{g}^{∗}) = Θ_{h}(r)+2πΛ_{h}^{∗},

by (18) and the definition of Θ_{h}. Consequently, when min(|B_{f}(r)|, |B_{g}(r)|) is sufficiently small and 0 is in the complement of Θ_{h}(r) relative to Φ(h), (3) must hold for at least one of f and g. This implies (3) for h.

Proof (of Theorem 3): Since Λ_{g} ⊆ Λ_{f}, it follows that Λ_{fg} = Λ_{f}. The remainder of the proof is straightforward and will be omitted.

Proof (of Theorem 4): By multidimensional multisection of series,

g(x) = \frac{1}{d(Λ)} ∑_{v∈Λ^{∗}/ℤ^{d}} f(xe^{2πiv})e^{−2πiv′k},

where the sum makes sense since e^{−2πiv′k} and the vector e^{2πiv} are constant on a coset of Λ^{∗}/ℤ^{d}. Noting that, when a_{n} ≠ 0, the value of e^{2πiv′(n−k)} is constant on a coset of Λ^{∗}/Λ_{f}^{∗}, we have

g(x) = \frac{1}{d(Λ)} ∑_{v∈Λ^{∗}/Λ_{f}^{∗}} f(xe^{2πiv})e^{−2πiv′k}.

When the diameter of Θ_{f}(r) is sufficiently small it follows that, for arg(x) ∈ Θ_{f}(r), only the v = 0+Λ_{f}^{∗} term is large. Let Φ(g) be a fundamental region for Λ^{∗} contained in Φ(f). If arg(x) is in the complement of Θ_{f}(r) in Φ(g), then none of arg(x) + 2πv is in Θ_{f}(r) + Φ(f). Hence g(x) is small in this case.

The following two lemmas lay the foundation for proving Theorem 5.

Lemma 1. In the notation of Theorem 5 with F = e^{f} and G = e^{g}, we have g(r) ∼ \overline{λ}f(r),

a_{G}(r) = rg′(r) ∼ \overline{λ}rf′(r) = \overline{λ}a_{F} (r) = o_{u}(g(r)^{1+ϵ}),
B_{G}(r) = r(rg′(r))′ ∼ \overline{λ}r(rf′(r))′ = \overline{λ}B_{F} (r) = o_{u}(g(r)^{1+ϵ}),
g(re^{iθ}) = g(r) + iθa_{G}(r) − θ^{2}B_{G}(r)/2 + o_{u}(θ^{3}g(r)^{1+ϵ})  (19)

for all ϵ > 0.

Proof: Using the asymptotic formula for the coefficients of admissible functions and an argument like that in Hayman’s proof of Theorem H.II, the results for a and B follow in a straightforward manner. The last equation follows from Taylor’s Theorem with remainder:

H(θ) = H(0) + H′(0)θ + H′′(0)θ^{2}/2 + ∫_{0}^{θ}(t − θ)^{2}H′′′(t) dt/2

with H(θ) = g(re^{iθ}) and the observation that for r sufficently near R,

|H′′′(θ)| ≤ H′′′(0) = O(r^{3}f′′′(r)) = O(f(r)^{1+ϵ}),

where we used Theorem H.III for growth of derivatives.

Lemma 2. Suppose f is H-admissible in |x| < R, g is given by (7), and C is a compact subset of (0, ∞). Then there is an R_{1} < R depending on f, C, and ϵ such that:

(a) When d is as in Theorem 5(a),

ℜ(g(re^{iθ})) ≤ g(r) − g(r)^{1−2c−ϵ}

whenever R_{1} < r < R, c ∈ C, and g(r)^{−c} ≤ |θ| ≤ π/d.

(b) When d is as in Theorem 5(b),

|g(re^{iθ})| ≤ g(r) − g(r)^{1−2c−ϵ}

whenever R_{1} < r < R, c ∈ C, and g(r)^{−c} ≤ |θ| ≤ π/d.

Proof: To prove the existence of R_{1}, it suffices to consider a fixed c ∈ C since compactness of C allows us to take the maximum R_{1}.

Let x = re^{iθ}. We assume that r is sufficiently near R for various asymptotic estimates given below. By H-admissibility, the coefficients of all sufficiently high powers of x in f(x) are nonzero and a_{f}(r) → ∞ as r → R. Let r be so close to R that all coefficients of f(x) with n ≥ a_{f}(r) are nonzero. Let t be the least integer such that mt ≥ a_{f}(r) and define α_{k} = a_{mt+k}x^{mt+k}. By H-admissibility, we have

|α_{k}| ∼ f(r)/\sqrt{2πb_{f}(r)}.

Hayman proves that b(r) = o(a(r)^{2}) = o(f(r)^{ϵ}) for admissible functions. Using Lemma 1, it follows that mt = o(g(r)^{ϵ}) and |α_{k}| > Cg(r)^{1−ϵ}. Let θ_{k} be (mt + k)θ reduced modulo 2π so that |θ_{k}| ≤ π. Then

|α_{k}| − ℜα_{k} = (1 − cos θ_{k})|α_{k}| > Cg(r)^{1−ϵ}θ_{k}^{2}.

It suffices to show that there is some k for which λ_{k} ≠ 0 and |θ_{k}| ≥ g(r)^{−c−ϵ}.

Suppose there is no such k. By the gcd condition, there are integers μ and μ_{k} for 0 ≤ k < m such that μ_{k} = 0 when λ_{k} = 0 and

d = μm + ∑_{k} μ_{k}k.

Let j be such that λ_{j} ≠ 0 and define

φ = μ(θ_{m+j} − θ_{j}) + ∑_{k=0}^{m−1} μ_{k}θ_{k}.

Since |θ_{k}| = O(g(r)^{−c−ϵ}), we have |φ| = O(g(r)^{−c−ϵ}). Modulo 2π,

φ ≡ μ(mθ) + ∑_{k=0}^{m−1} μ_{k}(mt + k)θ ≡ dθ + (t ∑_{k=0}^{m−1} μ_{k})mθ ≡ dθ + (t ∑_{k=0}^{m−1} μ_{k})(θ_{m+j} − θ_{j})

and so

dθ ≡ φ − (t ∑_{k=0}^{m−1} μ_{k})(θ_{m+j} − θ_{j}) (mod 2π).

Since t = o(g(r)^{ϵ}), the right side of this congruence is O(g(r)^{−c−ϵ}). Hence θ differs from a multiple of 2π/d by O(g(r)^{−c−ϵ}), a contradiction to the assumption g(r)^{−c} ≤ |θ| ≤ π/d. This proves (a).

The proof of (b) is similar to that for (a) except that we now want to estimate

δ = |c_{i}α_{i}| + |c_{k}α_{k}| − |c_{i}α_{i} + c_{k}α_{k}|.

For two complex numbers z and w with β = arg(z\overline{w}), we have

(|z| + |w|)^{2} − |z + w|^{2} = 2|zw| cos β

whence

|z| + |w| − |z + w| = \frac{2|zw| cos β}{|z| + |w| + |z + w|} ≥ \frac{|zw| cos β}{|z| + |w|} .

Hence

δ ≥ C cos((i − k)θ)g(r)^{1−ϵ}.

The remainder of the proof is nearly the same as that for (a), with (i − k)θ modulo 2π in place of θ_{k}.

Proof (of Theorem 5): We begin by deriving the description of Λ_{h}. Let S be the set of indices n for which x^{n} has a nonzero coefficient in g(x). Since f is admissible, its coefficients are positive for all sufficiently large indices. Hence, for some sufficiently large J,

{k + jm | k ∈ K, j ≥ J} ⊆ S ⊆ {k + jm | k ∈ K, j ≥ 0}.  (20)

The powers of h(x) with nonzero coefficients are precisely those which are sums of elements of S. From this and (20), the proof that Λ_{h} = ℤ(d) is now straightforward. The powers of h(x, y) which have nonzero coefficients are precisely those of the form (n, j) where n is the sum of j elements of S. This can be rewritten as j(k, 1)+(n^{∗}, 0) where k ∈ S and n^{∗} is a sum j numbers of the form s − k where s ∈ S. From this and (20), the formula for Λ_{h} is straightforward.

To prove Theorem 5(a), one need only follow Hayman’s proof of Theorem H.VI with his use of Lemmas H.5 and H.6 replaced by our (19) and Lemma 2(a), respectively.

We now prove Theorem 5(b). Let x = re^{iθ}, let y = se^{iφ}, and let R be the radius of convergence of g.

One easily computes a and B in terms of g and its derivatives and then applies Lemma 1 to obtain the asymptotics in the theorem. With g(x) = ∑ c_{n}x^{n}, one has

2|B(r, s)|/s^{2} = 2r(rg′(r))′g(r) − 2(rg′(r))^{2}

= ∑_{n,k=0}^{∞} n^{2}c_{n}c_{k}r^{n+k} + ∑_{n,k=0}^{∞} c_{n}k^{2}c_{k}r^{n+k} − 2 ∑_{n,k=0}^{∞} nc_{n}kc_{k}r^{n+k}

= ∑_{n,k=0}^{∞}(n − k)^{2}c_{n}c_{k}r^{n+k}.

This proves (8).

Since B has positive diagonal entries, it will be positive definite if |B| > 0, which is the case for all r < R if c_{n} ≥ 0 for all n; however, a finite number of coefficients of the H-admissible function f may be negative. Let g^{∗} be g with these negative terms removed. The previous argument shows that

2|B^{∗}(r, s)|/s^{2} = ∑_{n,k=0}^{∞}(n − k)^{2}c_{n}^{∗}c_{k}^{∗}r^{n+k}

≥ ∑_{n,k=0}^{∞} c_{n}^{∗}c_{k}^{∗}r^{n+k} − ∑_{n=0}^{∞}(c_{n}^{∗}r^{n})^{2}

≥ g^{∗}(r)^{2} − sup_{n}(c^{∗}nr^{n})g^{∗}(r) = g^{∗}(r)^{2} − O(g^{∗}(r)/b_{f}(r)^{1/2})g^{∗}(r)

= g^{∗}(r)^{2}(1 + o(1)) as r → R.

Since the entries in B(r, s)/s and B^{∗}(r, s)/s differ by at most a polynomial in r, the determinants differ by at most a polynomial in r times the largest entry in B(r, s)/s. Since f is H-admissible, Lemma H.2 and Theorem H.III tell us that this difference is O(f(r)^{1+ϵ}). Since |B^{∗}| grows like g(r)^{2}s^{2} and R requires that s > g(r)^{δ−1}, it follows that r → R and |B(r, s)| → ∞ are uniformly the same condition in R. We also have |B(r, s))| > 0 provided r is sufficiently close to R; that is, R_{0} < r < R for some R_{0}.

By Lemma 1,

g(x) = g(r)(1 + iα(r)θ − β(r)θ^{2}/2 + O(g(r)^{ϵ}θ^{3}))

where α(r) = a_{G}(r)/g(r) and β(r) = B_{G}(r)/g(r). Hence

yg(x) = sg(r)(cos φ + i(α(r)θ + sin φ) − β(r)θ^{2}(cos φ)/2 + O(g(r)^{ϵ}θ^{3})) (21)
= sg(r)(1 + ia′0 − 0′B0) + sg(r)^{1+ϵ} ∑_{k=0}^{3} O(φ^{3−k}θ^{k})  (22)

where 0 = (θ, φ) and ϵ is any positive number. Let η be a small positive number. When

|θ| ≤ (1/sg(r))^{2η+1/3} and |φ| ≤ (1/sg(r))^{2η+1/3},

(22) establishes (1). When

|θ| ≤ (1/sg(r))^{η+1/3} and |φ| ≥ (1/sg(r))^{2η+1/3},

α(r)θ = o(φ) and so (21) gives us

|yg(x)| < sg(r)(1 − Cφ^{2}) ≤ sg(r) − C(sg(r))^{1/3−4η}

for r sufficiently near R, the radius of convergence of g. This establishes (3) in that range of 0.

We finish establishing the asymptotic requirements on exp{yg(x)} by proving (3) for |θ| ≥ (1/sg(r))^{η+1/3}. Let λ = λ(r) = log s/ log f(r). We are given δ − 1 ≤ λ ≤ 1/δ. Let c = 2(λ + 1)/5 and note that

g(r)^{c} = g(r)^{2(λ+1)/5} = (sg(r))^{2/5} > (sg(r))^{η+1/3}.

Apply Lemma 2(b) to obtain

\begin{aligned}|yf(x)| ≤ |y|(g(r) − g(r)^{1−2c−ϵ}) & = sg(r) − sg(r)(g(r))^{−2c−ϵ} \\ & = sg(r) − (sg(r))^{1/5}g(r)^{−ϵ}. \end{aligned}

Since ϵ is arbitrarily small and sg(r) > g(r)^{δ}, condition (3) follows.

Proof (of Theorem 6): This proof uses ideas from the proofs of Theorems 5 and H.XII. All conditions in the definition of super-admissibility are easily established except for (1) and (3). By (H.17.2), when |θ| < \frac{β(1−r)}{16r},

g(re^{iθ}) = g(r) + iθa_{f}(r) − θ^{2}B_{f}(r)/2 + E(r, θ)  (23)

where |E(r, θ)| < A(α, β)|θ|^{3}g(r)(1 − r)^{−3} for some function A(α, β). From this, one easily establishes (1) as in the proof of Theorem 5.

The proof of (3) for small θ and large φ is similar to the proof in Theorem 5. The following discussion is intended for part (b) of the theorem. Setting s = 1

allows one to prove part (a).

Suppose (1 − r)/(sg(r))^{1/3+ϵ} < |θ| < η(1 − r) for some small η to be specified later. Let ρ = θ/(1 − r). Hayman shows that

\frac{a_{f}(r)}{g(r)} ∼ \frac{α}{1 − r} and \frac{B_{f}(r)}{g(r)} ∼ \frac{α(α + 1)}{(1 − r)^{2}}

From (23),

|\frac{g(re^{iθ})}{g(r)}|^{2} = |1 − iθa_{f}/g − θ^{2}B_{f}/2g + O(ρ^{3})|^{2}
= (1 − θ^{2}B_{f}/2g + O(ρ^{3}))^{2} + (θa_{f}/g + O(ρ^{3}))^{2}
= 1 − αρ^{2}(1 + o(1)) + O(ρ^{3}).

It follows that with η (and hence ρ) sufficiently small we have

|\frac{g(re^{iθ})}{g(r)}|^{2} < 1 − αρ^{2}/2.

Since ρ ≥ (1/sg(r))^{1/3+ϵ}, it follows that

|sg(re^{iθ})| < |sg(r)| − |sg(r)|^{1/3−ϵ}.

Next suppose that η(1−r) ≤ |θ| ≤ β(1−r). Hayman proves that |g(re^{iθ})/g(r)| is bounded above by a constant which is strictly less than 1 and so |g(re^{iθ})| ≤ g(r) − ϵg(r).

For β(1 − r) < |θ| ≤ π/m, apply the previous paragraph and (9).

Proof (of Theorem 7): To prevent complexity of argument from obscuring the underlying ideas, we give a proof without multisection of f; that is, we assume g(x) = f(x). The proof can be adapted for multisection by following the proof of Theorem 5.

As can be seen from the proof of Theorem 5, it suffices to establish • some estimates of r^{k}f^{(k)}(r) for k = 1, 2,

• Lemma 2 for dealing with angles outside Θ, and

• Equation (19) for dealing with angles in Θ. Using (10), one easily has that r^{k}f^{(k)}(r) = O(ν^{k}f(r)), which is o(f(r)^{1+ϵ}) since we are given ν = o(f(r)^{ϵ}) for all ϵ > 0.

Lemma 2 is easily established using (11).

We now prove (19). Let F = e^{f}, let H(r, θ) = f(r) + iθa_{F} (r) − θ^{2}B_{F} (r)/2, and let t be an integer to be specified later. By (10), we have

f(re^{iθ}) = ∑_{|k|<t} a_{ν+k}r^{ν+k}e^{iθ(ν+k)} + O(a_{ν}r^{ν} ∑_{k≥t} ρ^{k})

= ∑_{|k|<t} a_{ν+k}r^{ν+k}(1 + iθ(ν + k) − θ^{2}(ν + k)^{2}/2 + O(θ^{3}(ν + k)^{3})) + O(f(r)ρ^{t})

= H(r, θ) + ∑_{|k|≥t} O(f(r)ρ^{k})(1 + |θ|(ν + k) + θ^{2}(ν + k)^{2})

+ O(a_{ν}r^{ν}θ^{3} ∑_{k}(ν + k)^{3}ρ^{k}) + O(f(r)ρ^{t})

= H(r, θ) + ∑_{j=0}^{2} O(f(r)θ^{j}(ν + t)^{j}ρ^{t}) + O(f(r)θ^{3}ν^{3}) + O(f(r)ρ^{t})
= H(r, θ) + O(f(r)ρ^{t}) + O(f(r)θ^{3}(ν + t)^{3}ρ^{t}) + O(f(r)θ^{3}ν^{3}).

Using the assumption that ν = o(f(r)^{ϵ}) for all ϵ > 0 and setting t = log(f(r))/ϵ| log ρ|,

(19) follows.

References

1. E. A. Bender and J. R. Goldman, Enumerative uses of generating functions, Indiana Univ. Math. J. 20 (1971) 753–765.

2. E. A. Bender and L. B. Richmond, A generalisation of Canfield’s formula, J. Combin. Theory Ser. A 23 (1986) 50–60.

3. M. Drmota, A bivariate asymptotic expansion of coefficients of powers of generating functions, Europ. J. Combinat. 15 (1994) 139–152.

4. P. Flajolet and R. Sedgewick, The average case analysis of algorithms: Saddle point asymptotics, INRIA Rpt. No. 2376 (1994).

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

6. Z. Gao and L. B. Richmond, Central and local limit theorems applied to asymptotic enumeration IV: multivariate generating functions, J. Comput. and Appl. Math. 41 (1992) 177–186.

7. D. Gardy, Some results on the asymptotic behaviour of coefficients of large powers of functions, Discrete Math. 139 (1995) 189–217. See also the review by A. Meir (MR 96f:41038).

8. I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, J. Wiley and Sons, New York (1983).

9. L. H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Statist. 38 (1967) 410–414.

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

11. V. Lifschitz and B. Pittel, The number of increasing subsequences of a random permutation, J. Combin. Theory Ser. A 31 (1981) 1–20.

12. A. M. Odlyzko, Asymptotic enumeration methods. In R. L. Graham, M. Grötschel, and L. Lovász (eds.), Handbook of Combinatorics, Vol. II, Elsevier, Amsterdam (1995) 1063–1229.

13. S. J. Press Applied Multivariate Analysis, Holt, Rinehart and Winston, New York (1972).