On a Sequence Arising in Algebraic Geometry

I. P. Goulden^{1}

Department of Combinatorics and Optimization

University of Waterloo Waterloo, Ontario N2L 3G1

Canada

ipgoulde@uwaterloo.ca

S. Litsyn^{2}

Department of Electrical Engineering Systems Tel Aviv University 69978 Ramat Aviv

Israel

litsyn@eng.tau.ac.il

V. Shevelev^{3} Department of Mathematics

Ben Gurion University of the Negev

Beer Sheva Israel

email

Abstract

We derive recurrence relations for the sequence of Maclaurin coefficients of the function χ = χ(t) satisfying (1 + χ) ln(1 + χ) = 2χ − t.

1Supported by a Discovery Grant from NSERC 2Partly supported by ISF Grant 533-03 3Supported by a grant from the Gil’adi Foundation of the Israeli Ministry of Absorption

1 Introduction

Consider the function χ = χ(t) satisfying

(1 + χ) ln(1 + χ) = 2χ − t  (1)

The sequence of coefficients in the Maclaurin expansion of χ plays an important role in algebraic geometry. Namely, the n-th coefficient is equal to the dimension of the cohomology ring of the moduli space of n-pointed stable curves of genus 0. These coefficients are also related to WDVV equations of physics. Exact definitions can be found in [4, 6, 7, 8] and references therein.

It follows from (1) that

χ′ := \frac{dχ}{dt} = \frac{1 + χ}{1 + t − χ},  (2)

and χ has the critical point t = e − 2. Using this, Manin [7, Chap.4, p.194] provides for the coefficients in the Maclaurin expansion of χ,

χ(t) = t + ∑_{n=2}^{∞} m_{n} \frac{t^{n}}{n!},  (3)

the following expression:

m_{n} ∼ \frac{1}{\sqrt{n}} (\frac{n}{e^{2} − 2e})^{n− \frac{1}{2}} .  (4)

Exact computation of the defined numbers is a challenging problem. Indeed, taking into account that

2χ − (1 + χ) ln(1 + χ) = χ + ∑_{n=2}^{∞} \frac{(−1)^{n−1}}{(n − 1)n}χ^{n},

and differentiating n times the identity t = t(χ(t)), we deduce from the Bruno formula [9, p.36, (45a)] that

m_{n} = ∑ \frac{n!(−1)^{j}(j − 2)!}{j_{1}! ⋯ j_{n−1}!} (\frac{m_{1}}{1!} )^{j_{1}} (\frac{m_{2}}{2!} )^{j_{2}} ⋯ (\frac{m_{n}}{(n − 1)!})^{j_{n−1}} , n ≥ 2,  (5)

where m_{1} = 1, j = j_{1} +j_{2} +⋯+j_{n−1}, and the sum is over all non-negative integral solutions to j_{1} + 2j_{2} + ⋯ + (n − 1)j_{n−1} = n. This allows recurrent computation of the numbers m_{n}. Indeed, by (5),

m_{2} = 0!m_{1}^{2} = 1
m_{3} = −1!m_{1}^{3} + 0!(3m_{1}m_{2}) = 2
m_{4} = 2!m_{1}^{4} − 1!(6m_{1}^{2}m_{2}) + 0!(3m_{2}^{2} + 4m_{1}m_{3}) = 7
⋮

However, when n increases, (5) becomes intractable due to the fast growth of the number of partitions of n.

Koganov [5] used the Bürmann-Lagrange inversion formula and generalizations of the Stirling numbers of the second kind [2], to deduce an efficient 3-dimensional scheme for computation of m_{n}’s. Here the Stirling numbers of the second kind of first and second order (S_{1}(n, k) and S_{2}(n, k)) are defined by the two-dimensional recurrences:

S_{1}(n + 1, k) = kS_{1}(n, k) + S_{1}(n, k − 1),
n ≥ k ≥ 1, S_{1}(n, 0) = δ_{0,n}, S_{1}(n, 1) = 1,
S_{2}(n + 1, k) = kS_{2}(n, k) + nS_{2}(n − 1, k − 1),
n ≥ k ≥ 1, S_{2}(n, 0) = δ_{1,n}, S_{2}(n, 1) = 1.

Then, [5],

m_{n} = 1 + (n − 1)! ∑_{k=1}^{⌊ \frac{n−1}{2} ⌋} n(n + 1) ⋯ (n + k − 1)·

∑_{q=0}^{n−1} ∑_{ℓ=0}^{min(k,q)} \frac{S_{1}(q + 1, ℓ + 1)}{q!}(−2)^{k−ℓ} \frac{S_{2}(n − 1 − q − (k − ℓ), k − ℓ)}{(n − 1 − q − (k − ℓ))!}.

This made possible [5] computing the first 10 numbers m_{n}.

In what follows we present a simple computational method for m_{n} based on a quadratic recurrence.

Theorem 1.1 The numbers m_{n} satisfy

m_{n} = ∑_{i=1}^{n−1} \binom{n − 1}{i}m_{i}m_{n−i} − (n − 2)m_{n−1}, n ≥ 2,  (6)

with the initial condition m_{1} = 1.

Proof Multiplying both sides of (2) by 1 + t − χ and rearranging, we obtain

χ′ = χχ′ + χ − tχ′ + 1.

Applying (3) to this equation, we get

∑_{n=1}^{∞} m_{n} \frac{t^{n−1}}{(n − 1)!} = ∑_{i=1}^{∞} m_{i} \frac{t^{i}}{i!} ∑_{j=1}^{∞} m_{j} \frac{t^{j−1}}{(j − 1)!}

+ ∑_{n=1}^{∞} m_{n} \frac{t^{n}}{n!} − ∑_{n=1}^{∞} m_{n} \frac{t^{n}}{(n − 1)!} + 1.

Equating the coefficients of t^{n−1}/(n − 1)! in this equation we accomplish the proof. □

2 A generalization

A natural generalization of the numbers m_{n} is related to configuration spaces [3] and was introduced in [7, §4.3]. For an integer k, k ≥ 1, consider the function χ_{k} = χ_{k}(t) defined by

k(1 + χ_{k}) ln(1 + χ_{k}) = (k + 1)χ_{k} − t,  (7)

for some fixed k. The previously considered χ thus coincides with χ_{1}. Evidently,

\frac{d}{dt}χ_{k} = \frac{1 + χ_{k}(t)}{1 + t − kχ_{k}(t)},  (8)

and expanding at t = 0 we get ,

χ_{k}(t) = t + ∑_{n=2}^{∞} m_{n}(k)\frac{t!}{n!}.  (9)

In particular, m_{1}(k) = 1. Using (8) analogously to the previous section we have the following generalization of Theorem 1.1.

Theorem 2.1 The numbers m_{n}(k) are polynomials of degree (n − 1) in k, with integer coefficients defined by the recursion

m_{n}(k) = k ∑_{i=1}^{n−1} \binom{n − 1}{i}m_{i}(k)m_{n−i}(k) − (n − 2)m_{n−1}(k), n ≥ 2,  (10)

with initial condition m_{1}(k) = 1. □

2.1 Coefficients of m_{n}(k)

Set

m_{n}(k) = μ_{1}(n)k^{n−1} + μ_{2}(n)k^{n−2} + ⋯ + μ_{n−1}(n)k + μ_{n}(n).  (11)

Computation of the coefficients μ_{n}(n), μ_{n−1}(n), μ_{n−2}(n), … is enabled by the following theorem.

Theorem 2.2 For n ≥ 2 and ℓ = 1, …, n, the following recurrence holds:

μ_{ℓ}(n) = ∑_{j=1}^{ℓ} ∑_{i=1}^{n−1} \binom{n − 1}{i}μ_{j}(i)μ_{ℓ+1−j}(n − i) − (n − 2)μ_{ℓ−1}(n − 1).  (12)

Proof The relation (12) is obtained by equating coefficients of k^{n−ℓ} in equation (10). □

Using (12) for ℓ = n, n − 1, … we calculate recursively

μ_{n}(n) =  δ_{n,1}  n ≥ 1,
μ_{n−1}(n) =  (−1)^{n}(n − 2)!  n ≥ 2,
μ_{n−2}(n) =  (−1)^{n−1}(n − 2)! (n − 2 + 2 ∑_{i=1}^{n−2} \frac{1}{i})  n ≥ 3,
μ_{n−3}(n) =  (−1)^{n}(n − 2)!·
· (\frac{1}{2}(n − 3)(n + 4) + (2n − 7) ∑_{i=2}^{n−2} \frac{1}{i} + 6 ∑_{i=2}^{n−2} \frac{1}{i} ∑_{j=1}^{i−1} \frac{1}{j}) n ≥ 4,
⋮

Let us now describe a recurrence for computation of the initial coefficients μ_{1}(n), μ_{2}(n), . . .. Set

M_{ℓ}(x) = ∑_{n=1}^{∞} μ_{ℓ}(n)\frac{x^{n}}{n!} .  (13)

Theorem 2.3 Let M_{n} ≡ M_{n}(\frac{1}{2}(1 − t^{2})), t ≥ 0. Then for n ≥ 2 the following recursion holds:

\frac{d}{dt}(tM_{n}) = ∑_{i=2}^{n−1} (\frac{d}{dt}M_{i}) M_{n+1−i} − tM_{n−1} − \frac{1}{2}(1 − t^{2})\frac{d}{dt}M_{n−1},  (14)

with initial conditions

M_{1} = 1 − t,  M_{n}|_{t=1} = 0.  (15)

Proof Multiply on both sides of (12) by x^{n−1}/(n − 1)!, and sum over n ≥ 1, to obtain the following system of equations for M_{ℓ}(x):

M′_{1}(x) = M_{1}(x)M′_{1}(x) + 1, M_{1}(0) = 0,  (16)

M′_{ℓ}(x) = ∑_{i=2}^{ℓ−1} M′_{i}(x)M_{ℓ−i+1}(x) + M_{ℓ−1}(x) − xM′_{ℓ−1}(x), M_{ℓ}(0) = 0, ℓ ≥ 2.  (17)

From (16) we find

M_{1}(x) = \frac{1}{2}M_{1}^{2}(x) + x,

and

M_{1}(x) = 1 − \sqrt{1 − 2x} = 1 − t  (18)

with t = (1 − 2x)^{\frac{1}{2}} . Finally, changing variables in (17) from x to t, and using

M′_{1}(x) = t^{−1},  x = \frac{1}{2}(1 − t^{2}),  \frac{d}{dx} = \frac{dt}{dx} \frac{d}{dt} = −t^{−1} \frac{d}{dt},

we obtain (after multiplication by −1), for n ≥ 2, the formula (14). □

Notice that from Theorem 2.3 it follows by induction that for n ≥ 2, M_{n} is a polynomial in t and t^{−1} of the form:

M_{n} = ∑_{i=−(2n−3)}^{n} a_{i}(n)t^{i}.  (19)

Thus Theorem 2.3 recursively yields

M_{1} = −t + 1,
M_{2} = \frac{1}{6}t^{2} − \frac{1}{2}t + \frac{1}{2} − \frac{1}{6}t^{−1},
M_{3} = \frac{1}{72}t^{3} − \frac{1}{8}t + \frac{2}{9} − \frac{1}{8}t^{−1} + \frac{1}{72}t^{−3},
M_{4} = \frac{1}{270}t^{4} − \frac{1}{144}t^{3} − \frac{1}{72}t + \frac{1}{18} − \frac{1}{20}t^{−1} + \frac{1}{72}t^{−3} − \frac{1}{432}t^{−5},
M_{5} = \frac{23}{17280}t^{5} − \frac{1}{270}t^{4} + \frac{1}{576}t^{3} + \frac{1}{405}t^{2} − \frac{5}{1152}t + \frac{1}{90} − \frac{59}{4320}t^{−1}

+\frac{43}{5760}t^{−3} − \frac{5}{1728}t^{−5} + \frac{5}{10368}t^{−7},

⋮

Setting (−1)!! = 1, this easily implies

μ_{1}(n) = (2n − 3)!!, n ≥ 1,
μ_{2}(n) = −\frac{n − 2}{3}(2n − 3)!!, n ≥ 2,
μ_{3}(n) = \frac{(n − 1)(n − 2)(n − 3)}{3^{2}}(2n − 5)!!, n ≥ 2,
μ_{4}(n) = −\frac{(n − 3)(n − 4)(5(n − 1)^{2} + 1)}{3^{4} · 5}(2n − 5)!!, n ≥ 3,
μ_{5}(n) = \frac{(n − 3)(n − 4)(n − 5)(5(n − 1)^{3} + 4n − 1)}{2 · 3^{5} · 5}(2n − 7)!!, n ≥ 3.
⋮

Finally, we will state a conjecture we have not been able to verify. Conjecture 1 The expressions for M_{n} do not contain monomials corresponding to the integral negative degrees of (1 − 2x).

This conjecture is confirmed by our calculations for n ≤ 5.

2.2 Yet another property of m_{n}(k)

In this section we consider another combinatorial property of the polynomials m_{n}(k). Theorem 2.4

m_{n}(−1) = (1 − n)^{n−1}  (20)

Proof Substitute k = −1 into (8), to obtain

χ′_{−1} = −χ_{−1}χ′_{−1} + χ_{−1} − tχ′_{−1} + 1.  (21)

Now let

f(t) = ∑_{n=1}^{∞}(1 − n)^{n−1} \frac{t^{n}}{n!},

and note that, from Lagrange’s Theorem as stated in [1, §1.2] we obtain

f(t) = −\frac{t}{T} − 1,

where T = −te^{T}. Differentiating the functional equation for T with respect to t, we obtain

\frac{dT}{dt} = \frac{−e^{T}}{1 + te^{T}} = \frac{T}{t(1 − T)},

so that

\frac{df}{dt} = −\frac{T − tT′}{T^{2}} = \frac{1}{1 − T} ,

and it is now routine to check that f is a solution to (21). We conclude from the initial condition f(0) = 0 that χ_{−1}(t) coincides with f(t). □

3 Numerical Calculation

The derived result allows extending sequence A074059 of Sloane’s on-line Encyclopedia of Integer Sequences which previously contained only 5 terms. We give here the first 19 terms of the sequence:

m = {1, 1, 2, 7, 34, 213, 1630, 14747, 153946, 1821473,
24087590, 352080111, 5636451794, 98081813581,
1843315388078, 37209072076483, 802906142007946,
18443166021077145, 449326835001457846, …}

The first 10 polynomials m_{n}(k) for n = 1, …, 10, are given in the following table:

n m_{n}(k)
1 1
2 k
3 3k^{2} − k
4 15k^{3} − 10k^{2} + 2k
5 105k^{4} − 105k^{3} + 40k^{2} − 6k
6 945k^{5} − 1260k^{4} + 700k^{3} − 196k^{2} + 24k
7 10395k^{6} − 17325k^{5} + 12600k^{4} − 5068k^{3} + 1148k^{2} − 120k
8 135135k^{7} − 270270k^{6} + 242550k^{5} − 126280k^{4} + 40740k^{3}−

−7848k^{2} + 720k

9 2027025k^{8} − 4729725k^{7} + 5045040k^{6} − 3213210k^{5}+

+1332100k^{4} − 363660k^{3} + 61416k^{2} − 5040k

10 34459425k^{9} − 91891800k^{8} + 113513400k^{7} − 85345260k^{6}+

+43022980k^{5} − 15020720k^{4} + 3584856k^{3} − 541728k^{2} + 40320k

Acknowledgement

The third author is grateful to L. M. Koganov for introducing the problem.

References

[1] I. P. Goulden, and D. M. Jackson, Combinatorial Enumeration, Wiley, 1983 (Dover reprint, 2004).

[2] L. Comtet, Analyse Combinatoire, vol. II, Presse Universitaire, Paris, 1970.

[3] W. Fulton, and R. MacPherson, A compactification of configuration spaces, Ann. of Math. 139 (1994), 183–225.

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

[5] L. M. Koganov, Inversion of a power series and a result of S. K. Lando, in Proc. VIth Int. Conf. on Discr. Models in Control Systems Theory, Moscow, MSU, 2004, pp. 170–172.

[6] M. Kontsevich, and Yu. Manin, Quantum cohomology of a product (with Appendix by R. Kaufmann), Inv. Math. 124 (1996), 313–339.

[7] Yu. I. Manin, Frobenius Manifolds, Quantum Cohomology, and Moduli Spaces, AMS Colloquium Publications, 47, American Mathematical Society, Providence, Rhode Island, 1999.

[8] M. A. Readdy, The pre-WDVV ring of physics and its topology, preprint, 2002. Available

at http://www.ms.uky.edu/r̃eaddy/Papers/pre WDVV.pdf.

[9] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1967.

2000 Mathematics Subject Classification: Primary 11Y55. Keywords: cohomology rings of the moduli space, exponential generating functions, recurrences.

(Concerned with sequence \underline{A074059}.)

Received July 15 2005; revised version received October 12 2005. Published in Journal of Integer Sequences, October 12 2005.

Return to Journal of Integer Sequences home page.