Three Proofs and a Generalization of the Goulden-Litsyn-Shevelev Conjecture

on a Sequence Arising in Algebraic Geometry

Brian Drake and Ira M. Gessel^{1} Department of Mathematics

Brandeis University Waltham, MA 02454

USA

bdrake@brandeis.edu
gessel@brandeis.edu

Guoce Xin Center for Combinatorics

LPMC Nankai University Tianjin, 300071

P. R. China

gxin@nankai.edu.cn

Abstract

We prove and generalize a conjecture of Goulden, Litsyn, and Shevelev that certain Laurent polynomials related to the solution of a functional equation have only odd negative powers.

1 Introduction

Consider the functional equation

k(1 + χ) log(1 + χ) = (k + 1)χ − t.  (1)

1Partially supported by NSF Grant DMS-0200596.

It is easily seen that (1) has a unique solution χ = χ(t, k) as a formal power series in t, and that the coefficient of t^{n} in χ(t, k) is a polynomial in k of degree n − 1:

\begin{matrix}χ(t, k) = t + k \frac{t^{2}}{2!} + (3k^{2} − k)\frac{t^{3}}{3!} + (15k^{3} − 10k^{2} + 2k)\frac{t^{4}}{4!} \\ +(105k^{4} − 105k^{3} + 40k^{2} − 6k)\frac{t^{5}}{5!} + ⋯ \end{matrix}  (2)

Here the coefficients are sequence A075856 in the Online Encyclopedia of Integer Sequences [8].

If we set k = 1 then the coefficients of t^{n}/n! are the Betti numbers of the moduli space of n-pointed stable curves of genus 0, as shown by Keel [6]. These coefficients give sequence A074059 in [8]:

χ(t, 1) = t + \frac{t^{2}}{2!} + 2\frac{t^{3}}{3!} + 7\frac{t^{4}}{4!} + 34\frac{t^{5}}{5!} + ⋯  (3)

For an arbitrary positive integer k, there is an interpretation of χ(t, k) in terms of configuration spaces given by Manin [7, p. 197]. See also Goulden, Litsyn, and Shevelev [5] and the references given there. The series expansion of χ has also been studied from a combinatorial perspective. See Dumont and Ramamonjisoa [3, Proposition 6], where χ is shown to count functional digraphs by improper edges, and Zeng [11, Corollary 11], where χ is shown to count certain trees by improper edges. Some related bijections have been studied by Chen and Guo [1].

Following Goulden, Litsyn, and Shevelev [5], let us define μ_{l}(n) to be the coefficient of k^{n−l}t^{n}/n! in χ(t, k). The expansion (2) suggests that μ_{1}(n) = 1 · 3 ⋯ (2n − 3), and thus that

∑_{n=1}^{∞} μ_{1}(n)\frac{t^{n}}{n!} = 1 − \sqrt{1 − 2t}.

Goulden et al. proved more generally that for each l, ∑_{n=0}^{∞} μ_{l}(n)t^{n}/n! is a Laurent polynomial M_{l}(u) in u = \sqrt{1 − 2t}.

The first few polynomials M_{l}(u), given by Goulden et al. [5], are reproduced below:

M_{1}(u) = 1 − u,
M_{2}(u) = −\frac{1}{6}u^{−1} + \frac{1}{2} − \frac{1}{2}u + \frac{1}{6}u^{2},
M_{3}(u) = \frac{1}{72}u^{−3} − \frac{1}{8}u^{−1} + \frac{2}{9} − \frac{1}{8}u + \frac{1}{72}u^{3},
M_{4}(u) = −\frac{1}{432}u^{−5} + \frac{1}{72}u^{−3} − \frac{1}{20}u^{−1} + \frac{1}{18} − \frac{1}{72}u − \frac{1}{144}u^{3} + \frac{1}{270}u^{4},
M_{5}(u) = \frac{5}{10368}u^{−7} − \frac{5}{1728}u^{−5} + \frac{43}{5760}u^{−3} − \frac{59}{4320}u^{−1}

+ \frac{1}{90} − \frac{5}{1152}u + \frac{1}{405}u^{2} + \frac{1}{576}u^{3} − \frac{1}{270}u^{4} + \frac{23}{17280}u^{5}.

In this paper we give three proofs of the following conjecture of Goulden et al. [5, Conjecture 1]:

Theorem 1. The negative powers of u in M_{l}(u) are all odd.

Our first proof uses a change of variables to express the generating function in y for the Laurent polynomials M_{n}(u) in terms of the power series in y (with coefficients that are Laurent polynomials in u)

S = e^{−y/2}yu\sqrt{1 + \frac{2y}{u^{2}} T} ,

where T is a power series in y only. It is easily seen that any odd power of S contains only odd (but possibly negative) powers of u, while any even power of S contains no negative powers of u. This change of variables is related to an expansion of the Lambert W function around its branch point at −e^{−1} (though our proof uses only formal power series).

Our second proof uses properties of formal Laurent series, and shows that the Goulden-Litsyn-Shevelev property holds much more generally for solutions of the functional equation

H = t + kΛ(H)  (4)

where Λ(z) is an arbitrary power series of the form λ_{2}z^{2} + λ_{3}z^{3} + ⋯ with λ_{2} ≠ 0; the Goulden-Litsyn-Shevelev conjecture corresponds to the case Λ(z) = (1 + z) log(1 + z) − z.

In our third proof, we consider the same generalization as in the second proof, but we apply Lagrange inversion to obtain an explicit formula from which it is clear that there are no negative even powers of u.

2 First Proof of Theorem 1

When χ is expanded as a power series in t, the coefficient of t^{n} is a polynomial in k of degree n − 1. To reverse the coefficients of these polynomials, we introduce a new variable y and set ξ = ξ(t, y) = χ(yt, y^{−1}), so that ∑_{n=0}^{∞} μ_{l}(n)t^{n}/n! is the coefficient of y^{l} in ξ. As a power series in t,

ξ(t, y) = yt + y \frac{t^{2}}{2!} + (3y − y^{2})\frac{t^{3}}{3!} + (15y − 10y^{2} + 2y^{3})\frac{t^{4}}{4!}

+ (105y − 105y^{2} + 40y^{3} − 6y^{4})\frac{t^{5}}{5!} + ⋯

and ξ satisfies the functional equation

(1 + ξ) log(1 + ξ) = (1 + y)ξ − ty^{2}.  (5)

As we shall see in the second proof, equation (5) has two solutions as power series in t and y, but ξ is the unique solution in which the constant term in t is zero.

We can expand ξ as a power series in y, and as shown by Goulden et al. [5], in this expansion the coefficient of y^{l} is a Laurent polynomial in u = \sqrt{1 − 2t}.

Replacing t with \frac{1}{2}(1 − u^{2}) in (5) gives

(1 + ξ) log(1 + ξ) = (1 + y)ξ − \frac{1}{2}(1 − u^{2})y^{2}.  (6)

We will express ξ in terms of an auxiliary power series S = S(u, y) satisfying

1 + y + \frac{1}{2}(1 − u^{2})y^{2} = e^{y} (1 − S^{2}/2)  (7)

in which the sign of S is chosen so that S = yu + · · ·. Solving (7) for S gives

S = e^{−y/2}yu\sqrt{1 + \frac{2y}{u^{2}} T} ,

where T is the power series in y given by

T = \frac{e^{y} − 1 − y − y^{2}/2}{y^{3}}.

It is clear that S is a power series in y with coefficients that are Laurent polynomials in u. Our proof of Theorem 1 relies on the following lemma.

Lemma 1. For every nonnegative integer n, S(u, y)^{n} contains no even negative powers of u.

Proof. If n = 2j is even, then

S^{2j} = e^{−jy}y^{2j}u^{2j} (1 + \frac{2y}{u^{2}} T )^{j} ,

which is u^{2j} times a polynomial in u^{−1} of degree 2j, so no negative powers of u appear. If n = 2j + 1 is odd, then

S^{2j+1} = e^{−jy−y/2}y^{2j+1}u^{2j+1} (1 + \frac{2y}{u^{2}} T )^{j+1/2}

= e^{−jy−y/2}y^{2j+1}u^{2j+1} ∑_{m≥0} \binom{j + \frac{1}{2}}{m}\frac{2^{m}y^{m}}{u^{2m}} T^{m}.

The sum does not terminate, so negative powers of u appear. However, we have an odd power of u times a Laurent polynomial in u^{2}, so only odd powers of u occur.

Now we want to show that 1 + ξ is e^{y} times a power series in S. Then Theorem 1 will follow from Lemma 1.

Let 1 + ξ = e^{y}e^{−G} so that G = y − log(1 + ξ) = yu + · · ·. Making these substitutions in equation (6) and simplifying, we get

e^{−G}(1 + G) = 1 − \frac{S^{2}}{2} ,

which yields

S = \sqrt{2 − 2e^{−G}(1 + G)} = G − G^{2}/3 + ⋯  (8)

Then (8) can be inverted to express G as a power series in S, so 1 + ξ is e^{y} times a power series in S. This completes the first proof of Theorem 1.

Remark. What led us to these substitutions? We used Maple to solve equation (5), which gave

ξ = exp(W (−(1 + y + ty^{2})e^{−1−y}) + 1 + y) − 1.  (9)

Here W is the Lambert W function, which satisfies W (z)e^{−W (z)} = z. (See, e.g., Corliss et al. [2] for more information about this function.) Equation (9) suggests that if we set 1+ξ = e^{y+H} then H may be simpler than ξ. (We take G = −H to make the initial coefficient of G positive.) Since W (z) has a branch point of order 2 at z = −e^{−1}, W (−e^{−1} + z) can be expanded as a power series in \sqrt{z}. Replacing z with 2S^{2}e^{−1} gives a power series with rational coefficients:

W (−(1 − 2S^{2})e^{−1}) = −1 + 2S − \frac{4}{3}S^{2} + \frac{11}{9}S^{3} − \frac{172}{135}S^{4} + · · · .

To apply this expansion to ξ we need to find S with

−(1 − 2S^{2})e^{−1} = −(1 + y + ty^{2})e^{−1−y}.

This equation is equivalent to (7) with t = \frac{1}{2}(1 − u^{2}).

3 Second Proof of Theorem 1

In this section we give a different proof of a generalization of Theorem 1. Throughout this section, Φ(z) = 1 + ϕ_{1}z + ϕ_{2}z^{2} + ⋯ is a power series in z with constant term 1 in which the coefficients ϕ_{1}, ϕ_{2}, … are indeterminates, and R is the ring of polynomials in the ϕ_{i}, u, and u^{−1}, where u is another indeterminate.

Lemma 2. The equation

F^{2}Φ(F) − 2yF + (1 − u^{2})y^{2} = 0  (10)

has two power series solutions F = f_{1}y + f_{2}y^{2} + ⋯ with no constant term, given by F = Z(u, y) and F = Z(−u, y), where

Z(u, y) = (1 − u)y + \frac{(1 − u)^{3}}{2u} ϕ_{1}y^{2} + (\frac{(1 − u)^{5}(1 + 5u)}{8u^{3}}ϕ_{1}^{2} + \frac{(1 − u)^{4}}{2u} ϕ_{2}) y^{3}

+ (\frac{(1 − u)^{7}(1 + 7u + 16u^{2})}{16u^{5}}ϕ_{1}^{3} + \frac{(1 − u)^{6}(1 + 6u)}{4u^{3}}ϕ_{1}ϕ_{2} + \frac{(1 − u)^{5}}{2u} ϕ_{3}) y^{4} + · · · . (11)

Moreover, the coefficient of y^{n} in Z(u, y) is a Laurent polynomial in u.

Proof. Let F = f_{1}y + f_{2}y^{2} + · · ·. Substituting in (10) and equating coefficients of y^{2} gives (f_{1} −1)^{2} −u^{2} = 0, so if F satisfies (10) then f_{1} is either 1−u or 1+u. The coefficient of y^{n+1} in F^{2}Φ(F) is a polynomial in ϕ_{1}, …, ϕ_{n−1}, f_{1}, …, f_{n} in which f_{n} occurs only in the term 2f_{1}f_{n}, and the coefficient of y^{n+1} in −2yF is −2f_{n−1}. Thus for n ≥ 2, the coefficient of y^{n+1} in the left side of (10) is a polynomial in ϕ_{1}, …, ϕ_{n−1}, f_{1}, …, f_{n} in which f_{n} occurs only in the term 2(f_{1} − 1)f_{n}. Thus after a choice of either f_{1} = 1 − u or f_{1} = 1 + u, there is a unique solution of (10) in which f_{n} is a polynomial in ϕ_{1}, …, ϕ_{n−1}, f_{1}, …, f_{n−1} divided by f_{1} − 1. Since f_{1} − 1 is either u or −u, it follows that f_{n} is a Laurent polynomial in u. Replacing u by −u switches the two possibilities for f_{1}, so it must also switch the two solutions.

In the next lemma we will work in the ring R((X))[[y]] of formal power series in y with coefficients that are Laurent series in X. These are series of the form

∑_{i=−∞}^{∞} ∑_{j=0}^{∞} a_{ij}X^{i}y^{j}

such that for each j ≥ 0, a_{ij} = 0 for all but finitely many negative values of i. Related applications of formal Laurent series were used by Gessel [4] and Xin [10].

Lemma 3. Let X be an indeterminate and let Z(u, y) be as in Lemma 2. Then in the formal Laurent series ring R((X))[[y]], we have

Φ(X) − \frac{2y}{X} + \frac{(1 − u^{2})y^{2}}{X^{2}} = (1 − \frac{Z(u, y)}{X}) (1 − \frac{Z(−u, y)}{X}) T,  (12)

where T ∈ R[[X, y]] and T has constant term 1 in X and y.

Proof. Let

X^{2}Φ(X) − 2yX + (1 − u^{2})y^{2} = ∑_{j=0}^{∞} c_{j}X^{j}

and let

T_{1} = (1 − \frac{Z(u, y)}{X})^{−1} (Φ(X) − \frac{2y}{X} + \frac{(1 − u^{2})y^{2}}{X^{2}} ) .

In the ring R((X))[[y]] we have the expansion

(1 − \frac{Z(u, y)}{X})^{−1} = ∑_{n=0}^{∞} (\frac{Z(u, y)}{X})^{n} .

Then writing Z for Z(u, y), we have

T_{1} = ∑_{i=0}^{∞} (\frac{Z}{X} )^{i} ∑_{j=0}^{∞} c_{j}X^{j−2},

so the coefficient of X^{−m} in T_{1} is

∑_{j≥max(2−m,0)} c_{j}Z^{m+j−2}.

Thus for m ≥ 2 the coefficient of X^{−m} in T_{1} is 0. A similar argument applied to T = (1 − Z(−u, y)/X)^{−1} T_{1} shows that the coefficient of X^{−m} in T is 0 for m ≥ 1, so T ∈ R[[X, y]].

Finally, setting y = 0 in (12) shows that the constant term in y in T is Φ(X), so the constant term in X and y is 1.

Lemma 4. For any nonnegative integer r, Z(u, y)^{r} contains no even negative powers of u.

Proof. It is sufficient to prove that Z(u, y)^{r} + Z(−u, y)^{r} contains no negative powers of u. Let Ψ be the expression appearing in (12). Since the left side of (12) has constant term 1 and has no negative powers of u, log Ψ is a well-defined element of R((X))[[y]] with no negative powers of u.

The logarithm of the right side of (12) is

− ∑_{r=1}^{∞} \frac{Z(u, y)^{r} + Z(−u, y)^{r}}{rX^{r}} + log T

Since T contains no negative powers of X, for r > 0 the coefficient of X^{−r} in log Ψ is −\frac{1}{r} (Z(u, y)^{r} + Z(−u, y)^{r}), which therefore contains no negative powers of u.

We can now prove our generalization of the Goulden-Litsyn-Shevelev Conjecture.

Theorem 2. Let Λ(z) = λ_{2}z^{2} + λ_{3}z^{3} + ⋯ be a formal power series, where λ_{2} ≠ 0. Then the equation

H = t + kΛ(H)  (13)

has a unique power series solution H(t, k) = t + λ_{2}kt^{2} + (λ_{3}k + 2λ_{2}^{2}k^{2})t^{3} + ⋯, in which the coefficient of t^{n} is a polynomial in k of degree n − 1. Let μ_{l}(n)/n! be the coefficient of k^{n−l}t^{n} in H(t, k). Then ∑_{n=0}^{∞} μ_{l}(n)t^{n}/n! is a Laurent polynomial in \sqrt{1 − 4λ_{2}t} with no even negative powers.^{2}

Proof. We shall prove only the case λ_{2} = \frac{1}{2} of the theorem. The general case then follows, after a short calculation, by replacing k with 2λ_{2}k in (13).

We prove only the last assertion of the theorem; the other assertions are straightforward. Set J(t, y) = H(yt, y^{−1}) so that ∑_{n=0}^{∞} μ_{l}(n)t^{n}/n! is the coefficient of y^{l} in J and set Φ(z) = 2Λ(z)/z^{2} = 1+2λ_{3}z+. . .. Then (13) becomes J = yt+ \frac{1}{2}y^{−1}J^{2}Φ(J), which may be rewritten as

J^{2}Φ(J) − 2yJ + 2ty^{2} = 0.  (14)

By Lemma 2, J = Z(\sqrt{1 − 2t}, y) is a solution of (14) with no constant term in t, so it must be the unique such solution, and the conclusion follows from the case m = 1 of Lemma 4.

Remark. The reader may wonder how the two solutions of Lemma 2 became the unique solution of Theorem 2. We have two solutions, Z(\sqrt{1 − 2t}, y) and Z(−\sqrt{1 − 2t}, y) of (14). The coefficient of t^{n} in Z(\sqrt{1 − 2t}, y) is a polynomial in y, but the coefficient of t^{n} in Z(−\sqrt{1 − 2t}, y) is not a polynomial in y, so although Z(−\sqrt{1 − 2t}, y) corresponds to a solution (with nonzero constant term in t) of (14), it does not correspond to a formal power series solution of (13).

Theorem 1 is obtained from Theorem 2 by taking Λ(z) = (1 + z) log(1 + z) − z.

2The n! in the denominator is only for compatibility with the original Goulden-Litsyn-Shevelev conjecture.

Two cases of Theorem 2 with simple combinatorial interpretations are worth mentioning. First take Λ(z) = e^{z} − z − 1. (It is interesting to note that in this case, as in (1), the solution can be expressed in terms of the Lambert W function.) Here

H(t, k) = t + k \frac{t^{2}}{2!} + (k + 3k^{2})\frac{t^{3}}{3!} + (k + 10k^{2} + 15k^{3})\frac{t^{4}}{4!}

+ (k + 25k^{2} + 105k^{3} + 105k^{4})\frac{t^{5}}{5!} + ⋯

The coefficient of k^{i}t^{n}/n! in H(t, k) is the number of rooted trees with i unlabeled internal vertices, each with at least two children, and n labeled leaves. (These are sometimes called phylogenetic trees.) Setting k = 1 gives

H(t, 1) = t + \frac{t^{2}}{2!} + 4\frac{t^{3}}{3!} + 26\frac{t^{4}}{4!} + 236\frac{t^{5}}{5!} + 2752\frac{t^{6}}{6!} + 39208\frac{t^{7}}{7!} + 660032\frac{t^{8}}{8!} · · · .

These coefficients are sequence A000311 in [8].

Another example is Λ(z) = z^{2}/(1 − z), so

H = t + k \frac{H^{2}}{1 − H} .  (15)

Here we can solve for H explictly, obtaining

H = \frac{1 + t − \sqrt{(1 − t)^{2} − 4kt}}{1 + k} = t + ∑_{n=2}^{∞} ∑_{i=1}^{n−1} \frac{1}{i}\binom{n − 2}{i − 1}\binom{n + i − 1}{i − 1}k^{i}t^{n},  (16)

where the formula for the coefficients is easily derived by Lagrange inversion. It is clear from (15) that the coefficient of k^{i}t^{n} in H(t, k) is the number of ordered trees with n leaves and i internal vertices, in which every internal vertex has at least two children. These coefficients are sequence A033282 in [8], which gives many references and some additional combinatorial interpretations, notably in terms of dissections of a polygon.

Using the explicit formula (16) for the solution of (15) we can verify this case of Theorem 2 directly. In fact, a stronger statement holds here: if ρ_{l}(n) is the coefficient of k^{n−l}t^{n} in H(t, k) (here it is appropriate to use ordinary, rather than exponential, generating functions) then ∑_{n=0}^{∞} ρ_{l}(n)t^{n} is a Laurent polynomial in \sqrt{1 − 4t} in which the only even powers of \sqrt{1 − 4t} are (\sqrt{1 − 4t})^{0} and (\sqrt{1 − 4t})^{2}. To see this, we note that it follows from (16) that

∑_{l=0}^{∞} y^{l} ∑_{n=0}^{∞} ρ_{l}(n)t^{n} = H(yt, y^{−1}) = y \frac{1 + yt − \sqrt{(1 − yt)^{2} − 4t}}{2(1 + y)} = J(t, y)

Setting u = \sqrt{1 − 4t}, so that t = (1 − u^{2})/4, we have

J((1 − u^{2})/4, y) = y \frac{4 + y(1 − u^{2}) − u\sqrt{16 + 8y(1 − u^{−2}) + y^{2}(u − u^{−1})^{2}}}{8(1 + y)} .

Note that the expression under the square root sign involves only even powers of u, and it is multiplied by u, giving only odd powers of u. Thus the contribution to even powers of u is

y \frac{4 + y(1 − u^{2})}{8(1 + y)} = \frac{y}{2} − \frac{y^{2}(3 + u^{2})}{8(1 + y)} = \frac{y}{2} + ∑_{l=2}^{∞} \frac{1}{8}(−1)^{l−1}(3 + u^{2})y^{l}.

4 Third proof of Theorem 1

In our third proof, we use Lagrange inversion to prove Lemma 4 (from which, as we have seen, Theorem 2 follows easily) by giving an explicit formula for Z(u, y)^{r} that makes it clear that it has no even negative powers of u.

Theorem 3. With Z(u, y) as in Lemma 2, we have for any positive integer r,

Z(u, y)^{r} = y^{r}(1 − u)^{r} + ∑_{n=r+1}^{∞} y^{n}

×  ∑_{m_{1}+2m_{2}+···=n−r}(−1)^{m} \frac{r}{2m + n}\binom{m}{m_{1}, m_{2}, ⋯}P_{m,n}(u)ϕ_{1}^{m_{1}}ϕ_{2}^{m_{2}} ⋯,  (17)

where m = m_{1} + m_{2} + ⋯ and

P_{m,n}(u) = ∑_{i=1−2m}^{n} \binom{2m + n}{2m + i}\binom{m + i/2}{m}(−u)^{i}.  (18)

Proof. Let us set Ψ(z) = z^{2}(ϕ_{1}z + ϕ_{2}z^{2} + ⋯), so that with Φ(z) as defined at the beginning of Section 3 we have z^{2}Φ(z) = z^{2} +Ψ(z). Then (10) may be written (F −y)^{2} = u^{2}y^{2} −Ψ(F). Taking square roots gives

F − y = −uy\sqrt{1 − \frac{Ψ(F)}{u^{2}y^{2}}},  (19)

where the sign of the square root is chosen so as to give the solution in which the coefficient of y is 1−u rather than 1+u. To apply Lagrange inversion, we must make a slight modification in (19). It is not difficult to show, e.g., by equating coefficients in (10), that the coefficient of y^{n} in Z(u, y) is a sum of terms in ϕ_{1}^{m_{1}}ϕ_{2}^{m_{2}} ⋯ ϕ_{n−1}^{m_{n−1}}, where m_{1}+2m_{2}+⋯ (n−1)m_{n−1} = n−1. Thus the variable y in Z(u, y) is redundant; Z(u, y) can be recovered from Z(u, 1) be replacing each ϕ_{i} with y^{i}ϕ_{i} and then multiplying by y. So it is enough to solve F = 1−u\sqrt{1 − u^{−2}Ψ(F)} for F as a power series in ϕ_{1}, ϕ_{2}, …. Finally, to put this equation into a form to which Lagrange inversion, in its usual form, can be applied (see, e.g., Stanley [9, Theorem 5.4.2]) we introduce a new redundant variable x and consider the equation

F = x(1 − u\sqrt{1 − u^{−2}Ψ(F)} ).  (20)

for F in as power series in x. Applying Lagrange inversion, we have for any positive integer r,

[x^{s}]F^{r} = \frac{r}{s}[t^{s−r}](1 − u\sqrt{1 − u^{−2}Ψ(t)})^{s}

= \frac{r}{s}[t^{s−r}] ∑_{j=0}^{s} \binom{s}{j}(−u)^{j}(1 − u^{−2}Ψ(t))^{j/2}

= \frac{r}{s}[t^{s−r}] ∑_{j=0}^{s} \binom{s}{j}(−u)^{j} ∑_{m} \binom{j/2}{m}(−u^{−2})^{m}Ψ(t)^{m}

= \frac{r}{s}[t^{s−r}] ∑_{j=0}^{s} \binom{s}{j} ∑_{m}(−1)^{m}\binom{j/2}{m}(−u)^{j−2m}

× ∑_{m_{1}+m_{2}+···=m} \binom{m}{m_{1}, m_{2}, ⋯}ϕ_{1}^{m_{1}}ϕ_{2}^{m_{2}} ⋯ t^{2m+m_{1}+2m_{2}+···}.

Thus with m = m_{1} + m_{2} + ⋯ and n = r + m_{1} + 2m_{2} + ⋯, setting s = 2m + n gives

F^{r} = ∑_{m_{1},m_{2},...} x^{2m+n} \frac{r}{2m + n}\binom{m}{m_{1}, m_{2}, ⋯}ϕ_{1}^{m_{1}}ϕ_{2}^{m_{2}} ⋯

× (−1)^{m} ∑_{j=0}^{2m+n} \binom{2m + n}{j}\binom{j/2}{m}(−u)^{j−2m}

To obtain (17), we first set x = 1, replace each ϕ_{i} with y^{i}ϕ_{i}, and multiply by y^{r}. The contribution from m_{1} = m_{2} = ⋯ = 0 (which gives m = 0 and n = r) is

y^{r} ∑_{j=0}^{r} \binom{r}{j}(−u)^{j} = y^{r}(1 − u)^{r}.

If m > 0 then \binom{j/2}{m} = 0 for j = 0, so we may start the inner sum on j with j = 1, rather than j = 0. Finally, setting j = i + 2m yields (17).

It follows immediately from Theorem 3 that Z(u, y) has no negative even powers of u, since \binom{m+i/2}{m} is 0 when i is even and negative and i ≥ 1 − 2m.

Remarks. The coefficients of Z(u, y) as displayed in (11) show divisibility by powers of 1 − u, and it is not difficult to prove from (18) that the numerator of P_{m,n}(u) is divisible by (1 − u)^{m+n}.

Theorem 3 can be generalized to the equation (F −y)^{p}+Ψ(F)−u^{p}y^{p} = 0. The coefficients are Laurent polynomials in u in which the coefficient of u^{−ip} is 0 for every positive integer i.

References

[1] W. Y. C. Chen and V. J. W. Guo, Bijections behind the Ramanujan polynomials, Adv. in Appl. Math. 27 (2001), 336–356.

[2] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, On the Lambert W function, Adv. Computational Math. 5 (1996), 329–359.

[3] D. Dumont and A. Ramamonjisoa, Grammaire de Ramanujan et arbres de Cayley, Electronic J. Combinatorics 3 (2) (1996), #R17.

[4] I. M. Gessel, A factorization for formal Laurent series and lattice path enumeration, J. Combin. Theory Ser. A 28 (1980), 321–337.

[5] I. P. Goulden, S. Litsyn, and V. Shevelev, On a sequence arising in algebraic geometry, J. Integer Sequences 8 (2005), Paper 05.4.7.

[6] S. Keel, Intersection theory of moduli space of stable n-pointed curves of genus zero, Trans. Amer. Math. Soc. 330 (1992), 545–574.

[7] Y. Manin, Quantum Cohomology, Frobenius Manifolds and Moduli Spaces, AMS Colloquium Publications, Vol. 47, American Mathematical Society, Providence, RI, 1999.

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/∼njas/sequences/, 1996–2006.

[9] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.

[10] G. Xin, The Ring of Malcev-Neumann Series and the Residue Theorem, Ph.D. thesis, Brandeis University, 2004, arXiv:math.CO/0405133.

[11] J. Zeng, A Ramanujan sequence that refines the Cayley formula for trees, Ramanujan J. 3 (1999), 45–54.

2000 Mathematics Subject Classification: Primary 11B83. Secondary 05A15. Keywords: Laurent polynomial, cohomology rings of moduli spaces, Lagrange inversion.

(Concerned with sequences \underline{A000311}, \underline{A033282}, \underline{A074059}, and \underline{A075856}.)

Received September 17 2006; revised version received April 10 2007. Published in Journal of Integer Sequences, April 10 2007.

Return to Journal of Integer Sequences home page.