A Multivariate Lagrange Inversion Formula for Asymptotic Calculations

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 3, 1998 Accepted: June 30, 1998

Abstract

The determinant that is present in traditional formulations of multivariate Lagrange inversion causes difficulties when one attempts to obtain asymptotic information. We obtain an alternate formulation as a sum of terms, thereby avoiding this difficulty.

1991 AMS Classification Number. Primary: 05A15 Secondary: 05C05, 40E99

1. Introduction

Many researchers have studied the Lagrange inversion formula, obtaining a variety of proofs and extensions. Gessel [4] has collected an extensive set of references. For more recent results see Haiman and Schmitt [6], Goulden and Kulkarni [5], and Section 3.1 of Bergeron, Labelle, and Leroux [3].

Let boldface letters denote vectors and let a vector to a vector power be the product of componentwise exponentiation as in x^{n} = x_{1}^{n_{1}} ⋯ x_{d}^{n_{d}}. Let [x^{n}] h(x) denote the coefficient of x^{n} in h(x). Let ∥a_{i,j}∥ denote the determinant of the d × d matrix with entries a_{i,j}. A traditional formulation of multivariate Lagrange inversion is

Theorem 1. Suppose that g(x), f_{1}(x), ⋯, f_{d}(x) are formal power series in x such that f_{i}(0) ≠ 0 for 1 ≤ i ≤ d. Then the set of equations w_{i} = t_{i}f_{i}(w) for 1 ≤ i ≤ d uniquely determine the w_{i} as formal power series in t and

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

where δ_{i,j} is the Kronecker delta.

If one attempts to use this formula to estimate [t^{n}] g(w(t)) by steepest descent or stationary phase, one finds that the determinant vanishes near the point where the integrand is maximized, and this can lead to difficulties as min(n_{i}) → ∞. We derive an alternate formulation of (1) which avoids this problem. In [2], we apply the result to asymptotic problems.

Let D be a directed graph with vertex set V and edge set E. Let the vectors x and f(x) be indexed by V. Define

\frac{∂f}{∂D} = ∏_{j∈V} \{( ∏_{(i,j)∈E} \frac{∂}{∂x_{i}} )f_{j}(x)\} .

We prove

Theorem 2. Suppose that g(x), f_{1}(x), ⋯, f_{d}(x) are formal power series in x such that f_{i}(0) ≠ 0 for 1 ≤ i ≤ d. Then the set of equations w_{i} = t_{i}f_{i}(w) for 1 ≤ i ≤ d uniquely determine the w_{i} as formal power series in t and

[t^{n}] g(w(t)) = \frac{1}{∏ n_{i}} [x^{n−1}] ∑_{T} \frac{∂(g, f_{1}^{n_{1}}, …, f_{d}^{n_{d}})}{∂T},  (2)

where 1 = (1, …, 1), the sum is over all trees T with V = {0, 1, …, d} and edges directed toward 0, and the vector in ∂/∂T is indexed from 0 to d.

When d = 1, this reduces to the classical formula

[t^{n}] g(w(t)) = \frac{[x^{n−1}] g′(t)f(t)^{n}}{n} .

Derivatives with respect to trees have also appeared in Bass, Connell, and Wright [1].

2. Proof of Theorem 2

Expand the determinant ∥δ_{i,j} − a_{i,j}∥. For each subset S of {1, …, d} and each permutation π on S, select the entries −a_{i,π(i)} for i ∈ S and δ_{i,i} for i ∉ S. The sign of the resulting term will be (−1)^{|S|} times the sign of π. Since (i) the sign of π is −1 to the number of even cycles in π and (ii) |S| has the same parity as the number of odd cycles in π, it follows that

∥δ_{i,j} − a_{i,j}∥ = ∑_{S,π}(−1)^{c(π)} ∏_{i∈S} a_{i,π(i)},  (3)

where c(π) is the number of cycles of π and the sum is over all S and π as described above. (When S = ∅, the product is 1 and c(π) = 0.)

Applying (3) to (1) with h_{0} = g, h_{1} = f_{1}^{n_{1}}, …, h_{d} = f_{d}^{n_{d}} and understanding that S ⊆ {1, …, d}, we obtain

(∏n_{i}) [x^{n}] g(w(t))

= [x^{n}] ∑_{S,π}(−1)^{c(π)} \{ ∏_{{i∉S \atop i≠0}} n_{i} × ∏_{i∉S} h_{i}(x) × ∏_{i∈S} x_{i}n_{i} f_{π(i)}(x)^{n_{i}−1} \frac{∂f_{π(i)}(x)}{∂x_{i}} \}

= [x^{n−1}] ∑_{S,π}(−1)^{c(π)} \{ ∏_{{i∉S \atop i≠0}} \frac{n_{i}}{x_{i}} × ∏_{i∉S} h_{i}(x) × ∏_{i∈S} \frac{∂h_{π(i)}(x)}{∂x_{i}} \}

= [x^{n−1}] ∑_{S,π}(−1)^{c(π)} \{( ∏_{{i∉S \atop i≠0}} \frac{∂}{∂x_{i}} )(∏_{i∉S} h_{i}(x) × ∏_{i∈S} \frac{∂h_{π(i)}(x)}{∂x_{i}})\} ,  (4)

where, in the last line, the ∂/∂x_{i} operators replaced n_{i}/x_{i} because we are extracting the coefficient of x_{i}^{n_{i}−1}.

If we expand a particular S, π term in (4) by distributing the partial derivative operators, we obtain a sum of terms of the form

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

where V = {0, 1, …, d} and E ⊂ V × V. Since each ∂/∂x_{i} appears exactly once per term, all vertices in the directed graph D = (V, E) have outdegree one, except for vertex 0 which has outdegree zero. Thus adding the edge (0, 0) to D gives a functional digraph. The cycles of π are among the cycles of D, and, since the ∂/∂x_{i} for i ∉ S can be applied to any factor, the remaining edges are arbitrary. Hence

( ∏_{{i∉S \atop i≠0}} \frac{∂}{∂x_{i}} )(∏_{i∉S} h_{i}(x) × ∏_{i∈S} \frac{∂h_{π(i)}(x)}{∂x_{i}}) = ∑_{D} \frac{∂h}{∂D} ,

where the sum ranges over all directed graphs D on V = {0, 1, …, d} such that (i) adjoining (0, 0) produces a functional digraph and (ii) the cycles of D include π. Denote condition (ii) by π ⊆ D. We have shown that

(∏n_{i}) [x^{n}] g(w(t)) = [x^{n−1}] ∑_{S,π}(−1)^{c(π)} ∑_{D:π⊆D} \frac{∂h}{∂D}

= [x^{n−1}] ∑_{D} ∑_{π:π⊆D}(−1)^{c(π)} \frac{∂h}{∂D} .

Since ∑_{π⊆D}(−1)^{c(π)} = 0 when D has cyclic points and is 1 otherwise, the sum reduces to a sum over acyclic directed graphs D such that adjoining (0, 0) gives a functional digraph. Since these are precisely the trees with edges directed toward 0, the proof is complete.

References

[1] H. Bass, E. H. Connell, and D. Wright, The Jacobian conjecture: Reduction of degree and formal expansion of the inverse, Bull. Amer. Math. Soc. (N.S.) 7 (1982) 287–330.

[2] E. A. Bender and L. B. Richmond, Asymptotics for multivariate Lagrange inversion, in preparation.

[3] F. Bergeron, G. Labelle, and P. Leroux (trans. by M. Readdy), Combinatorial Species and Tree-Like Structures, Encylopedia of Math. and Its Appl. Vol 67, Cambridge Univ. Press, 1998.

[4] I. M. Gessel, A combinatorial proof of the multivariate Lagrange inversion formula, J. Combin. Theory Ser. A 45 (1987) 178–195.

[5] I. P. Goulden and D. M. Kulkarni, Multivariable Lagrange invers, Gessel-Viennot cancellation and the Matrix Tree Theorem, J. Combin. Theory Ser. A 80 (1997) 295–308.

[6] M. Haiman and W. Schmitt, Incidence algebra antipodes and Lagrange inversion in one and several variables, J. Combin. Theory Ser. A 50 (1989) 172–185.