\input amstex \magnification\magstep 1 \input epsf.tex \documentstyle{amsppt} \topmatter \title Trees Associated with the Motzkin Numbers \endtitle \leftheadtext{A.~Kuznetsov, I.~Pak, A.~Postnikov} \author {Alexander Kuznetsov\medskip {\rm %Department of Mathematics\\ Moscow State University\\ E-mail: sasha\@sch57.mcn.msk.su} \bigskip Igor~Pak\medskip {\rm % Department of Mathematics\\ Harvard University\\ E-mail: pak\@math.harvard.edu} \bigskip Alexander~Postnikov\medskip {\rm %Department of Mathematics\\ Massachusetts Institute of Technology\\ E-mail: apost\@math.mit.edu}} \endauthor \date July 19, 1995 \enddate \address Dept. of Mathematics, Moscow State University, Leninskie Gory, Moscow, Russia \endaddress \address Dept. of Mathematics, Harvard University, Cambridge, MA 02138, U.S.A. \endaddress \address Dept. of Mathematics, MIT, Cambridge, MA 02139, U.S.A. \endaddress %\keywords \endkeywords \abstract We consider plane rooted trees on $n{+}1$ vertices without branching points on odd levels. The number of such trees in equal to the Motzkin number $M_n$. We give a bijective proof of this statement. \endabstract \endtopmatter \document \noindent {\bf 1.}\qquad Let $\Cal P_n$ be the set of all plane rooted trees on $n{+}1$ unlabeled vertices with edges oriented from the root (see \cite{1}). We say that a vertex $v$ in a tree $T\in \Cal P_n$ is a {\it branching point} if at least two edges in $T$ go from $v$. The {\it level} of a vertex $v$ is the number of edges in the shortest path between $v$ and the root. Let $\Cal E_n\subset\Cal P_n$ denote the set of plane trees without branching points on odd levels. By $\Cal M_n\subset\Cal P_n$ denote the set of plane trees with at most two edges going from every vertex. The {\it Motzkin number} $M_n$ is the number of elements in $\Cal M_n$. The generating function $M(x)=1+\sum_{n\ge 0}M_nx^{n{+}1}$ satisfies the following functional equation (see \cite{1, 2, 3}): $$ M(x)=1+xM(x)+x^2M^2(x). $$ This equation gives a recurrence relation for the Motzkin numbers. Note that $|\Cal P_n|$ is the {\it Catalan number} $ C_n=\frac1{n+1}\binom{2n}n$ (see \cite{1, 3}). \proclaim{Theorem 1} $|\Cal E_n|=M_n$. \endproclaim \nopagebreak \proclaim{Theorem 2} The number of trees $T\in \Cal E_n$ with $k{+}1$ vertices on even levels is equal to $ \binom{n}{2k}C_k$. \endproclaim We get well-known formula $M_n=\sum_{k\ge0}\binom{n}{2k}C_k$ (see \cite{2, 4}). \bigskip \noindent{\bf 2.}\qquad Our proofs of Theorems~1 and~2 are based on a bijection $\rho:\Cal E_n\to \Cal M_n$. Let $\Cal B_n$ be the set of binary trees with $n$ unlabeled vertices (see \cite{1}). There is a simple bijection $\phi:\Cal P_n\to\Cal B_n$ (see e.g. \cite{1, 3}). This bijection is clear from an example on Fig.~1. \midinsert %\vskip 10pt \line{\hfill\epsfysize=2.0cm\epsfbox{fig1.eps}\hfill} %\vskip 10pt \botcaption{Figure 1} Bijection $\phi:\Cal P_n\to\Cal B_n$. \endcaption \endinsert Denote $\Cal{EB}_n=\phi(\Cal E_n)$ and $\Cal{MB}_n=\phi(\Cal M_n)$. Then a tree $T$ is an element of $\Cal{MB}_n$ if and only if there are no chains of two left edges in $T$. We say that {\it level} of a vertex~$v$ in a binary tree is the number of right edges in the shortest path between the root and~$v$. Then a binary tree $T$ is an element of $\Cal{EB}_n$ if and only if there are no left edges in $T$ which go from an odd level vertex. Let $\tau:\Cal B_n\to\Cal B_n$ be the involution which exchanges left and right edges in a tree $T\in\Cal B_n$. Now construct a bijection $\eta:\Cal{EB}_n\to\tau(\Cal{MB}_n)$. Let the map $\eta$ changes all right edges in $T\in\Cal{EB}_n$ going from an odd level vertex to left edges. Then $\eta(T)$ does not have chains of two rights edges, otherwise, one of the edges in such a chain goes from an odd level vertex. Conversely, construct the inverse map $\eta^{-1}:\tau(\Cal{MB}_n)\to\Cal{EB}_n$. Let $T\in\tau(\Cal{MB}_n)$. For every right edge $(v,u)$ in $T$ such that $u$ has a child $w$ (then $(u,w)$ should be a left edge) we change $(u,w)$ to a right edge. It is not difficult to see that we get a tree from $\Cal{EB}_n$ and this map is the inverse to $\eta$. Hence $\eta$ is a bijection between $\Cal{EB}_n$ and $\tau(\Cal{MB}_n)$. Now $\rho=\phi^{-1}\circ \tau\circ\eta\circ\phi$ is a bijection between $\Cal E_n$ and $\Cal M_n$. See Fig.~2, as an example. We have proved Theorem~1. \midinsert \vskip 10pt \line{\hfil \epsfysize=6.0cm \epsfbox{fig2.eps}\hfil } \vskip 10pt \botcaption{Figure 2} Bijection $\rho:\Cal E_n\to\Cal M_n$. \endcaption \endinsert \smallskip The proof of Theorem~2 is based on the following property of the bijection $\rho$: The number of vertices on even levels of a plane tree $T\in \Cal E_n$ is equal to the number of end points in the plane tree $\rho(T)\in\Cal M_n$. Indeed, let a tree $T\in\Cal E_n$ have $k{+}1$ vertices on even levels. Then $\phi(T)$ contains $k{+}1$ vertices which do not have a left child and which are either end points or lie on an even level. The bijection $\eta$ maps these vertices to the vertices of $(\eta\circ\phi)(T)$ which do not have a left child. And $\phi^{-1}\circ\tau$ maps them to the end points of $\rho(T)$. On the other hand, it is known (see \cite{4}) that the number of trees $T\in \Cal M_n$ with $k{+}1$ end points is equal to $\binom{n}{2k}C_k$. This completes the proof of Theorem~2. \remark{Remark} The bijection $\rho$ is an ``unlabeled analogue'' of a bijection from \cite{5}. In this sense, the sequence of Motzkin numbers is an ``unlabeled analogue'' of the numbers of up-down (alternating) permutations. \endremark \vfil \pagebreak \Refs\widestnumber\key{4} \ref\key 1\by I. P. Goulden, D. M. Jackson \book Combinatorial Enumeretion \publ John Wiley \publaddr New York \yr 1983 \endref \ref\key 2\by Th. Motzkin \paper Relations between hyperface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products \jour Bull. Amer. Math. Soc. \vol 54 \yr 1948 \pages 352--360 \endref \ref\key 3\by R. Donaghey, L. W. Shapiro \paper Motzkin numbers \jour J. Comb. Theory. Ser. A \vol 23 \yr 1977 \pages 291--301 \endref \ref\key 4\by R. Donaghey \paper Restricted plane tree representations of four Motzkin-Catalan Equations \jour J. Comb. Theory. Ser. B \vol 22 \yr 1977 \pages 114--121 \endref \ref \key 5\by A. G. Kuznetsov, I. M. Pak, A. E. Postnikov \paper Increasing trees and alternating permutations \jour Russian Math. Surveys \vol 49 \yr 1994 \pages 79--110 \endref \endRefs \enddocument