<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf On a Sequence Arising in Algebraic Geometry
}
\vskip 1cm
\large
I. P. Goulden\footnote{Supported by a Discovery Grant from NSERC}\\
Department of Combinatorics and Optimization \\
University of Waterloo \\
Waterloo, Ontario  N2L 3G1 \\
Canada\\
\href{mailto:ipgoulde@uwaterloo.ca}{\tt ipgoulde@uwaterloo.ca} \\
\medskip

S. Litsyn\footnote{Partly supported by ISF Grant 533-03} \\
Department of Electrical Engineering Systems \\
Tel Aviv University \\
69978 Ramat Aviv \\
Israel\\
\href{mailto:litsyn@eng.tau.ac.il}{\tt litsyn@eng.tau.ac.il} \\
\medskip

V. Shevelev\footnote{Supported by a grant
from the Gil'adi Foundation of the Israeli Ministry of Absorption} \\
Department of Mathematics \\
Ben Gurion University of the Negev \\
Beer Sheva \\
Israel \\
\href{mailto:email}{\tt email} \\
\end{center}

\begin{abstract}
We derive
recurrence relations for the sequence of Maclaurin
coefficients of the function $\chi=\chi(t)$ satisfying $(1+\chi)
\ln (1+\chi)=2 \chi-t$.
%This allows extension of sequence A074059
%which contained five terms.
%Some generalizations of the sequence
%are discussed.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 


%the new version with Goulden, revised by Goulden - Aug 5, 2005
% final version October 11, 2005, SL

%\documentclass[12pt]{article}
%\usepackage{amsmath,amssymb}

%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newcommand{\proof}{\noindent {\bf Proof}\ \ }
\newcommand{\qed}{\hfill \mbox{$\Box$}}
\date{}

%\begin{document}


\bigskip

\section{Introduction}

Consider the function $\chi=\chi(t)$ satisfying
\begin{equation} \label{eq:1}
(1+\chi) \ln (1+\chi)=2 \chi-t
\end{equation}
The sequence of coefficients in the Maclaurin expansion of $\chi$
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 \cite{keel92,kont96,mani99,read02} and
references therein.

It follows from (\ref{eq:1}) that
\begin{equation} \label{eq:2a}
\chi':=\frac{d \chi}{dt}=\frac{1+\chi}{1+t-\chi},\end{equation}
and $\chi$ has the critical point $t=e-2$. Using this, Manin
\cite[Chap.4, p.194]{mani99} provides for the coefficients in the
Maclaurin expansion of $\chi$,
\begin{equation} \label{eq:2}
\chi(t)=t+\sum_{n=2}^\infty m_n \frac{t^n}{n!},
\end{equation}
the following expression:
\begin{equation} \label{eq:3}
m_n \sim \frac{1}{\sqrt{n}} \left(
\frac{n}{e^2-2e}\right)^{n-\frac{1}{2}}.
\end{equation}
%By (\ref{eq:3}) we have also
%\begin{equation} \label{eq:4}
%\mu_n:=\frac{m_n}{n!} \sim \sqrt{\frac{e^2-2e}{2 \pi}\,\,}
%n^{-\frac{3}{2}} (e-2)^{-n}=0.557448 \cdots n^{-\frac{3}{2}}
%(e-2)^{-n}
%\end{equation}

Exact computation of the defined numbers is a challenging problem.
Indeed, taking into account that
$$2 \chi-(1+\chi) \ln (1+\chi)=\chi+\sum_{n=2}^\infty
\frac{(-1)^{n-1}}{(n-1)n} \chi^n,$$ and differentiating $n$ times
the identity $t=t(\chi(t))$, we deduce from the Bruno formula
\cite[p.36, (45a)]{rior67} that
\begin{equation} \label{eq:4}
m_n=\sum \frac{n! (-1)^{j} (j-2)!}{j_1! \cdots j_{n-1}!}
\left(\frac{m_1}{1!} \right)^{j_1} \left(\frac{m_2}{2!}
\right)^{j_2}  \cdots \left(\frac{m_n}{(n-1)!} \right)^{j_{n-1}},
\quad n\ge 2,
\end{equation}
where $m_1=1$, $j=j_1+j_2+\cdots+j_{n-1}$, and the sum is over all
non-negative integral solutions to $j_1+2j_2+\cdots+(n-1)
j_{n-1}=n$. This allows recurrent computation of the numbers
$m_n$. Indeed, by (\ref{eq:4}),
\begin{eqnarray*}
m_2=0! m_1^2=1\\
m_3=-1! m_1^3+0! (3 m_1 m_2)=2\\
m_4=2! m_1^4-1! (6 m_1^2 m_2)+0! (3 m_2^2+4 m_1 m_3)=7\\
\vdots
\end{eqnarray*}
%and we compute $m_2=1$, $m_3=2$, $m_4=7$, $\ldots$
However, when $n$ increases, (\ref{eq:4}) becomes intractable due
to the fast growth of the number of partitions of $n$.

Koganov \cite{koga04} used the B\"{u}rmann-Lagrange inversion
formula and generalizations of the Stirling numbers of the second
kind \cite{comt70}, 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)=k S_1(n,k)+S_1(n,k-1),$$ $$ n \ge k \ge 1,
S_1(n,0)=\delta_{0,n}, S_1(n,1)=1,$$
$$S_2(n+1,k)=k S_2(n,k)+n S_2(n-1,k-1), $$ $$n \ge k \ge 1,
S_2(n,0)=\delta_{1,n}, S_2(n,1)=1. $$ Then, \cite{koga04},
$$m_n=1+(n-1)! \sum_{k=1}^{\lfloor \frac{n-1}{2} \rfloor}
n (n+1)\cdots (n+k-1) \cdot $$
$$ \sum_{q=0}^{n-1} \sum_{\ell=0}^{\min (k,q)}
\frac{S_1(q+1,\ell+1)}{q!} (-2)^{k-\ell}
\frac{S_2(n-1-q-(k-\ell),k-\ell)}{(n-1-q-(k-\ell))!}.$$ This made
possible \cite{koga04} computing the first 10 numbers $m_n$.

In what follows we present a simple computational method for $m_n$
based on a quadratic recurrence.

\begin{theorem} \label{thm:1}
The numbers $m_n$ satisfy
\begin{equation} \label{eq:6a}
m_n=\sum_{i=1}^{n-1} {n-1 \choose i} m_i m_{n-i}-(n-2) m_{n-1},
\quad n \ge 2,
\end{equation}
with the initial condition $m_1=1$.
\end{theorem}

\proof Multiplying both sides of (\ref{eq:2a}) by $1+t-\chi$ and
rearranging, we obtain
$$\chi'=\chi \chi'+\chi-t \chi'+1.$$
Applying  (\ref{eq:2}) to this equation, we get
$$\sum_{n=1}^\infty m_n \frac{t^{n-1}}{(n-1)!}=\sum_{i=1}^\infty
m_i \frac{t^i}{i!} \, \, \sum_{j=1}^\infty m_j
\frac{t^{j-1}}{(j-1)!}$$
$$+\sum_{n=1}^\infty m_n \frac{t^n}{n!}-\sum_{n=1}^\infty m_n \frac{t^n}{(n-1)!}+1.$$
Equating the coefficients of $t^{n-1}/(n-1)!$ in this equation we
accomplish the proof. \qed
\medskip

\section{A generalization}

A natural generalization of the numbers $m_n$ is related to
configuration spaces \cite{fult94} and was introduced in \cite[\S
4.3]{mani99}. For an integer $k$, $k \ge 1$, consider the function
$\chi_k=\chi_k(t)$ defined by
\begin{equation} \label{eq:12a}
k (1+\chi_k) \ln (1+\chi_k)=(k+1) \chi_k-t , \end{equation} for
some fixed $k$. The previously considered $\chi$ thus coincides
with $\chi_1$. Evidently,
\begin{equation} \label{eq:13a}
\frac{d}{dt} \chi_k=\frac{1+\chi_k(t)}{1+t-k \chi_k(t)}
,\end{equation} and expanding at $t=0$ we get ,
\begin{equation} \label{eq:14a}
\chi_k(t)=t+\sum_{n=2}^\infty m_n(k) \frac{t!}{n!} .
\end{equation}
In particular, $m_1(k)=1$. Using (\ref{eq:13a}) analogously to the
previous section we have the following generalization of Theorem
\ref{thm:1}.

\begin{theorem} \label{thm:2} The numbers $m_n(k)$ are polynomials
of degree $(n-1)$ in $k$, with integer coefficients defined by the
recursion
\begin{equation} \label{eq:15a}
m_n(k)=k\sum_{i=1}^{n-1} {n-1 \choose i} m_i(k) m_{n-i}(k)-(n-2)
m_{n-1}(k), \quad n \ge 2,
\end{equation}
with initial condition $m_1(k)=1$. \qed \end{theorem}

\subsection{Coefficients of $m_n(k)$}

Set
\begin{equation} \label{eq:17a}
m_n(k)=\mu_1(n) k^{n-1}+\mu_2(n) k^{n-2}+\cdots+\mu_{n-1}(n)
k+\mu_n(n).
\end{equation}
Computation of the coefficients $\mu_n(n), \mu_{n-1}(n),
\mu_{n-2}(n),\ldots$ is enabled by the following theorem.

\begin{theorem} \label{thm:3}
For $n\geq 2$ and $\ell =1,\ldots ,n$, the following recurrence
holds:
\begin{equation} \label{eq:b}
\mu_{\ell}(n)=\sum_{j=1}^\ell \sum_{i=1}^{n-1} {n-1 \choose i}
\mu_{j}(i) \mu_{\ell+1-j}(n-i)-(n-2) \mu_{\ell-1}(n-1).
\end{equation}
\end{theorem}

\proof The relation (\ref{eq:b}) is obtained by equating
coefficients of $k^{n-\ell}$ in equation~(\ref{eq:15a}). \qed
\medskip

Using (\ref{eq:b}) for $\ell=n,n-1,\ldots$ we calculate
recursively
\begin{eqnarray*}
\mu_n(n)=&amp; \delta_{n,1} &amp; n \ge 1,\\
\mu_{n-1}(n)=&amp;(-1)^n (n-2)! &amp; n \ge 2,\\
\mu_{n-2}(n)=&amp;(-1)^{n-1} (n-2)! \left(
n-2+2 \sum_{i=1}^{n-2} \frac{1}{i} \right) &amp; n \ge 3,\\
\mu_{n-3}(n)=&amp;(-1)^n (n-2)! \cdot &amp; \\
&amp; \cdot \left(\frac12(n-3)(n+4)+(2n-7) \sum_{i=2}^{n-2}
\frac{1}{i}+6 \sum_{i=2}^{n-2} \frac{1}{i} \sum_{j=1}^{i-1}
\frac{1}{j} \right) &amp; n \ge 4,\\
&amp;\vdots &amp;
\end{eqnarray*}

Let us now describe a recurrence for computation of the initial
coefficients $\mu_1(n), \mu_2(n), \ldots$.   Set
\begin{equation} \label{eq:18a}
M_{\ell}(x)=\sum_{n=1}^\infty \mu_{\ell}(n) \frac{x^n}{n!}.
\end{equation}

\begin{theorem} \label{thm:4}
Let $M_n\equiv M_n(\frac12 (1-t^2)), \qquad t \ge 0$. Then for $n
\ge 2$ the following recursion holds:
\begin{equation} \label{eq:19a}
\frac{d}{dt} (t M_n)=\sum_{i=2}^{n-1} \left( \frac{d}{dt}
M_i\right) M_{n+1-i}-t M_{n-1}-\frac12 (1-t^2) \frac{d}{dt}
M_{n-1},
\end{equation}
with initial conditions
\begin{equation} \label{eq:20a}
M_1=1-t, \qquad M_n|_{t=1}=0.
\end{equation}
\end{theorem}

\proof Multiply on both sides of~(\ref{eq:b}) by $x^{n-1}/(n-1)!$,
and sum over $n\ge 1$, to obtain the following system of equations
for $M_{\ell}(x)$:
\begin{equation} \label{eq:28a}
M'_1(x)=M_1(x) M'_1(x)+1, \quad M_1(0)=0,
\end{equation}
\begin{equation} \label{eq:29a}
M'_{\ell}(x)=\sum_{i=2}^{\ell -1} M'_i(x) M_{\ell -i+1}(x)+M_{\ell
-1}(x) -x M'_{\ell -1}(x), M_{\ell}(0)=0, \ell \ge 2.
\end{equation}
{F}rom (\ref{eq:28a}) we find
$$M_1(x)=\frac12 M_1^2(x)+x,$$
and
\begin{equation} \label{eq:30a}
M_1(x)=1-\sqrt{1-2x}=1-t
\end{equation}
with $t=(1-2x)^{\frac12}$. Finally, changing variables in
(\ref{eq:29a}) from $x$ to $t$, and using
$$M'_1(x)=t^{-1},\qquad x=\frac12 (1-t^2), \qquad\frac{d}{dx}=\frac{dt}{dx} \frac{d}{dt}=
-t^{-1} \frac{d}{dt},$$ we obtain (after multiplication by $-1$),
for $n \ge 2$, the formula (\ref{eq:19a}).  \qed
\medskip

Notice that from Theorem \ref{thm:4} it follows by induction that
for $n \ge 2$, $M_n$ is a polynomial in $t$ and $t^{-1}$ of the
form:
\begin{equation} \label{eq:31a}
M_n=\sum_{i=-(2n-3)}^n a_i(n) t^i .
\end{equation}
Thus Theorem \ref{thm:4} recursively yields
\begin{eqnarray*}
M_1&amp;=&amp;-t+1,\\
M_2&amp;=&amp;\frac16 t^2-\frac12 t+\frac12-\frac16 t^{-1},\\
M_3&amp;=&amp;\frac{1}{72} t^3-\frac18 t+\frac29-\frac18
t^{-1}+\frac{1}{72}
t^{-3},\\
M_4&amp;=&amp;\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&amp;=&amp;\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}\\
&amp;{}&amp;+\frac{43}{5760}t^{-3}-\frac{5}{1728} t^{-5}+\frac{5}{10368}
t^{-7},
\end{eqnarray*}
$$\vdots$$

Setting $(-1)!!=1$, this easily implies
\begin{eqnarray*}
\mu_1(n)&amp;=&amp;(2n-3)!!, \quad n \ge 1,\\
\mu_2(n)&amp;=&amp;-\frac{n-2}3 (2n-3)!!, \quad n \ge 2,\\
\mu_3(n)&amp;=&amp;\frac{(n-1)(n-2)(n-3)}{3^2} (2n-5)!!, \quad n \ge 2,\\
\mu_4(n)&amp;=&amp;-\frac{(n-3)(n-4)(5(n-1)^2+1)}{3^4 \cdot
5} (2n-5)!!, \quad n \ge 3,\\
\mu_5(n)&amp;=&amp;\frac{(n-3)(n-4)(n-5)(5(n-1)^3+4n-1)}{2 \cdot 3^5 \cdot
5} (2n-7)!!, \quad n \ge 3.
\end{eqnarray*}
$$\vdots$$

Finally, we will state a conjecture we have not been able to
verify.

\begin{conjecture}
The expressions for $M_n$ do not contain monomials corresponding
to the integral negative degrees of $(1-2x)$.
\end{conjecture}

This conjecture is confirmed by our calculations for $n \le 5$.

\subsection{Yet another property of $m_n(k)$}

In this section we consider another combinatorial property of the
polynomials $m_n(k)$.

\begin{theorem} \label{thm:5}
\begin{equation} \label{eq:32a}
m_n(-1)=(1-n)^{n-1}
\end{equation}
\end{theorem}

\proof Substitute $k=-1$ into (\ref{eq:13a}), to obtain
\begin{equation} \label{eq:33a}
\chi'_{-1}=-\chi_{-1} \chi'_{-1}+\chi_{-1}-t \chi'_{-1}+1.
\end{equation}
Now let
$$f(t)=\sum_{n=1}^\infty (1-n)^{n-1} \frac{t^n}{n!} ,$$
and note that, from Lagrange's Theorem as stated in \cite[\S
1.2]{goul83} we obtain
$$f(t)=-\frac{t}{T}-1,$$
where $T=-t e^T$. Differentiating the functional equation for $T$
with respect to $t$, we obtain
$$\frac{dT}{dt}=\frac{-e^T}{1+t e^T}=\frac{T}{t(1-T)},$$
so that
$$\frac{df}{dt}=-\frac{T-t T'}{T^2}=\frac{1}{1-T},$$
and it is now routine to check that $f$ is a solution to
(\ref{eq:33a}). We conclude from the initial condition $f(0)=0$
that $\chi_{-1}(t)$ coincides with $f(t)$. \qed

\section{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:
\begin{eqnarray*}
m=&amp;\{1,1,2,7,34,213,1630,14747,153946,1821473,\\
&amp;24087590, 352080111, 5636451794, 98081813581, \\&amp;1843315388078,
37209072076483, 802906142007946,
\\&amp;
18443166021077145, 449326835001457846, \ldots \}
\end{eqnarray*}


 The first 10
polynomials $m_n(k)$ for $n=1,\ldots,10$, are given in the
following table:
$$\begin{array}{cl}
n &amp; m_n(k) \\
1 &amp; 1 \\
2 &amp; k \\
3 &amp; 3k^2-k \\
4 &amp; 15 k^3-10k^2+2k \\
5 &amp; 105 k^4-105 k^3+40 k^2-6k \\
6 &amp; 945 k^5-1260 k^4+700 k^3-196 k^2+24k\\
7 &amp; 10395 k^6-17325 k^5+12600 k^4-5068 k^3+1148 k^2-120k \\
8 &amp; 135135 k^7-270270 k^6+242550 k^5-126280 k^4+40740 k^3-\\&amp;-
7848 k^2+720 k\\
9 &amp; 2027025 k^8-4729725 k^7+5045040 k^6-3213210 k^5 +\\
&amp;+1332100 k^4-
363660 k^3+61416 k^2-5040 k \\
10 &amp; 34459425 k^9-91891800 k^8+113513400 k^7-85345260
k^6+\\&amp;+43022980 k^5-15020720 k^4+3584856 k^3-541728 k^2+40320 k
\end{array}
$$

\section*{Acknowledgement}

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

\begin{thebibliography}{99}
\bibitem{goul83} I.~P.~Goulden, and D.~M.~Jackson,
{\it Combinatorial Enumeration}, Wiley, 1983 (Dover reprint,
2004).

\bibitem{comt70} L.~Comtet, {\it Analyse Combinatoire}, vol.~II,
Presse Universitaire, Paris, 1970.

\bibitem{fult94} W.~Fulton, and R.~MacPherson, A compactification
of configuration spaces, {\it Ann. of Math.} {\bf 139} (1994), 183--225.

\bibitem{keel92}
S.~Keel, Intersection theory of moduli space of stable $n$-pointed
curves of genus zero, {\it Trans. Amer. Math. Soc.}
{\bf 330} (1992), 545--574.

\bibitem{koga04}
L.~M.~Koganov, Inversion of a power series and a result of
S.~K.~Lando, in {\it Proc. VIth Int. Conf. on Discr. Models
in Control Systems Theory}, Moscow, MSU, 2004, pp.\ 170--172.

\bibitem{kont96}
M.~Kontsevich, and Yu.~Manin, Quantum cohomology of a product
(with Appendix by R. Kaufmann), {\it Inv. Math.} {\bf 124} (1996),
313--339.

\bibitem{mani99} Yu.~I.~Manin, {\it Frobenius Manifolds, Quantum
Cohomology, and Moduli Spaces}, AMS Colloquium Publications, 47,
American Mathematical Society, Providence, Rhode Island, 1999.

\bibitem{read02}
M.~A.~Readdy, The pre-WDVV ring of physics and its topology,
preprint, 2002.  Available at
\href{http://www.ms.uky.edu/~readdy/Papers/pre_WDVV.pdf}{\tt http://www.ms.uky.edu/$\tilde{}$readdy/Papers/pre\_WDVV.pdf}.

\bibitem{rior67} J.~Riordan, {\it An Introduction to
Combinatorial Analysis,} Wiley, 1967.

%\bibitem{whit27} E.~T.~Whittaker, and G.~N.~Watson, {\it A Course
%in Modern Analysis}, Cambridge University Press, 1927.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11Y55.

\noindent \emph{Keywords: } cohomology rings of the moduli space,
exponential generating functions, recurrences.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A074059}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 15 2005;
revised version received October 12 2005.
Published in {\it Journal of Integer Sequences}, October 12 2005.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
</pre></body></html>