Multivariate Asymptotics for Products of Large Powers with Applications to Lagrange Inversion

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

                          ebender@ucsd.edu

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

                  lbrichmond@watdragon.uwaterloo.ca

Submitted: March 27, 1998 Revised: January 5, 1999 Accepted: January 12, 1999

Abstract

An asymptotic estimate is given for the coefficients of products of large powers of generating functions. This theorem and another local limit theorem which is useful for conditioning are applied to various combinatorial enumeration problems that involve multivariate Lagrange inversion.

1991 AMS Class. No. Primary: 41A63 Secondary: 05A16, 05C05, 41A60

1. Introduction

If f(0) ≠ 0 has a (possibly formal) power series expansion at 0, the equation w = xf(w) determines the power series w(x). Two forms of the Lagrange inversion formula are

g_{n} = [x^{n}] g(w) = [x^{n}] (g(x)f(x)^{n}{(1 − xf′(x)/f(x)})  (1)
= (1/n)[x^{n}] (xg′(x)f(x)^{n}),  (2)

where [x^{n}] h(x) denotes the coefficient of the monomial x^{n} in the power series h(x). We obtained asymptotics for g_{n} from (2) for some types of formal power series [6]. When f has a nonzero radius of convergence, various authors have studied the asymptotics of [x^{n}] g(w) using three basic approaches:

• Exact Formula. Using (2), obtain an exact formula g_{n}. This is often either a simple expression or a summation with alternating signs. Obtain asymptotics from the exact formula. This has been used only sporadically.

• Singularity Analysis. Determine the nature of the singularities of w by looking at xf(w) − w = 0. They are usually square root branch points due to the vanishing of ∂(xf(w) − w)/∂w. Obtain asymptotics by what is essentially Darboux’s Theorem. For a systematic discussion of this approach, see Sprugnoli and Verri [24].

• Contour Integration. Using the Cauchy Residue Theorem, one can estimate g_{n} from (2). Since f(x)^{n} leads to an integral with a simple dominant term it suffices to use a circle. For a systematic discussion of this approach, see Gardy [13]. One can easily include other variables in (2) by simply thinking of the co-

efficients of f, g, and w as involving the new variables. Furthermore, there are extensions of Lagrange inversion to several functions and other variables can be included in these as well.

Recently Drmota [12] treated a system of functional equations using singularity analysis. His results can be applied to multifunction Lagrange inversion when g(w_{1}, w_{2}, …, w_{d}) = w_{i} for some i. Not all cases of interest have this form, a prime example being map enumeration.

The asymptotics of rooted convex polyhedra by faces and vertices (two equations with no extra variables) were studied by us [7] using singularity analysis and later by Bender and Wormald [11] using an exact formula. Rooted maps on general surfaces were dealt with in a similar manner by us and Canfield [4].

In this paper, we are concerned with the asymptotic behavior of the coefficients of large powers of multivariate generating functions and their application to multivariate Lagrange inversion. In Theorem 2 of [5] we studied coefficients of large powers of a single multivariate function using a contour integration approach. In Theorem 2.1 below, we extend this to products of powers of several functions when the exponents tend to infinity in such a way that their ratios are bounded. When there is only one power, Theorem 2.1 is essentially contained in Theorem 2 of [5], but we believe the conditions here are more easily verified than those in [5]. From a probabilistic viewpoint, our concern is with local limit theorems (estimates of coefficients) rather than central limit theorems (estimates for averages of coefficients). One could certainly obtain a central limit theorem extending Theorem 1 of [5]; however, more general central limit theorems have been obtained by Hwang [17] in the case of two variables. Hwang also studies the rate of convergence (which we do not) and points out that the central limit theorem we would derive would have a convergence rate of O(n^{−1/2}).

In the next section we state and prove Theorem 2.1, our theorem for products of powers. In Section 3 we explain how the theorem applies to Lagrange inversion of a single function and discuss the problem of conditioning on some of the indices. This is useful when one wishes to study combinatorial objects conditioned on things such as “size” or number of “components.” Section 4 illustrates applies these ideas to specific enumeration problems. Since neither conditioning nor Lagrange inversion applications were discussed in [5], the material in Sections 3 and 4 is new even though Theorem 2.1 follows from Theorem 2 of [5] in this case. In Section 5, we recall Lagrange inversion formulas for several functions and show how the product of powers theorem can be applied to these formulas. We also prove a local limit theorem that is needed to continue the discussion of conditioning. Section 6 contains examples of specific applications. Although Theorem 2.1 leads to Langrange inversion asymptotics for many functions g; maps present a difficulty which we can resolve only in the single variable situation. This is explained in Section 6. In the final section, we indicate some research problems suggested by the limitations of our approach.

We thank Donatella Merlini and Renzo Sprugnoli for helpful conversations.

2. A Limit Theorem for Products of Powers

Let ZZ denote the integers. For a set V of vectors, let A(V) be the additive abelian group generated by V. Bold face letters denote vectors, x^{n} = x_{1}^{n_{1}}x_{2}^{n_{2}} ⋯, |x| denotes

the vector whose components are |x_{i}|, and ∥x∥ denotes the length of x. As already noted [x^{n}] h(x) denotes the coefficient of x^{n} in the power series h(x).

Let m(f(z)) and B(f(z)) be the vector and matrix given by

m(f(z))_{i} = \frac{∂(log f)}{∂(log z_{i})} and B(f(z))_{i,j} = \frac{∂^{2}(log f)}{∂(log z_{i}) ∂(log z_{j})}.

In all cases, the logarithms are real for real positive z. (This is possible since our functions are positive reals for such z.) Note that

m(f^{n}) = ∑n_{i}m(f_{i}) and B(f^{n}) = ∑n_{i}B(f_{i}).  (3)

Theorem 2.1. Let u denote an l-dimensional vector over the complex numbers, let R be a compact subset of (0, ∞)^{l} with nonempty interior, and let C be the set of complex vectors u with |u| ∈ R. Suppose f_{j}(u) (1 ≤ j ≤ d) and h(u) are such that (a) h and the f_{j} are analytic in C and strictly positive in R;

(b) in R, the B(f_{j}) are positive semidefinite and ∑_{j=1}^{d} B(f_{j}) is nonsingular;

(c) in C, |f_{j}(u)| ≤ f_{j}(|u|) with equality for all j only in R. Fix δ > 0 and let n = ∑ n_{i}. Then we have

[u^{k}] (h(u)f(u)^{n}) = \frac{h(r)f(r)^{n}\{exp(−tB^{−1}t′/2) + o(1)\}}{\sqrt{det(2πB)} r^{k}} as n → ∞ (4)

uniformly for n ∈ [nδ, n/δ]^{d} and r ∈ R, where i = m(f(r)^{n}), B = B(f(r)^{n}), t = k − i, and t′ denotes transpose.

If, for all i, f_{i}(u) = ∑ a_{i}(k)u^{k} where a_{i}(k) ≥ 0 for all k and

Λ(f) = A{k − j | a_{i}(k)a_{i}(j) ≠ 0 for some i} = ZZ^{l},  (5)

then conditions (b) and (c) are satisfied. Frequently a_{i}(0) > 0 for all i, in which case (5) becomes A{k | a_{i}(k) > 0 for some i} = ZZ^{l}.

Proof: Note that B(f^{1}) = ∑ B(f_{j}). Since

B(f^{n}) = nδB(f^{1}) + ∑(n_{i} − δn)B(f_{i}),

n ∈ [nδ, n/δ]^{d}, and the B(f_{i}) are positive semidefinite, it follows that

tB(f^{n})t′ ≥ nδtB(f^{1})t′.

Since the domain of r is compact and B(f^{1}) is positive definite, it follows that B(f^{n})/n is positive definite in a uniform sense; that is, there is a constant C such that tB(f(r)^{n})t′ ≥ nCtt′ for all r ∈ R, all n ∈ [nδ, n/δ]^{d}, and all t.

The proof of (4) follows that of Theorem 2 of [5] almost exactly:

Expand the logarithm of h(z)f(z)^{n} in a Taylor series about r, keeping quadratic terms and a third-order error estimate. Use the Cauchy Residue Theorem with the contours |z_{i}| = r_{i} to estimate the desired coefficient, with (b), (c), and the uniform positive definiteness of B(f^{n})/n ensuring that

|\frac{h(z)f(z)^{n}}{h(r)f(r)^{n}} | = O(exp(−Cθ^{2}n))

uniformly for some C > 0 and θ = max(| arg z_{j}|). See [5] for details.

We now prove the claims concerning (5). Since f_{j} has a power series with nonnegative coefficients:

(i) The first part of (c) holds.

(ii) By Rényi’s number 2 on p.341 of [23], the first part of (b) holds. (iii) f^{1} has a power series with nonnegative coefficients a(k) and

Λ(f^{1}) = A{k − j | a(k)a(j) ≠ 0} = Λ(f)

Since Λ(f) = ZZ^{l}, it follows from (iii) that |f^{1}(u)| = f^{1}(|u|) if and only if u = |u| and so the proof of (c) is complete. The second half of (b) follows from Lemma 6 in [10], with the matrix T in in that paper being the 1 × 1 matrix f^{1} and A_{i,j}^{(s)} = A_{1,1}^{(1)} = Λ(f^{1}).

For Theorem 2.1 to give more than an asymptotic upper bound, the exponential in (4) must not be o(1). In other words, we must have |t| = O(n^{1/2}). Thus the domain of useful k is asymptotically the same as the domain of i. The latter depends on the problem and becomes evident only by calculation; however, we can describe the typical situation. Let Z(n) be the set of j such that [u^{j}] (h(u)f(u)^{n}) = 0. It usually suffices to require that i be at least ϵn from Z(n), where ϵ > 0 is an arbitrary constant. In particular, all components of i will be at least ϵn.

Theorem 2.1 can be strengthened in at least two ways:

(a) The function h can depend on n so long as its partials through second order are uniformly o(n).

(b) It may happen that the lattice Λ(f) in (5) is a proper sublattice of ZZ^{l} rather than all of ZZ^{l}. A theorem still exists, but it requires multisection as discussed in [10].

We have omitted these from the theorem because they are relatively rare and add complications.

3. Lagrange Inversion of One Function

How does Theorem 2.1 apply to Lagrange inversion of a single function? Since (1) and (2) deal with formal power series over a commutative ring of characteristic zero, we are free to include extra variables y in the coefficients of g, f and w. Thus, if

w(x, y) = xf(w(x, y), y) with f(0, y) ≠ 0,

we have [x^{n}y^{j}] g(w(x, y), y) = [y^{j}] g_{n} where g_{n} as in (1). Apply Theorem 2.1 with

d = 1, n = (n), f = (f), u = (x, y), k = (n, j),

and h the remaining factors in (1) or (2) after f^{n} is removed. We start the indexing of k, i, and t at zero so that k_{s} = j_{s} for s > 0. For greatest accuracy in estimating the coefficient of u^{k}, one would normally set t = 0, that is, i = k. The equation for i is then

n = n\frac{r_{0}}{f(r_{0}, r)} \frac{∂f(r_{0}, r)}{∂r_{0}} and j_{s} = n\frac{r_{s}}{f(r_{0}, r)} \frac{∂f(r_{0}, r)}{∂r_{s}} for s > 0.

Regarding the first of these as an equation in n, it has a nontrivial solution if and only if

1 − \frac{r_{0}}{f(r_{0}, r)} \frac{∂f(r_{0}, r)}{∂r_{0}} = 0;  (6)

that is, the last factor in (1) vanishes. Hence h fails to satisfy the h > 0 condition in Theorem 2.1 and so we must use (2):

[x^{n}y^{j}] g(w, y) = [x^{n}y^{j}] (x\frac{∂g(x, y)}{∂x}f(x, y)^{n}) .

Conditioning. In addition to providing asymptotics, (4) provides a local limit theorem for j as n → ∞. One obtains a normal distribution by setting r = (r_{0}, 1), choosing r_{0} so that d log(f(r_{0}, 1)/d log r_{0} = 1, and conditioning on the zeroth component of i being k_{0} = n. To condition, one drops the zeroth component of t and the corresponding row and column of B^{−1}. The latter corresponds to replacing the l × l “covariance” matrix B with the inverse of the lower (l − 1) × (l − 1) block of B^{−1}, say C. One can compute C directly from the block matrix formula found on pp.25–26 of [22]:

[ \begin{matrix}B_{1,1} & B_{1,2} \\ B′_{1,2} & B_{2,2} \end{matrix} ]^{−1}= [ \begin{matrix}∗ & ∗ \\ ∗ & C^{−1} \end{matrix} ] , where C = B_{2,2} − B′_{1,2}(B_{1,1})^{−1}B_{1,2}. (7)

In this case B_{1,1} is 1 × 1.

One can condition on a set of variables that includes n. In this case, we set r_{i} = 1 if we are not conditioning on j_{i}. The remaining components of the equation (n, j) = m(r), including the zeroth, are used to solve for r_{0} and the remaining r_{i}. Again the indices of the variables being conditioned on are dropped from t and B^{−1}. Equation (7) still applies, but B_{1,1} is no longer 1 × 1 since it is indexed by all the variables on which we are conditioning. Since the asymptotics obtained from (4) is uniform, so are the asymptotics for limiting distributions, provided (r_{0}, r) ∈ R and all components of j lie in [nδ, n/δ]. Of course (r_{0}, r) varies as n → ∞ unless the conditioned components grow at a rate proportional to n.

It is possible to condition on a set of variables that does not contain n.

This is more complex. Rather than discuss it here, we treat the general case in the context of multiple Lagrange inversion in Section 5.

Summing over variables, which is roughly the complement of conditioning, is also discussed in Section 5.

4. Examples of Inversion of One Function

We now turn to examples of single function inversion.

Example 4.1. (Noncrossing Partitions) A noncrossing partition of a set of integers is a set partition such that there are no integers a_{1} < b_{1} < a_{2} < b_{2} with a_{i} in one block and b_{i} in another block. Kreweras [18] showed that the number of noncrossing partitions with s_{m} blocks of size m is

a(n, s) = \frac{(n)_{k−1}}{s_{1}! s_{2}! ⋯}, where k = ∑ s_{m} and n = ∑ ms_{m}.

Asymptotic results can be obtained by summing this formula over appropriate indices. Alternatively, one can study the ordinary generating function A(x, z) for noncrossing partitions with z_{m} keeping track of s_{m} and x keeping track of n (the size of the set). By the argument leading to (6.2) of Beissinger [3],

A(x, z) = 1 + ∑_{m}(xA(x, z))^{m}z_{m}.

With w(x, z) = xA(x, z), we have

w(x, z) = xf(w, z) where f(w, z) = 1 + ∑_{m} z_{m}w^{m}.

By specializing z_{m} to 0, 1, and a finite set of indeterminates we can count various noncrossing partitions. For example,

z_{1} = y_{1}, z_{m} = y_{2} for m ∈ M ⊆ {2, 3, …}, and z_{m} = 0 otherwise,

counts noncrossing partitions whose blocks are singletons or have sizes in M, keeping track of the number of each type. To verify (5), fix m_{0} ∈ M and note that

A({(1, 1, 0), (m, 0, 1) : m ∈ M})
= A({(1, 1, 0), (m − m′, 0, 0), (m_{0}, 0, 1) : m, m′ ∈ M})
= A({(1, 1, 0), (g, 0, 0), (m_{0}, 0, 1)}),

where g = gcd{m − m′ : m, m′ ∈ M}. Hence (5) holds if and only if g = 1. Thus

f(x, y) = 1 + y_{1}x + y_{2}S_{0}, where S_{i} = S_{i}(x) = ∑_{m∈M} m^{i}x^{m},

and so

(n, k_{1}, k_{2}) = m = (n/f)(y_{1}x + y_{2}S_{1}, y_{1}x, y_{2}S_{0}).

Since we want the zeroth component of m to be n, f = y_{1}x + y_{2}S_{1} and so

y_{2}S_{1} = 1 + y_{2}S_{0} at (x, y_{1}, y_{2}) = r.

After some calculations,

B = \frac{n}{f^{2}} [ \begin{matrix}fy_{2}(S_{2} − S_{1}) & 0 & f \\ 0 & y_{1}x(f − y_{1}x) & −y_{1}xy_{2}S_{0} \\ f & −y_{1}xy_{2}S_{0} & y_{2}S_{0}(1 + y_{1}x) \end{matrix} ] at (x, y_{1}, y_{2}) = r.

These equations can be used in the theorem to obtain asymptotics.

With k_{1} the number of singleton blocks and k_{2} the number of other blocks, we can get a local limit theorem for the distribution of (k_{1}, k_{2}) as n → ∞ when noncrossing partitions of \underline{n} are selected at random. To do this, we set r_{1} = r_{2} = 1 and use (7) to obtain the covariance matrix. It follows that the joint distribution of (k_{1} − nμ_{1}) /\sqrt{n} and (k_{2} − nμ_{2}) /\sqrt{n} is asymptotically normal with covariance matrix C where

S_{i} = S_{i}(r_{0}), S_{1} = 1 + S_{0} determines r_{0}, f = r_{0} + S_{1} = 1 + r_{0} + S_{0},
μ_{1} = r_{0}/f, μ_{2} = S_{0}/f,

and

C = [ \begin{matrix}r_{0}S_{1}/f^{2} & −r_{0}S_{0}/f^{2} \\ −r_{0}S_{0}/f^{2} & (1 + r_{0})S_{0}/f^{2} \end{matrix} ] − [ \begin{matrix}0 \\ 1/f \end{matrix} ] \frac{f}{S_{2} − S_{1}} [ 0 1/f ] .

For example, when M is the set of primes, r_{0} = 0.5580260,

μ_{1} = 0.263674, μ_{2} = 0.263815, and C = [ \begin{matrix}0.194150 & −0.069561 \\ −0.069561 & 0.067667 \end{matrix} ] .

Example 4.2. (Powers of an Inversion) Suppose w(x, y) = xf(w, y). How do the coefficients of [x^{n}] w^{k} behave as k → ∞ with n? Meir and Moon [19] studied the case when y was absent because w(x) = xf(w(x)) is associated with a variety of labeled and unlabeled tree enumerations and w^{k} counts forests with k components. The introduction of y allows us to keep track of additional information (such as vertex degrees), but we can still follow Meir and Moon’s approach. Furthermore, when y is absent, we obtain their result. Since g(w) = w^{k}, Meir and Moon observed that Lagrange inversion gives

[x^{n}] w(x, y)^{k} = (1/n)[x^{n}] (xkx^{k−1}f(x, y)^{n}) = (k/n)[x^{n−k}] f(x, y)^{n}.

One can now apply Theorem 2.1 to obtain asymptotics. The zeroth component of m gives the equation

\frac{n − k}{n} f(x, y) = x\frac{∂f(x, y)}{∂x}.  (8)

It follows that \frac{n−k}{n} must be bounded away from 0 and so the value of k must be restricted to 1 ≤ k ≤ αn where α < 1. If (8) has a solution (r_{0}, r) when k = 0 and if the power series for f has nonnegative coefficients, letting r_{0} decrease toward 0 produces a solution for the same r and all larger values of k. In particular, when r = 1, one obtains a local limit theorem for the distribution of the variables counted by y, with means and covariance matrix proportional to n and their values depending on the value of k/n.

Example 4.3. (Plane Trees by Vertex Degree) A planted plane tree is a rooted plane tree in which the root has degree 1. If x counts nonroot vertices and y_{k} counts nonroot vertices of degree k, then the generating function satisfies

w(x, y) = x ∑_{k≥0} z_{k+1}w^{k}.  (9)

Goulden and Jackson [15, Sec.2.7.7] obtain the formula

[x^{n}y^{k}] w(x, y) = \frac{(n − 1)!}{∏ k_{i}!},

provided ∑ k_{i} = n and ∑ ik_{i} = 2n − 1, and is zero otherwise. where the last factor is a multinomial coefficient If one wishes to keep track of only a few degrees, say those in a finite set D, summing this formula could be impractical. In Exercise 2.7.2 of [15], Goulden and Jackson obtain formulas when D is a singleton or a pair of degree. The former is an alternating sum and the latter an alternating double sum.

Specializing (9) by setting y_{k} = 1 for k ∉ D, we can apply the theorem with h = x and

f = ∑_{k∉D} x^{k−1} + ∑_{k∈D} y_{k}x^{k−1} = \frac{1}{1 − x} + ∑_{k∈D}(y_{k} − 1)x^{k−1}  (10)

Since f has positive coefficients, we now verify (5). If k is the jth element in D, let e_{k} be the unit vector whose jth component is 1 and let i ∉ D be fixed. Since gcd{i − j | i, j ∉ D} = 1 when D is finite,

A{k − j | a(k)a(j) ≠ 0} = A{(i − j, 0), (k − j, e_{k}) | i, j ∉ D, k ∈ D}
= A{(1, 0), (k − j, e_{k}) | j ∉ D, k ∈ D}
= ZZ^{1+|D|}.

One easily computes that the component of m associated with x is

m_{0} = \frac{n}{f}(\frac{x}{(1 − x)^{2}} + ∑_{k∈D}(k − 1)(y_{k} − 1)x^{k−1}),  (11)

and that associated with y_{k} is

m_{k} = ny_{k}x^{k−1}/f.  (12)

After some calculation, and using the fact that m_{0} = n for Lagrange inversion, we find that

\begin{aligned}b_{0,0} & = \frac{n}{f}(\frac{x(1 + x)}{(1 − x)^{3}} + ∑_{k∈D}(k − 1)^{2}(y_{k} − 1)x^{k−1}) − 1, \\ b_{0,k} & = (k − 2)m_{k}/f, \\ b_{k,k} & = m_{k}(1 − m_{k}/n), \\ b_{k,j} & = −m_{k}m_{j}/n, k ≠ j. \end{aligned}

We can use the theorem to obtain either asymptotics or a local limit theorem.

To obtain asymptotics, we want m to give the number of vertices of each type so that then t = 0 in (4), which will give the greatest accuracy. The values of r_{0} and r_{k} are given by setting x = r_{0} and y_{k} = r_{k} and then combining (10), (11), and (12): With μ_{k} = m_{k}/n, the fraction of vertices of degree k, we have

\frac{1}{1 − r_{0}} + ∑_{k∈D}(μ_{k} − r_{0}^{k−1}) = \frac{r_{0}}{(1 − r_{0})^{2}} + ∑_{k∈D}(k − 1)(μ_{k} − r_{0}^{k−1}),

which can be solved numerically for r_{0} once D and the fractions μ_{k} are given. Then r_{k} = μ_{k}/r_{0}^{k−1}. Using these values in the formulas for b_{i,j} and then in (4) with t = 0 gives the asymptotics.

The local limit theorem is easily obtained since we simply set y_{k} = r_{k} = 1 for k ∈ D and x = r_{0}. This leads to

r_{0} = 1/2, f = 2, μ_{k} = 2^{−k}, b_{0,0} = 2n.

Using (7), we obtain

\frac{c_{k,k}}{n} = μ_{k} − μ_{k}^{2} (1 + \frac{(k − 2)^{2}}{2} ) and \frac{c_{k,j}}{n} = −μ_{k} μ_{j} (1 + \frac{(k − 2)(j − 2)}{2}) .

We could equally well have looked at out-degrees in simply generated families of trees. In that case, (10) becomes

f = ∑_{k≥1} f_{k}x^{k} + ∑_{k∈D} f_{k}(y_{k} − 1)x^{k},

and the analysis proceeds as above. In particular, when D is a singleton set, we recover Theorem 1(i) of Meir and Moon [20].

Example 4.4. (3-Connected Rooted Maps) The asymptotics for 3-connected rooted maps by number of edges were determined by Tutte [25]. We use Mullin and Schellenberg’s parameterization [21]. They found that the generating function with x^{m}y^{n} counting 3-connected rooted planar maps with m + 1 vertices and n + 1 faces is

p(x, y) = (\frac{1}{1 + x} + \frac{1}{1 + y} − 1) xy − \frac{rs}{(r + s + 1)^{3}} ,

where r = x(s + 1)^{2} and s = y(r + 1)^{2}. Setting x = y and r = s, we obtain the generating function by number of edges since E = V + F − 2 by Euler’s relation. For asymptotic purposes, we can ignore the first part of p(x, y) and look at

[x^{n}] (\frac{−r^{2}}{(1 + 2r)^{3}} ) where r = x(1 + r)^{2}.

We have

\begin{aligned}[x^{n}] (\frac{−r^{2}}{(1 + 2r)^{3}} ) & = n^{−1}[x^{n}] (x (\frac{−x^{2}}{(1 + 2x)^{3}} )′ (x + 1)^{2n}) \\ & = n^{−1}[x^{n}] (\frac{2x^{2}(x − 1)}{(1 + 2x)^{4}}(x + 1)^{2n}) . \end{aligned}  (13)

The fraction in the last line is h(x). Since condition (6) becomes 1 − \frac{2r_{0}}{1+r_{0}} = 0, h(r_{0}) = 0 and Theorem 2.1 fails to apply. Fortunately, we can rewrite the last line of (13) in the form of (1) and then use (2):

n^{−1}[x^{n}] (\frac{2x^{2}(x − 1)}{(1 + 2x)^{4}}(x + 1)^{2n}) = n^{−1}[x^{n}] (\frac{−2x^{2}(x + 1)}{(1 + 2x)^{4}}(x + 1)^{2n} (1 − \frac{2x}{1 + x}))

= n^{−2}[x^{n}] (x (\frac{−2x^{2}(1 + x)}{(1 + 2x)^{4}})′ (x + 1)^{2n})

= n^{−2}[x^{n}] (\frac{2x^{2}(2x^{2} + x − 2)}{(1 + 2x)^{5}}(x + 1)^{2n}) .

Noting that r_{0} = 1 and putting all this in the theorem we find that the number of rooted 3-connected maps with n edges is asymptotic to 2^{2n+1} / 3^{5}\sqrt{nπ} n^{2}.

5. Lagrange Inversion of Several Functions

Suppose we have

w_{i}(x, y) = x_{i}f_{i}(w(x, y), y) for 1 ≤ i ≤ d  (14)

and want [x^{n}y^{j}] g(w, y). The two forms of Lagrange inversion for several equations that parallel (1) and (2), respectively, are [9]

[x^{n}y^{j}] g(w(x, y), y)
= [x^{n}y^{j}] \{g(x, y) f(x, y)^{n} ∥δ_{i,j} − \frac{x_{i}}{f_{j}(x, y)} \frac{∂f_{j}(x, y)}{∂x_{i}} ∥\}  (15)

= \frac{1}{∏ n_{i}} [x^{n}y^{j}] ∑_{T} x^{1} \frac{∂(g, f_{1}^{n_{1}}, …, f_{d}^{n_{d}})}{∂T} ,  (16)

where 1 is the vector of all ones, δ_{i,j} is the Kronecker delta, • ∥D∥ is the determinant of the d × d matrix D,

• the vector (g, f_{1}^{n_{1}}, …, f_{d}^{n_{d}}) has indices 0, …, d,

• T runs over all trees with vertex set indexed on 0, …, d and edges directed toward 0, and

• for a directed graph D whose vertex set V is the indices of h and x

\frac{∂h}{∂D} = ∏_{j∈V} \{( ∏_{(i,j)∈E} \frac{∂}{∂x_{i}} )h_{j}(x)\} ,

where E is the edge set of D.

To apply the theorem, we let u = (x, y), k = i = (n, j), and we let h be what is left in (15) or (16) after removing f^{n}. By Theorem 2.1,

[x^{n}y^{j}] g(w(x, y), y) ∼ \frac{h(r)f(r)^{n}}{\sqrt{det(2πB)} r^{k}} ,  (17)

where B = B(f(r)^{n}) and k = m(f^{n}). The last equation can be written

nL(r) = 0 where L_{i,j}(x) = δ_{i,j} − \frac{x_{j}}{f_{i}} \frac{∂f_{i}}{∂x_{j}} ,  (18)

where δ_{i,j} is the Kronecker delta. Thinking of n as unknown, we see the condition for this set of equations to have a nontrivial solution is precisely that the determinant in (15) vanish, and so h will violate condition (a) in Theorem 2.1. Hence we use (16) rather than (15). This is the multiple inversion case of what happened with (1).

We now turn our attention to conditioning. Since the discussion is somewhat involved, you may wish to read Example 6.1 beforehand.

To discuss conditioning, we first need an appropriate local limit theorem. It will be simpler not to distinguish between the variables x and y. This can be done by supplementing (14) with the additional equations w_{i} = y_{i}, which means f_{i} = 1. In this way, we eliminate references to y and incorporate j in n. Since the new f_{i} = 1, (17) and (18) are still valid and L_{new} = L_{old} ⊕ I, where I is an identity matrix indexed for the added Lagrange equations w_{i} = y_{i}.

Theorem 5.1. Let r be the solution to iL(r) = 0. Under the assumptions of Theorem 2.1, with the extra variables y eliminated as described above, we have

[x^{k}] (h(x)f(x)^{k}) = \frac{h(r)f(r)^{k}\{exp(−tLB^{−1}L′t′/2) + o(1)\}}{\sqrt{det(2πB)} r^{k}}  (19)

uniformly as ∥k∥ → ∞, where L = L(r), B = B(f(r)^{k}), and t = k − i. Since iL = 0, we can replace t by k.

Equation (19) does not give a distribution becausee det(L) = 0 implies that LB^{−1}L′ is singular. It turns out that conditioning leads to a nonsingular matrix.

Proof: Let n = ∥k∥. Let r^{∗} be the solution to kL = 0. Let s and s^{∗} be the the componentwise logarithms of r and r^{∗}, respectively. Let B denote B(f(r)^{k}). Note that B = O(n) and det(B) is of order n^{dim(B)}, where the latter follows from (a) B is positive definite, (b) B(f_{i}) is positive semidefinite, and (c) k_{i}/n is bounded away from 0. It follows that B^{−1} = O(1/n). These results also hold for B(f(r^{∗})^{k}).

For now, we assume that ∥tL∥ ≤ n^{3/5}. By Taylor series with remainder,

kL(r^{∗}) = kL(r) + (s^{∗} − s)B + O (∥s^{∗} − s∥^{2}n) .  (20)

Since kL(r^{∗}) = 0, it follows from the above that

∥s^{∗} − s∥ = O(n^{3/5})B^{−1} = O(n^{−2/5})

and so, from (20),

s^{∗} − s = −kL(r^{∗})B^{−1} + O(n^{−4/5}n)B^{−1}
= −tL(r^{∗})B^{−1} + O(n^{−4/5}) = O(n^{−2/5}).  (21)

Since the components of r are bounded away from 0 and ∞, we also have r^{∗} − r = O(n^{−2/5}). We now consider the expansion of the logarithm of the ratio

\frac{h(r)f(r)^{k}/r^{k}}{\sqrt{det(2πB(f(r)^{k}))}}/ \frac{h(r^{∗})f(r^{∗})^{k}/(r^{∗})^{k}}{\sqrt{det(2πB(f(r^{∗})^{k}))}}  (22)

in a Taylor series about s^{∗}. Note that

h(r^{∗}) = h(r) + O(∥r^{∗} − r∥) = h(r)(1 + O(n^{−2/5})

since h is bounded away from 0. Since

B = B(f(r^{∗})^{k}) + O(n∥r − r^{∗}∥) = B(f(r^{∗})^{k}) + O(n^{3/5}).

and B^{−1} = O(1/n), it follows that

B(f(r)^{k})^{−1}B(f(r^{∗})^{k}) = I + O(B^{−1}n∥r − r^{∗}∥) = I + O(n^{−2/5}).  (23)

Finally, with Δs = s − s^{∗},

log (\frac{f(r)^{k}(r^{∗})^{k}}{f(r^{∗})^{k}r^{k}} ) = −kL(f(r^{∗}))(Δs)′ + \frac{1}{2}ΔsB(f(r^{∗})^{k})(Δs)′ + O (n∥Δs∥^{3})
= \frac{1}{2}ΔsB(f(r^{∗})^{k})(Δs)′ + O(n^{−1/5}),

since kL(r^{∗}) = 0. Combining this with (21),

log (\frac{f(r)^{k}(r^{∗})^{k}}{f(r^{∗})^{k}r^{k}} ) = \frac{1}{2}tL(r)B^{−1}B(f(r^{∗})^{k})B^{−1}L(r)′t′ + O(n^{−1/5}).  (24)

From (23),

B^{−1}B(f(r^{∗})^{k})B^{−1} = B^{−1}(I + O(n^{−2/5})) = B^{−1} + O(n^{−7/5})

and B(f(r^{∗})^{k})^{−1} = B^{−1} +O(n^{−7/5}). Combining the various equations and (4) with i = k and the fact that tL(r) = O(n^{3/5}), we obtain (19).

We now assume that ∥tL∥ ≥ n^{3/5}. In this case, the exponential in (19) is o(1). Thus, it suffices to prove that (22) tends to ∞ with n. The compactness of R and the nonsingularity of B assure us that h(r)/h(r^{∗}) and the ratios of the square roots in (22) are bounded away from 0 and ∞. Thus it suffices to consider the ratio F (s)/F (s^{∗}) where

F (u) = f(x)^{k}/x^{k}, u_{i} = log x_{i}, and x ∈ R.

We may assume that the region R, viewed in s coordinates is convex: Other than the compactness requirement, the main restriction on R was that the various power series converge. If ∑ a_{n} exp(n · s) and ∑ a_{n} exp(n · s^{∗}) converge absolutely, then so does ∑ a_{n} exp(n · (λs + (1 − λ)s^{∗})) because, for series with nonnegative terms,

∑ A_{n}^{λ}B_{n}^{1−λ} ≤ ∑ max(A_{n}, B_{n})^{λ} max(A_{n}, B_{n})^{1−λ}
= ∑ max(A_{n}, B_{n}) ≤ ∑ A_{n} + ∑ B_{n}.

By standard calculus, the gradient and matrix of second derivatives of F are ∇F = kL(x) and B(f(x)^{k}). Since B is positive definite, F is convex and so has just one minimum, which is given by the solution s^{∗} to ∇F (u) = 0. Think of k as fixed and i as variable. (Thus s is also variable.) Using (24) for ∥tL∥ = n^{3/5}, we see that F (s^{∗}) = o(F (s)) uniformly for such values. From the convexity of F, it follows that F (s^{∗}) = o(F (s)) for ∥tL∥ ≥ n^{3/5}.

Conditioning and Summing. Let C be the indices of variables on which we are conditioning and N the remaining indices. One uses the equation iL = 0 to determine r_{j} for j ∈ C and i_{j} for j ∈ N. In addition, one has the equations f_{j}(r)/r_{j} = 1 for j ∈ N. The latter equations guarantee that i_{j} will be chosen to be at the peak of the distribution when j ∈ N. One extracts the diagonal submatrix of LB^{−1}L′ that is indexed by N. If we condition on all the original x, then r_{j} = 1 for j ∈ N (since f_{j} = 1) and the relevant portion of L is the identity matrix so we are just extracting a diagonal submatrix of B^{−1}; all of which is as described in Section 3 for the single Lagrange equation. In particular, (7) applies with B_{1,1} indexed by C and B_{2,2} and C indexed by N.

The theorem can also be used for summing over variables. Suppose we have a formula as in (19) and want to sum over certain components of t. Let the set of indices be S The corresponding i components must be chosen so that we are the peak; that is, f_{j}(r)/r_{j} = 1 for j ∈ S. Partition M = LB^{−1}L′ into a 2 × 2 block matrix where the subscript 1 refers to elements of S. In summing (19), the tail will be negligible because of the convexity discussed in the last paragraph of the theorem’s proof. Thus we are faced with the problem of summing exp(−z/2) over t_{1} where

z = (t_{1}, t_{2}) [ \begin{matrix}M_{1,1} & M_{1,2} \\ M_{2,1} & M_{2,2} \end{matrix} ] (t_{1}, t_{2})′
= (t_{1} + t_{2}T)M_{1,1}(t_{1} + t_{2}T)′ + t_{2}(M_{2,2} − T M_{1,1}T′)t′_{2},

and T satisfies T M_{1,1} = M_{2,1}. (We have used the fact that M is symmetric.) In order to be able to carry out the summation, M_{1,1} must be nonsingular. In that case, we obtain a factor of (det(2πM_{1,1}^{−1}))^{1/2} from the summation and the exponential becomes

exp(−t_{2}(M_{2,2} − T M_{1,1}T′)t′_{2}/2),

which is still singular if M is singular. If M is not singular, the above matrix is the inverse of the lower righthand block of M^{−1}.

(In this case, an alternative proof can be found in Section 3.4 of Press [22].) Conditioning, before or after summing, will normally make the matrix nonsingular.

Before conditioning and/or summing, one may wish to make a linear change of variables. For example, if m_{k} is the number of vertices of type k, one might introduce the coordinate n = ∑ m_{k}, the total number of vertices, and condition on it. After changing coordinates, the rules for selecting r and i differ somewhat, but the underlying principles are the same: If n = mA gives the old coordinates n in terms of the new coordinates m, then

\frac{f(r)^{n}}{r^{n}} = \frac{f^{∗}(r)^{m}}{(r^{∗})^{m}} ,

where log f^{∗} = (log f)A and log r^{∗} = (log r)A. The earlier rules now apply with f^{∗}(r), r^{∗}, and iA^{−1} in place of f(r), r, and i. (This is illustrated in the next example.)

6. Examples of Inversion of Several Functions

We now turn to examples of inversion of more than one function. Because of the intimate connection between Lagrange inversion and tree enumeration, it is not surprising that Lagrange inversion is often ideal for studying tree enumeration questions. For a single function, this can be seen in the examples of the Section 4. Good [14] may have been the first to point this out for inversion of several functions. In this connection, see also Goulden and Jackson [15]. As the examples in this section illustrate, Lagrange inversion of several functions leads to more complicated calculations than occur for a single function. Thus one should reduce the inversion problem to a single function when possible.

Example 6.1. (Plane Rooted Colored Trees) As usual, the set of colors is finite. We consider situations in which local conditions determine the possible colors of a vertex. Similar methods apply to rooted labeled colored trees (no longer planar). Examples of situations that can be dealt with in this manner are:

• A vertex must have a different color from its children (proper coloring).

• The children of a vertex must have distinct colors.

• A vertex with grandchildren must have the same color as a grandchild. The more complex the conditions and the greater the number of colors, the greater the number of equations that must be inverted, and so the more complicated the calculations.

We begin by considering trees with green and red vertices. Our local condition will be that a nonleaf green vertex must have exactly one red child and two green children, while a nonleaf red vertex must have exactly one child of each color with the left one being red. Associate the subscript 1 with green and 2 with red. Let t_{i} keep track of number of vertices of color i and let w_{i} be the generating function for trees by root color. The conditions translate to

w_{1}(x) = x_{1}f_{1}(w), where f_{1}(w) = 1 + 3w_{1}(x)^{2}w_{2}(x),
w_{2}(x) = x_{2}f_{2}(w), where f_{2}(w) = 1 + w_{1}(x)w_{2}(x).

Lagrange inversion gives us c(k), the number of trees with k_{1} green and k_{2} red vertices:

c(k) = [x^{k}] (w_{1} + w_{2}).

There are 3 directed trees in the sum over T . Their edge sets are

E_{1} = {(1, 0), (2, 1)}, E_{2} = {(2, 0), (1, 2)}, and E_{3} = {(1, 0), (2, 0)}. (25)

Thus

c(k) = (k_{1}k_{2})^{−1}[x^{k}] \{x_{1}x_{2} (\frac{∂(x_{1} + x_{2})}{∂x_{1}} \frac{∂f_{1}(x)^{k_{1}}}{∂x_{2}} f_{2}(x)^{k_{2}}
+\frac{∂(x_{1} + x_{2})}{∂x_{2}} \frac{∂f_{2}(x)^{k_{2}}}{∂x_{1}} f_{1}(x)^{k_{1}} + \frac{∂^{2}(x_{1} + x_{2})}{∂x_{1}∂x_{2}}f_{1}(x)^{k_{1}}f_{2}(x)^{k_{2}})\}

= (k_{1}k_{2})^{−1}[x^{k}] \{x_{1}x_{2} (\frac{3k_{1}x_{1}^{2}}{f_{1}(x)} f_{1}(x)^{k_{1}}f_{2}(x)^{k_{2}} + \frac{k_{2}x_{2}}{f_{2}(x)}f_{1}(x)^{k_{1}}f_{2}(x)^{k_{2}})\} .

We apply Theorem 2.1 with n = (k_{1}, k_{2}) and h = 3x_{1}^{3}x_{2}/f_{1}(x) + x_{1}x_{2}^{2}/f_{2}(x). We set k = i and ν = 0 in (4). The equation i = m(f(r)^{i}) is

\begin{aligned}k_{1} & = \frac{6r_{1}^{2}r_{2}}{1 + 3r_{1}^{2}r_{2}} k_{1} + \frac{r_{1}r_{2}}{1 + r_{1}r_{2}} k_{2} \\ k_{2} & = \frac{3r_{1}^{2}r_{2}}{1 + 3r_{1}^{2}r_{2}} k_{1} + \frac{r_{1}r_{2}}{1 + r_{1}r_{2}} k_{2} \end{aligned}  (26)

and (4) becomes

c(k) ∼ (\frac{3r_{1}^{3}r_{2}}{k_{2}(1 + 3r_{1}^{2}r_{2})} + \frac{r_{1}r_{2}^{2}}{k_{1}(1 + r_{1}r_{2})}) \frac{(1 + 3r_{1}^{2}r_{2})^{k_{1}}(1 + r_{1}r_{2})^{k_{2}}}{\sqrt{det(2πB)} r_{1}^{k_{1}}r_{2}^{k_{2}}} , (27)

where B = k_{1}B(f_{1}) + k_{2}B(f_{2}). To verify (5), note that

Λ(f) = A{(2, 1), (1, 1)} = ZZ^{2}.

It remains to compute r, verify that h > 0, compute B, and, perhaps, simplify (27), details of which we omit. One can check that, with 1 < ρ = k_{1}/k_{2} < 2,

r_{1} = \frac{(ρ − 1)^{2}}{3(2 − ρ)} and r_{2} = \frac{3(2 − ρ)^{2}}{(ρ − 1)^{3}}  (28)

r_{1} and r_{2} are positive and (26) is satisfied. Hence the theorem applies if, for some ϵ > 0, we have 1 + ϵ ≤ k_{1}/k_{2} ≤ 2 − ϵ as ∥k∥ → ∞.

Let n = k_{1} + k_{2}. After some calculations

B(f_{1}) = \frac{3r_{1}^{2}r_{2}}{(1 + 3r_{1}^{2}r_{2})^{2}} [ \begin{matrix}4 & 2 \\ 2 & 1 \end{matrix} ] = \frac{ρ − 1}{ρ^{2}} [ \begin{matrix}4 & 2 \\ 2 & 1 \end{matrix} ]
B(f_{2}) = \frac{r_{1}r_{2}}{(1 + r_{1}r_{2})^{2}} [ \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ] = (2 − ρ)(ρ − 1) [ \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ]
B(f^{n}) = k_{1}B(f_{1}) + k_{2}B(f_{2}) = \frac{nρ}{ρ + 1}B(f_{1}) + \frac{n}{ρ + 1}B(f_{2})

= \frac{n(ρ − 1)}{ρ(ρ + 1)} [ \begin{matrix}4 + 2ρ − ρ^{2} & 2 + 2ρ − ρ^{2} \\ 2 + 2ρ − ρ^{2} & 1 + 2ρ − ρ^{2} \end{matrix} ] .

One can eliminate r from (27) by using (28), and k by using k = n (\frac{ρ}{ρ+1}, \frac{1}{ρ+1}).

We now obtain a local limit theorem for the number of red vertices in trees having a fixed number of vertices.

To do so, we use (19), change coordinates from k to (n, k_{2}), choose i_{1}/i_{2} so that we are at a peak, and condition on n. Since the change of coordinates is given by

(k_{1}, k_{2}) = (n, k_{2})A where A = [ \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} ] ,  (29)

tLB^{−1}L′t′ = u(ALB^{−1}L′A′)u′, where u = (n − i_{1} − i_{2}, k_{2} − i_{2}). To condition on u_{1} = 0, we delete the first row and column of ALB^{−1}L′A′, which leaves a single number, say 1/nσ^{2}. Thus the number of trees satisfies

c(n, k_{2}) = \frac{h(r)(f_{1}/r_{1})^{n}\{exp(−(k_{2} − i_{2})^{2}/2nσ^{2}) + o(1)\}}{\sqrt{det(2πB)}} (\frac{f_{2}r_{1}}{f_{1}r_{2}} )^{k_{2}} .

To be a peak as a function of k_{2}, the last factor must be 1; that is f_{1}/r_{1} = f_{2}/r_{2}. With Maple’s help we found that ρ = 1.73473. Using this in the preceding formula, we obtain

c(n, k_{2}) = \frac{C_{1}C_{2}^{n}\{exp(−(k_{2} − nμ)^{2}/2nσ^{2}) + o(1)\}}{2πn^{2}C_{3}},

where C_{1} = 1.00829, C_{2} = 2.55726, C_{3} = 0.105061, μ = 0.36567, and σ = 0.110205. (The extra factor of n in the denominator is due to h(r).) Of course, since the local limit theorem states that k_{2} is normally distributed with mean nμ and variance nσ^{2}, it does not require the various C_{i} values.

We now turn our attention to the last problem raised at the start of this example, namely, a vertex with grandchildren must have the same color as a grandchild. We want to count trees according to the number of vertices of each color. This problem has a new feature: with each vertex we must keep track of its color and the set of colors of its children, with the empty set arising when a vertex has no children. As a result, we consider generating functions T_{c,S}(x) for trees where c is the root color and S is the set of children’s colors. This leads to functional equations of the form

T_{c,S} = x_{c} f_{c,S}(T),

which are inappropriate for Lagrange inversion. Consider instead

T_{c,S} = x_{c,S} f_{c,S}(T).

We may think of x_{c,S} as keeping track of k_{c,S}, the number of vertices of color c whose children’s colors are S. After applying (19) to obtain asymptotics, we change coordinates to k_{c} = ∑_{T} k_{c,T} and k_{c,S} with S ≠ ∅, then we sum over all values of k_{c,S} (with S ≠ ∅) to obtain a result in terms of just the k_{c}. The change of coordinates is done as in (29). The method for summation is described at the end of Section 5. After changing coordinates, the condition for setting the components of r becomes “f_{c,S}(r)/r_{c,S} must be independent of S.” We omit the details.

Example 6.2. (Plane Trees by Vertex Degree, Continued) Counting planted plane trees by vertex degree was treated in Example 4.3. We now consider a multiple Lagrange equation approach so that one can compare the two approaches.

Let the sets S_{i} be a finite partition of a subset of {1, 2, …} with 1 ∈ S_{1}. (We need 1 to have leaves.)

Let y_{i} keep track of the number of vertices having degree in S_{i}.

To follow the idea of Example 4.3, we introduce one further variable x keeping track of all vertices except the root and write the single equation

T (x, y) = xf(T (x, y), y) where f(w, y) = ∑_{i} y_{i}( ∑_{k∈S_{i}} w^{k−1}),

which is dealt with as follows: The equations

n = \frac{nx∂f(x, y)/∂x}{f(x, y)} and k_{i} = \frac{ny_{i}∂f(x, y)/∂y_{i}}{f(x, y)}  (30)

must be solved for x = r_{0} and y = r if we have values of n and k in mind. If we want to study the distribution of k conditioned on n, we must set r = 1 and solve the first equation from (30),

1 = \frac{r_{0}∂f(r_{0}, 1)/∂r_{0}}{f(r_{0}, 1)}  (31)

for r_{0}. The remaining equations in (30) determine k/n, the value of k that gives the peak of the normal. We can then proceed with conditioning as in the previous example.

If we do not introduce x, it is natural to introduce T_{i}(y), the enumerator for trees where the degree of the root’s son is in S_{i}. We have

T_{i}(y) = y_{i}f_{i}(T (y)), where f_{i}(T) = ∑_{k∈S_{i}} T^{k−1} and T (y) = ∑_{i} T_{i}(y).

This leads to the equations

k_{i} = ∑_{j} k_{j}r_{i}f′_{j}(r)/f_{j}(r), where r = ∑_{j} r_{j}.

Hence r_{i} is proportional to k_{i} and so r_{i} = rk_{i}/n, which is chosen so that

1 = ∑_{j} r_{j}f′_{j}(r)/f_{j}(r).  (32)

If we want to get a distribution by conditioning on ∑ k_{i} = n, then, as in the previous example, we want r_{j}/f_{j}(r) to be independent of j. This together with (32) gives us dim r equations in the same number of unknowns; however, that does not seem to be as easily solved as (31).

Example 6.3. (3-Connected Rooted Maps, Continued) Continuing Example 4.4, we now consider enumeration of 3-connected rooted maps by vertices and faces. As noted in that example, we want

[x^{n}] (\frac{−w_{1}w_{2}}{(1 + w_{1} + w_{2})^{3}} ) where w_{1} = x_{1}(1 + w_{2})^{2} and w_{2} = x_{2}(1 + w_{1})^{2}.

We must sum over 3 trees, namely those in (25). The tree with E_{3} produces a term that is smaller by a factor on the order of n than those for E_{1} and E_{2}. The sum over the trees with E_{1} and E_{2} lead to a term which vanishes when we set x to the r according to Theorem 2.1. Paralleling Example 4.4, we could write this sum S as (S/D) × D, where D is the determinant in (15), and then use the fact that (15) equals (16) to get a more tractable formula. This approach requires that S/D be well behaved as we approach r. In Example 4.4, this was the case since we had cancellation between S and D. In this case there is no such cancellation and, based on Maple calculations, the limit of S/D as we approach r depends on how r is approached.

Consequently, we are unable to proceed.

7. Unsolved Problems

Examples 4.4 and 6.3 raise the issue that the function g(w) can cause problems. We were able to avoid them in the first example but not in the second. If one attempts to enumerate all rooted maps a similar problem arises. There is also a new problem in that case: One can enumerate all maps on general surfaces [1, 4] and the vanishing determinant problem causes difficulty on the projective plane even in the one variable case because of a branch point. Can the approach in this paper be extended to such situations or must one use singularity analysis? If the latter, is there a useful general formulation that will deal with problems of this sort?

Suppose additional variables appear in g but not in h. In particular, suppose h = h(w) and g = g(w, y) and g does not have a singularity at w = r. If g(r, y) has finite radius of convergence and has nice singularities there, then the arguments in [10] may be usable. If g(r, y) is entire, this approach breaks down. For example, if w = xf(w) is the functional equation for the exponential generating function of a regular family of labelled trees, then (1 − w(x))^{−y} is the enumerator for functional digraphs such that removal of cyclic edges results in a forest of trees enumerated by w and y keeps track of the number of cycles. When w(r) < 1, (1 − w(r))^{−y} is a Hayman admissible function [16]. We are not aware of any multivariate singularity analysis that combines algebraic singularities and Hayman-admissibility. We discussed multivariate Hayman admissibility in [8].

We believe it should be possible to extend Drmota’s functional equation results [12] to remove the limitation that g(w) be w_{i} for some i.. Also, one should be able to eliminate the conditioning on n in his Theorem 1, thereby obtaining a result like our Theorem 5.1, probably with his I − F_{y} and F_{y,y} playing a role akin to our L and B. We have not attempted to develop these ideas and currently have no plans to do so.

References

[1] D. Arquès, Une relation fonctionelle nouvelle sur les cartes planaire pointées, J. Combin. Theory Ser. B 39 (1985) 27–424.

[2] D. Arquès, Relations fonctionelles et dénombrement des cartes pointées sur le tore, J. Combin. Theory Ser. B 43 (1987) 253–274.

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

[4] E. A. Bender, E. R. Canfield, and L. B. Richmond, The asymptotic number of rooted maps on a surface II: Enumeration by vertices and faces, J. Combin. Theory Ser. A 63 (1993) 318–329.

[5] E. A. Bender and L. B. Richmond, Central and local limit theorems applied to asymptotic enumeration II: Multivariate generating functions, J. Combin. Theory Ser. A 34 (1983) 255–265.

[6] E. A. Bender and L. B. Richmond, An asymptotic expansion for the coefficients of some formal power series II: Lagrange inversion, Discrete Math. 50 (1984) 135–142.

[7] E. A. Bender and L. B. Richmond, The asymptotic enumeration of rooted convex polyhedra, J. Combin. Theory Ser. B 36 (1984) 276–283.

[8] E. A. Bender and L. B. Richmond, Admissible functions and asymptotics for labeled structures by number of components, Electron. J. Combin. 3 (1996) R34.

[9] E. A. Bender and L. B. Richmond, A multivariate Lagrange inversion formula for asymptotic calculations, Electron. J. Combin. submitted.

[10] E. A. Bender, L. B. Richmond, and S. G. Williamson, Central and local limit theorems applied to asymptotic enumeration III: Matrix recursions, J. Combin. Theory Ser. A 35 (1983) 263–278.

[11] E. A. Bender and N. C. Wormald, The number of rooted convex polyhedra, Canad. Math. Bull. 31 (1988) 99–102.

[12] M. Drmota, Systems of functional equations, Random Structures and Algorithms 10 (1997) 103–124.

[13] D. Gardy, Some results on the asymptotic behaviour of coefficients of large powers of functions, Discrete Math. 139 (1995) 189–217.

[14] I. J. Good, The generalization of Lagrange’s expansion and the enumeration of trees, Proc. Cambridge Phil. Soc. 61 (1965) 499–517.

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

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

[17] H. K. Hwang, ??? quasipowers ??? Europ. J. Combin. 19?? (1998) ???–???.

[18] G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972) 333–350.

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

[20] A. Meir and J. W. Moon, On nodes of given out-degree in random trees, 213– 222 in J. Nešetřil and M. Fiedler (eds.), Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, Elsevier (1992).

[21] R. C. Mullin and P. J. Schellenberg, The enumeration of c-nets via quadrangulations, J. Combin. Theory 3 (1968) 259–276.

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

[23] A. Rényi, Probability Theory, North-Holland, Amsterdam (1970).

[24] R. Sprugnoli and C. M. Verri, Asymptotics for Lagrange inversion, Pure Math. Appl. 5 (1994) 79–104.

[25] W. T. Tutte, A census of planar maps, Canad. J. Math. 15 (1963) 249–271.