\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}

.
