\documentclass[12pt,reqno]{article} \usepackage [colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \usepackage{color} \usepackage{fullpage} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb,graphicx} \usepackage[all]{xy} \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}}} \newtheorem{theorem}{Theorem} \def\trace{\rm trace}\newcommand{\qed}{\hfill\vrule height6pt width6pt depth0pt \medskip} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm {\LARGE\bf Some formulas for the central trinomial} \vskip .3cm {\LARGE\bf and Motzkin numbers} \vskip 1cm \large Dan Romik\\ Department of Mathematics\\ Weizmann Institute of Science\\ Rehovot 76100\\ Israel\\ \href{mailto:romik@wisdom.weizmann.ac.il}{romik@wisdom.weizmann.ac.il} \end{center} \vskip 0.5cm \begin{abstract} We prove two new formulas for the central trinomial coefficients and the Motzkin numbers. \end{abstract} \section{Introduction} \bigskip Let $c_n$ denote the $n$th \emph{central trinomial coefficient}, defined as the coefficient of $x^n$ in the expansion of $(1+x+x^2)^n$, or more combinatorially as the number of planar paths starting at $(0,0)$ and ending at $(n,0)$, whose allowed steps are $(1,0), (1,1), (1,-1)$. Let $m_n$ denote the $n$th \emph{Motzkin number}, defined as the number of such planar paths which do not descend below the $x$-axis. The first few $c_n$'s are $1,3,7,19,51,...$, and the first few $m_n$'s are $1,2,4,9,21,...$. We prove \begin{theorem}\ \vspace{-15.0pt} \begin{equation} {\label{eq:motzkin}} m_n = \sum_{k=\lceil (n+2)/3 \rceil}^{\lfloor (n+2)/2 \rfloor} \frac{(3k-2)!}{(2k-1)!(n+2-2k)!(3k-n-2)!} \end{equation} \begin{equation} {\label{eq:trinomial}} c_n = (-1)^{n+1} + 2n \sum_{k=\lceil n/3 \rceil}^{\lfloor n/2 \rfloor} \frac{ (3k-1)! }{ (2k)! (n-2k)! (3k-n)! } \end{equation} \end{theorem} It is interesting to compare these formulas with some of the other known formulas \cite{6} for $m_n$ and $c_n$: $$ m_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{k!(k+1)!(n-2k)!} $$ $$ m_n = \sum_{k=0}^n \frac{(-1)^{n+k}\ n!\,(2k+2)!}{k!\,((k+1)!)^2\,(k+2) (n-k)!} $$ $$ c_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{(k!)^2 (n-2k)!} $$ $$ c_n = \frac{1}{2^n} \sum_{k=0}^{\lfloor n/2\rfloor} \frac{3^k (2n-2k)!}{k!(n-k)!(n-2k)!} $$ Formulas such as \eqref{eq:motzkin} and \eqref{eq:trinomial} can be proven automatically by computer, using the methods and software of Petkov\v sek, Wilf and Zeilberger \cite{5}. We offer an independent, non-automatic proof that involves a certain symmetry idea which might lead to the discovery of other such identities. Two simpler auxiliary identities used in the proof are also automatically verifiable and shall not be proved. \section{Proof of the main result} \paragraph{Proof of \eqref{eq:motzkin}.} Our proof uses a variant of the generating function \cite{6} for the numbers $m_n$, namely $$ f(x) = \frac{1-x+\sqrt{1+2x-3x^2}}{2} = 1 - x^2 + \sum_{n=3}^\infty (-1)^{n+1} m_{n-2} x^n $$ Then $f$ satisfies $f(0)=1, f(1)=0$ and is decreasing on $[0,1]$. Another property of $f$ that will be essential in the proof is that it satisfies the functional equation \begin{equation} {\label{eq:symmetry}} f(x)^2 - f(x)^3 = x^2 - x^3, \qquad 0\le x\le 1, \end{equation} as can easily be verified. A simple corollary of this is that $f(f(x))=x$ for $x\in[0,1]$. Next, define $$ g(x) = \sum_{k=1}^\infty \frac{2(3k-2)!}{(2k)!(k-1)!} (x^2-x^3)^k $$ Since on $[0,1]$, the maximal value attained by $x^2-x^3$ is $4/27$ (at $x=2/3$), by Stirling's formula the series is seen to converge everywhere on $[0,1]$, to a function $g(x)$ which is real-analytic except at $x=2/3$. We now expand $g(x)$ in powers of $1-x$; all rearrangement operations are permitted by absolute convergence: $$ g(x) = \sum_{k=1}^\infty \frac{2(3k-2)!}{(2k)!(k-1)!} x^{2k} (1-x)^k = $$ $$ = \sum_{k=1}^\infty \frac{2(3k-2)!}{(2k)!(k-1)!} (1-x)^k \sum_{j=0}^k \binom{2k}{j} (-1)^j (1-x)^j = $$ $$ = \sum_{n=1}^\infty \left(\sum_{k=\lceil n/3 \rceil}^n \binom{2k}{n-k} (-1)^{n+k} \frac{2(3k-2)!}{(2k)!(k-1)!} \right) (1-x)^n = 1-x,$$ where the last equality follows from the automatically verifiable \cite{5} identity $$ \sum_{k=\lceil n/3 \rceil}^n \frac{(-1)^k (3k-2)!}{(k-1)!(n-k)!(3k-n)!} = 0,\qquad n>1 .$$ We have shown that $g(x)=1-x$ near $x=1$. But since $g(x)$ is defined as a function of $x^2-x^3$, by \eqref{eq:symmetry} it follows that $g(f(x))=g(x)$, and therefore near $x=0$ we have $$ g(x) = g(f(x)) = 1-f(x) = x^2 + \sum_{n=3}^\infty (-1)^n m_{n-2} x^n .$$ Now to prove \eqref{eq:motzkin}, we expand $g(x)$ into powers of $x$, again using easily justifiable rearrangement operations $$ g(x) = \sum_{k=1}^\infty \frac{2(3k-2)!}{(2k)!(k-1)!} x^{2k} (1-x)^k = $$ $$ = \sum_{k=1}^\infty \frac{2(3k-2)!}{(2k)!(k-1)!} x^{2k} \sum_{j=0}^k \binom{k}{j} (-1)^j x^j = $$ $$ = \sum_{n=2}^\infty \left( (-1)^n \sum_{k=\lceil n/3 \rceil}^{\lfloor n/2 \rfloor} \frac{ (3k-2)!}{(2k-1)!(n-2k)!(3k-n)!} \right) x^n . $$ Equating coefficients in the last two formulas gives \eqref{eq:motzkin}. \qed \paragraph{Proof of \eqref{eq:trinomial}.} We use a similar idea, this time using instead of the function $f(x)$ the function $-\log f(x)$, which generates a sequence related to $c_n$. Since the generating function for $c_n$ is well known \cite{6} to be $1/\sqrt{1-2x-3x^2}$, it is easy to verify that $$ \frac{f'(x)}{f(x)} = \sum_{n=0}^\infty \frac{(-1)^n c_{n+1} -1}{2}\ x^n $$ and therefore $$ -\log f(x) = \sum_{n=1}^\infty \frac{(-1)^n c_n+1}{2n}\ x^n .$$ Now define the function $$ h(x) = \sum_{k=1}^\infty \frac{(3k-1)!}{k!(2k)!}(x^2-x^3)^k $$ which again converges for all $x\in[0,1]$ to a function which is analytic except at $x=2/3$. Expanding $h(x)$ into powers of $1-x$ gives $$ h(x) = \sum_{k=1}^\infty \frac{(3k-1)!}{k!(2k)!}(1-x)^k \sum_{j=0}^{2k} \binom{2k}{j} (-1)^j (1-x)^j = $$ $$ = \sum_{n=1}^\infty \left( \sum_{k=\lceil n/3 \rceil}^n \binom{2k}{n-k} (-1)^{n-k} \frac{(3k-1)!}{k!(2k)!} \right) (1-x)^n = $$ $$=\sum_{n=1}^\infty \frac{(1-x)^n}{n} = -\log x, $$ again making use of a verifiable identity \cite{5}, namely that \begin{equation}\label{eq:liggett} (-1)^n \sum_{k=\lceil n/3 \rceil}^n \frac{(-1)^k (3k-1)!}{k!(n-k)!(3k-n)!} = \frac{1}{n}, \qquad n\ge 1. \end{equation} So $h(x)=-\log x$ near $x=1$, and therefore because of the symmetry property \eqref{eq:symmetry} we have that $h(x)=-\log f(x)$ near $x=0$. Expanding $h(x)$ in powers of $x$ near $x=0$ gives $$ -\log f(x) = h(x) = \sum_{k=1}^\infty \frac{(3k-1)!}{k!(2k)!}x^{2k} \sum_{j=0}^k \binom{k}{j} (-1)^j x^j = $$ $$ = \sum_{n=2}^\infty \left((-1)^n \sum_{k=\lceil n/3 \rceil}^{\lfloor n/2 \rfloor} \frac{(3k-1)!}{(2k)!(n-2k)!(3k-n)!} \right) x^n $$ Equating coefficients with our previous expansion of $h(x)$ gives \eqref{eq:trinomial}. \qed \paragraph{Remarks.} \begin{enumerate} \item One obvious question on seeing formulas \eqref{eq:motzkin} and \eqref{eq:trinomial} is, Can they be explained combinatorially? That is, do there exist bijections between sets known to be enumerated by the numbers $m_n$ and $c_n$, and sets whose cardinality is seen to be the right-hand sides of \eqref{eq:motzkin} and \eqref{eq:trinomial}? Such explanations elude us currently. \item Identity \eqref{eq:liggett} is a special case of a more general identity \cite[Eq.\ (6)]{4} that was discovered by Thomas Liggett. \item See \cite{1,2,3,6} for some other formulas involving the central trinomial coefficients and the Motzkin numbers, and for more information on the properties, and the many different combinatorial interpretations, of these sequences. \end{enumerate} \section{Acknowledgments} Thanks to the anonymous referee for some useful suggestions and references. \begin{thebibliography}{9} \bibitem{1} M. Aigner, Motzkin numbers. {\it European J. Combin.} 19 (1998), 663--675. \bibitem{2} E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family. {\it Pure Math. Appl. Ser. A} 2 (1991), 249--279. \bibitem{3} R. Donaghey and L. W. Shapiro, Motzkin numbers. {\it J. Combin. Theory Ser. A} 23 (1977), 291--301. \bibitem{4} A. E. Holroyd, D. Romik and T. M. Liggett, Integrals, partitions and cellular automata. To appear in {\it Trans. Amer. Math. Soc.} \bibitem{5} M. Petkov\v sek, H. S. Wilf and D. Zeilberger, $A=B$, A. K. Peters, 1996. \bibitem{6} N. J. A. Sloane, editor (2003), The On-Line Encyclopedia of Integer Sequences, \texttt{http://www.research.att.com/$\tilde{\ }$njas/sequences/}, sequences \texttt{A002426}, \texttt{A001006}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: 05A10, 05A15, 05A19.\ \ \noindent \emph{Keywords: } central trinomial coefficients, Motzkin numbers, binomial identities. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A001006} and \seqnum{A002426}.) \vspace*{+.1in} \noindent Received March 25, 2003; revised version received June 20, 2003. Published in {\it Journal of Integer Sequences} July 8, 2003. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterlo o.ca/JIS/}. \vskip .1in \end{document}