\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)=& \delta_{n,1} & n \ge 1,\\ \mu_{n-1}(n)=&(-1)^n (n-2)! & n \ge 2,\\ \mu_{n-2}(n)=&(-1)^{n-1} (n-2)! \left( n-2+2 \sum_{i=1}^{n-2} \frac{1}{i} \right) & n \ge 3,\\ \mu_{n-3}(n)=&(-1)^n (n-2)! \cdot & \\ & \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) & n \ge 4,\\ &\vdots & \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&=&-t+1,\\ M_2&=&\frac16 t^2-\frac12 t+\frac12-\frac16 t^{-1},\\ M_3&=&\frac{1}{72} t^3-\frac18 t+\frac29-\frac18 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}, \end{eqnarray*} $$\vdots$$ Setting $(-1)!!=1$, this easily implies \begin{eqnarray*} \mu_1(n)&=&(2n-3)!!, \quad n \ge 1,\\ \mu_2(n)&=&-\frac{n-2}3 (2n-3)!!, \quad n \ge 2,\\ \mu_3(n)&=&\frac{(n-1)(n-2)(n-3)}{3^2} (2n-5)!!, \quad n \ge 2,\\ \mu_4(n)&=&-\frac{(n-3)(n-4)(5(n-1)^2+1)}{3^4 \cdot 5} (2n-5)!!, \quad n \ge 3,\\ \mu_5(n)&=&\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=&\{1,1,2,7,34,213,1630,14747,153946,1821473,\\ &24087590, 352080111, 5636451794, 98081813581, \\&1843315388078, 37209072076483, 802906142007946, \\& 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 & m_n(k) \\ 1 & 1 \\ 2 & k \\ 3 & 3k^2-k \\ 4 & 15 k^3-10k^2+2k \\ 5 & 105 k^4-105 k^3+40 k^2-6k \\ 6 & 945 k^5-1260 k^4+700 k^3-196 k^2+24k\\ 7 & 10395 k^6-17325 k^5+12600 k^4-5068 k^3+1148 k^2-120k \\ 8 & 135135 k^7-270270 k^6+242550 k^5-126280 k^4+40740 k^3-\\&- 7848 k^2+720 k\\ 9 & 2027025 k^8-4729725 k^7+5045040 k^6-3213210 k^5 +\\ &+1332100 k^4- 363660 k^3+61416 k^2-5040 k \\ 10 & 34459425 k^9-91891800 k^8+113513400 k^7-85345260 k^6+\\&+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}