\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{amsthm} \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 From $(2,3)$-Motzkin Paths to Schr\"oder Paths } \vskip 1cm \large Sherry H. F. Yan\\ Department of Mathematics \\ Zhejiang Normal University\\ Jinhua 321004 \\ P. R. China\\ \href{mailto:hfy@zjnu.cn}{\tt hfy@zjnu.cn}\\ \end{center} \vskip .2 in \begin{abstract} In this paper, we provide a bijection between the set of restricted $(2,3)$-Motzkin paths of length $n$ and the set of Schr\"oder paths of semilength $n$. Furthermore, we give a one-to-one correspondence between the set of $(2,3)$-Motzkin paths of length $n$ and the set of little Schr\"oder paths of semilength $n+1$. By applying the bijections, we get the enumerations of Schr\"oder paths according to the statistics ``number of $udd$'s" and ``number of $hd$'s". \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} %\usepackage{amssymb,amsfonts,amsmath, psfrag,eepic,colordvi} \newtheorem{theo}{Theorem} \newtheorem{defi}[theo]{Definition} \newtheorem{exam}[theo]{Example} \newtheorem{lem} [theo]{Lemma} \newtheorem{coro}[theo]{Corollary} \newtheorem{prop}[theo]{Proposition} \newtheorem{re}[theo]{Remark} \newtheorem{perty}[theo]{Property} %\makeatletter \@addtoreset{equation}{section} %\@addtoreset{theo}{}\makeatother %\renewcommand{\theequation}{\arabic{section}.\arabic{equation}} %\renewcommand{\thesection}{\arabic{section}.} %\renewcommand{\thetheo}{\arabic{section}.\arabic{theo}} %\renewcommand{\arraystretch}{1.3} \def\o{\overline{o}} \def\e{\overline{e}} \def\mp{\mbox{pyramid}} \def\mb{\mbox{block}} \def\mc{\mbox{cross}} \vskip 1cm %------------------------------------------------------------- \section{Introduction and notations} A {\it (2,3)-Motzkin} path of length $n$ is a lattice path from $(0,0)$ to $(n,0)$ that does not go below the $x$-axis and consists of up steps $u=(1,1)$, down steps $d=(1,-1)$ and level steps $l=(1,0)$, where each up step is possibly colored by $u_1$ or $u_2$ and each level step is possibly colored by $l_1$, $l_2$ or $l_3$. such Motzkin paths have been extensively studied by Woan \cite{Woan1, Woan2}. Ordinary Motzkin paths arise when both level steps and up steps are only of one color. They are counted by the so-called Motzkin numbers \cite{Don}. Denote by $\mathcal{M}_n$ the set of $(2,3)$-Motzkin paths of length $n$ and $m_n$ its cardinality. Recall that $m_n$ equals $n+1$-th super-Catalan number or little Schr\"{o}der number (\seqnum{A001003} in \cite{Seq}). A {\it restricted (2,3)-Motzkin} path of length $n$ is a $(2,3)$-Motzkin path such that each level step on the x-axis is possibly colored by $l_2$ or $l_3$. Denote by $\mathcal{M^*}_n$ the set of restricted $(2,3)$-Motzkin paths of length $n$ and $m^*_n$ its cardinality. $m^*_n$ equals $n$-th large Schr\"{o}der number (\seqnum{A006318} in \cite{Seq}). A {\it Schr\"oder path} of semilength $n$ is a lattice path from $(0,0)$ to $(2n,0)$ that does not go below the $x$-axis and consists of up steps $u=(1,1)$, down steps $d=(1,-1)$ and horizontal steps $h=(2,0)$. They are counted by the larger Schr\"{o}der numbers (\seqnum{A006318} in \cite{Seq}). Denote by $\mathcal{R}_n$ the set of Schr\"oder paths of semilength $n$ and $r_n$ its cardinality. A {\it little Schr\"oder path} is a Schr\"oder path without horizontal steps on the $x$-axis. Denote by $\mathcal{S}_n$ the set of little Schr\"oder paths of semilength $n$ and $s_n$ its cardinality. It is well known that $s_{n}$ is the $n$-th super-Catalan number or little Schr\"{o}der number (\seqnum{A001003} in \cite{Seq}) with $s_0=s_1=1, s_2=3, s_3=11$. Hence we have the relation $s_{n+1}=m_n$ and $r_n=m^*_n$ for $n\geq 0$ . In this paper, we aim to provide a bijection between the set of restricted $(2,3)$-Motzkin paths of length $n$ and the set of Schr\"oder paths of semilength $n$. By refining this bijection, we obtain a bijection between the set of $(2,3)$-Motzkin paths of length $n$ and the set of little Schr\"oder paths of semilength $n+1$. The enumeration of Dyck paths according to semilength and various other parameters has been extensively studied in several papers \cite{ Mer, Mansour, Sun}. The enumeration of Dyck paths according to the statistic ``number of udu's" has been recently considered by Sun\cite{Sun}. His results was generalized by Mansour \cite{Mansour} by studying the statistic ``number of $uu\ldots udu$'s" and the statistic ``number of $udud\ldots udu$'s". However, there are few results on the enumerations of little Schr\"oder paths according to semilength and various other parameters. By applying bijections, we get the enumerations of Schr\"oder paths according to the statistics: `` number of $udd$'s " and `` number of $hd$'s". The organization of this paper is as follows. In Section 2, we give a bijection between the set of restricted $(2,3)$-Motzkin paths of length $n$ and the set of Schr\"oder paths of semilength $n$. By refining this bijection, one-to-one correspondence between the set of $(2,3)$-Motzkin paths of length $n$ and the set of little Schr\"oder paths of semilength $n+1$ is found. In section 3, by specializing the bijections, we get the enumerations of Schr\"oder paths according to statistics: `` number of $udd$'s " and `` number of $hd$'s". \section{Bijections between $(2,3)$-Motzkin paths and Schr\"oder paths} In this section, our goal is to construct a bijection between the set of restricted $(2,3)$-Motzkin paths of length $n$ and Schr\"oder paths of semilength $n$. By refining this bijection we get a bijection between $(2,3)$-Motzkin paths of length $n$ and little Schr\"oder paths of semilength $n+1$. Before giving the bijections, we recall some definitions. For any step in a lattice path, we say that it is at level $k$ if the $y$-coordinate of its end point equals $k$. For an up step $s$ at level $k$, its {\it corresponding down step} is defined to be the leftmost down step at level $k-1$ right to $s$. Similarly, for a down step $s$ at level $k$, its {\it corresponding up step} is defined to be the rightmost up step at level $k+1$ left to $s$. In a Schr\"oder path, the level of $udd$ is equal to that of its step $u$ and the level of $hd$ is equal to that of its step $h$. A $udd$ is said to be {\it high} if its level is larger than two. A $hd$ is said to be {\it high} if its level is lager than one. In a Schr\"oder path, a {\it $udd\ldots d$} consists of an up step and at least two immediately followed down steps; similarly, a {\it $hd\ldots d$} consists of a horizontal step and immediately followed down steps; a $udd\ldots d$ or $hd\ldots d$ is called {\it maximal} if it is not followed by another down step; a peak is said to be {\it single} if it is not followed immediately by a down step; similarly, a horizontal step is said to be {\it single} if it is not followed immediately by a down step; a down step is called a {\it tail} if it is the last down step of a maximal $udd\ldots d$ or $hd\ldots d$; an up step is called a {\it head} if it is the up step of $udd\ldots d$. Figure \ref{fig.3} is an illustration of the above definitions. Steps $a,c,$ and $d$ are at levels $1, 3,$ and $ 2$, respectively; the corresponding down step of the step $a$ is the step $f$ and the corresponding up step of the step $d$ is the step $b$; the step $c$ altogether with the step $d$ forms a maximal $hd$; the steps from $e$ to $f$ in the Schr\"oder path form a maximal $uddd$; the first peak from left to right is a single peak; the second and the third horizontal steps from left to right are single; steps $d$ and $f$ are tails; the step $e$ is a head. \begin{figure}[tbp] \begin{center} \setlength{\unitlength}{5mm} \begin{picture}(10,5) \put(0,0){\circle*{0.2}}\put(1,1){\circle*{0.2}}\put(2,0){\circle*{0.2}} \put(3,1){\circle*{0.2}}\put(4,2){\circle*{0.2}}\put(5,3){\circle*{0.2}} \put(7,3){\circle*{0.2}}\put(8,2){\circle*{0.2}}\put(10,2){\circle*{0.2}} \put(11,3){\circle*{0.2}}\put(12,2){\circle*{0.2}}\put(13,1){\circle*{0.2}} \put(14,0){\circle*{0.2}}\put(16,0){\circle*{0.2}} \put(2.3, 0.7){$a$} \put(4.3, 2.7){$b$} \put(5.7, 3.2){$c$} \put(7.5, 2.7){$d$}\put(10.3, 2.7){$e$} \put(13.5, 0.7){$f$} \put(0,0){\line(1,1){1}}\put(1,1){\line(1,-1){1}}\put(2,0){\line(1,1){1}} \put(3,1){\line(1,1){1}}\put(4,2){\line(1,1){1}}\put(5,3){\line(1,0){2}} \put(7,3){\line(1,-1){1}}\put(8,2){\line(1,0){2}}\put(10,2){\line(1,1){1}} \put(11,3){\line(1,-1){3}}\put(14,0){\line(1,0){2}} \end{picture} \end{center} \caption{ A Schr\"oder path } \label{fig.3} \end{figure} Now we construct a map $\tau: \mathcal{M^*}_n\rightarrow \mathcal{R}_n$. Given a restricted $(2,3)$-Motzkin path $P$ of length $n$, we can obtain a lattice path $\tau(P)$ by the following procedure. \begin{enumerate} \item Firstly, for each down step x, find its corresponding up step y. If y is at level $k$ and colored by $u_1$ (resp. $u_2$) and there are $m$ level steps colored by $l_1$ at level $k$ between x and y, then remove the color of y, change $x$ to $h$ (resp. $ud$) and add $m+1$ consecutive down steps immediately after $h$ (resp. $ud$). \item Secondly, change each level step colored by $l_1$ to an up step. \item Lastly, change each level step colored by $l_2$ to a peak, each level step colored by $l_3$ to a horizontal step. \end{enumerate} It is clear that the obtained path $\tau(P)$ is a Schr\"oder path of semilength $n$. Figure \ref{fig.1} is an illustration of the map $\tau$. \begin{figure}[tbp] \begin{center} \setlength{\unitlength}{5mm} \begin{picture}(10,20) \put(-2,0){$\longrightarrow$} \put(0,0){\circle*{0.2}}\put(1,1){\circle*{0.2}}\put(2,0){\circle*{0.2}} \put(3,1){\circle*{0.2}}\put(4,2){\circle*{0.2}}\put(5,3){\circle*{0.2}} \put(7,3){\circle*{0.2}}\put(8,2){\circle*{0.2}}\put(10,2){\circle*{0.2}} \put(11,3){\circle*{0.2}}\put(12,2){\circle*{0.2}}\put(13,1){\circle*{0.2}} \put(14,0){\circle*{0.2}}\put(16,0){\circle*{0.2}} \put(0,0){\line(1,1){1}}\put(1,1){\line(1,-1){1}}\put(2,0){\line(1,1){1}} \put(3,1){\line(1,1){1}}\put(4,2){\line(1,1){1}}\put(5,3){\line(1,0){2}} \put(7,3){\line(1,-1){1}}\put(8,2){\line(1,0){2}}\put(10,2){\line(1,1){1}} \put(11,3){\line(1,-1){3}}\put(14,0){\line(1,0){2}} %------------------------------------------------------------------------------------- \put(-2,5){$\longrightarrow$} \put(0,5){\circle*{0.2}}\put(1,5){\circle*{0.2}}\put(0.3,5.2){\small$l_2$} \put(4,8){\circle*{0.2}}\put(3,7){\circle*{0.2}}\put(2,6){\circle*{0.2}} \put(6,8){\circle*{0.2}}\put(7,7){\circle*{0.2}}\put(8,7){\circle*{0.2}} \put(7.3,7.2){\small$l_3$} \put(9,8){\circle*{0.2}}\put(10,7){\circle*{0.2}}\put(11,6){\circle*{0.2}} \put(12,5){\circle*{0.2}}\put(13,5){\circle*{0.2}}\put(12.3,5.2){\small$l_3$} \put(0,5){\line(1,0){1}}\put(1,5){\line(1,1){3}}\put(4,8){\line(1,0){2}} \put(6,8){\line(1,-1){1}}\put(7,7){\line(1,0){1}}\put(8,7){\line(1,1){1}} \put(9,8){\line(1,-1){3}}\put(12,5){\line(1,0){1}} %------------------------------------------------------------------------------- \put(-2,10){$\longrightarrow$} \put(0,11){\circle*{0.2}}\put(1,11){\circle*{0.2}} \put(0.3,11.2){\small $l_2$}\put(2,12){\circle*{0.2}} \put(3,12){\circle*{0.2}} \put(2.3,12.2){\small $l_1$} \put(4,13){\circle*{0.2}}\put(6,13){\circle*{0.2}} \put(7,12){\circle*{0.2}}\put(8,12){\circle*{0.2}} \put(7.3,12.2){\small $l_3$}\put(9,13){\circle*{0.2}} \put(10,12){\circle*{0.2}}\put(11,11){\circle*{0.2}} \put(12,10){\circle*{0.2}}\put(13,10){\circle*{0.2}} \put(12.3,10.2){\small $l_3$} \put(0,11){\line(1,0){1}}\put(1,11){\line(1,1){1}}\put(2,12){\line(1,0){1}} \put(3,12){\line(1,1){1}}\put(4,13){\line(1,0){2}}\put(6,13){\line(1,-1){1}} \put(7,12){\line(1,0){1}}\put(8,12){\line(1,1){1}}\put(9,13){\line(1,-1){3}} \put(12,10){\line(1,0){1}} %--------------------------------------------------------------------------- \put(0,14){\circle*{0.2}} \put(1,14){\circle*{0.2}} \put(0.3,14){\small$l_2$} \put(2,15){\circle*{0.2}}\put(1.2,14.5){\small$u_2$} \put(3,15){\circle*{0.2}}\put(2.2,15){\small$l_1$} \put(4,16){\circle*{0.2}}\put(3.2,15.6){\small$u_1$} \put(5,15){\circle*{0.2}} \put(6,15){\circle*{0.2}}\put(5.2,15){\small$l_3$} \put(7,14){\circle*{0.2}} \put(8,14){\circle*{0.2}}\put(7.2,14){\small$l_3$} \put(0,14){\line(1,0){1}}\put(1,14){\line(1,1){1}} \put(2,15){\line(1,0){1}}\put(3,15){\line(1,1){1}} \put(4,16){\line(1,-1){1}}\put(5,15){\line(1,0){1}} \put(6,15){\line(1,-1){1}}\put(7,14){\line(1,0){1}} \end{picture} \end{center} \caption{ From a restricted $(2,3)$-Motzkin path to a Schr\"oder path} \label{fig.1} \end{figure} Conversely, we can obtain a $(2,3)$-Motzkin path from a Schr\"oder path. Given a Schr\"oder path $P$ of semilength $n$, we get a lattice path by the following procedure. \begin{enumerate} \item Firstly, change each single peak to a level step colored by $l_2$ and each single horizontal step to a level step colored by $l_3$. \item secondly, for each non-head up step $x$, find its corresponding down step $y$. If $y$ is a tail of a maximal $hd\ldots d$, then color $x$ by $u_1$ and change this $hd\ldots d$ to one down step. If $y$ is a tail of a maximal $udd\ldots d$, then color $x$ by $u_2$ and change this $udd\ldots d$ to one down step. Otherwise, change $x$ to a level step colored by $l_1$. \end{enumerate} It is easy to check that the obtained path is a $(2,3)$-Motzkin paths of length $n$. Note that for any non-head up step at level one, its corresponding down step must be a tail of a maximal $udd\ldots d$ or $hd\ldots d$. Hence, there is no level step colored by $l_1$ at level zero in the obtained path. That is to say, the obtained path is a restricted $(2,3)$-Motzkin path. Therefore, the map $\tau$ is reversible. Figure \ref{fig.2} is an illustration of the inverse map of $\tau$. \begin{figure}[tbp] \begin{center} \setlength{\unitlength}{5mm} \begin{picture}(10,10) \put(-2,0){$\longrightarrow$} \put(0,0){\circle*{0.2}} \put(1,0){\circle*{0.2}} \put(0.3,0){\small$l_2$} \put(2,1){\circle*{0.2}}\put(1.2,0.5){\small$u_2$} \put(3,1){\circle*{0.2}}\put(2.2,1){\small$l_1$} \put(4,2){\circle*{0.2}}\put(3.2,1.6){\small$u_1$} \put(5,1){\circle*{0.2}} \put(6,1){\circle*{0.2}}\put(5.2,1){\small$l_3$} \put(7,0){\circle*{0.2}} \put(8,0){\circle*{0.2}}\put(7.2,0){\small$l_3$} \put(0,0){\line(1,0){1}}\put(1,0){\line(1,1){1}} \put(2,1){\line(1,0){1}}\put(3,1){\line(1,1){1}} \put(4,2){\line(1,-1){1}}\put(5,1){\line(1,0){1}} \put(6,1){\line(1,-1){1}}\put(7,0){\line(1,0){1}} %------------------------------------------------------------------------------------- %------------------------------------------------------------------------------- \put(-2,4){$\longrightarrow$} \put(0,3){\circle*{0.2}} \put(1,3){\circle*{0.2}} \put(0.2,3.2){\small$l_2$} \put(2,4){\circle*{0.2}} \put(3,5){\circle*{0.2}} \put(4,6){\circle*{0.2}} \put(6,6){\circle*{0.2}}\put(7,5){\circle*{0.2}} \put(8,5){\circle*{0.2}}\put(7.2,5.2){\small$l_3$} \put(9,6){\circle*{0.2}}\put(10,5){\circle*{0.2}}\put(11,4){\circle*{0.2}} \put(12,3){\circle*{0.2}}\put(13,3){\circle*{0.2}}\put(12.2,3.2){\small$l_3$} \put(0,3){\line(1,0){1}}\put(1,3){\line(1,1){3}}\put(4,6){\line(1,0){2}} \put(6,6){\line(1,-1){1}}\put(7,5){\line(1,0){1}}\put(8,5){\line(1,1){1}} \put(9,6){\line(1,-1){3}}\put(12,3){\line(1,0){1}} %--------------------------------------------------------------------------- \put(0,7){\circle*{0.2}}\put(1,8){\circle*{0.2}}\put(2,7){\circle*{0.2}} \put(3,8){\circle*{0.2}}\put(4,9){\circle*{0.2}}\put(5,10){\circle*{0.2}} \put(7,10){\circle*{0.2}}\put(8,9){\circle*{0.2}}\put(10,9){\circle*{0.2}} \put(11,10){\circle*{0.2}}\put(12,9){\circle*{0.2}}\put(13,8){\circle*{0.2}} \put(14,7){\circle*{0.2}}\put(16,7){\circle*{0.2}} \put(0,7){\line(1,1){1}}\put(1,8){\line(1,-1){1}}\put(2,7){\line(1,1){1}} \put(3,8){\line(1,1){1}}\put(4,9){\line(1,1){1}}\put(5,10){\line(1,0){2}} \put(7,10){\line(1,-1){1}}\put(8,9){\line(1,0){2}}\put(10,9){\line(1,1){1}} \put(11,10){\line(1,-1){3}}\put(14,7){\line(1,0){2}} \end{picture} \end{center} \caption{ From a Schr\"oder path to a $(2,3)$-Motzkin path} \label{fig.2} \end{figure} \begin{theo}\label{th1} The map $\tau$ is a bijection between the set of restricted $(2,3)$-Motzkin paths of length $n$ and Schr\"oder paths of semilength $n$. \end{theo} From the construction of the bijection $\tau$, we immediately get the following corollary. \begin{coro}\label{coro1} The number of up steps colored by $u_1$ in a restricted $(2,3)$-Motzkin path is equal to that of $hd$'s in the corresponding Schr\"oder path. The number of up steps colored by $u_2$ in a restricted $(2,3)$-Motzkin path is equal to that of $udd$'s in the corresponding Schr\"oder path. \end{coro} With the bijection $\tau$, we can construct a map $\phi: \mathcal{M}_n\rightarrow \mathcal{S}_{n+1}$. Given a $(2,3)$-Motzkin path $P$, it can be uniquely decomposed as $P=P_1l_1P_2\ldots l_1P_m$, where each $P_i$ is possibly empty restricted $(2,3)$-Moztkin path. Now we can construct $\phi(P)$ as follows: firstly, we get a $(2,3)$-Motzkin path $P'=l_1P_1l_1P_2\ldots l_1P_m$ of length $n+1$ by adding a level step colored by $l_1$ at the beginning of $P$; then $\phi(P)=u\tau(P_1)d u\tau(P_2)d \ldots u\tau(P_m)d$. Obviously, the obtained path $\phi(P)$ is a little Schr\"oder path of semilength $n+1$ and the map $\phi$ is invertible. Hence from Theorem \ref{th1} and Corollary \ref{coro1}, we have the following conclusions. \begin{theo}\label{th2} The map $\phi$ is a bijection between the set of $(2,3)$-Motzkin paths of length $n$ and little Schr\"oder paths of semilength $n+1$. \end{theo} \begin{coro}\label{coro2} The number of up steps colored by $u_1$ in a $(2,3)$-Motzkin path is equal to that of high $hd$'s in the corresponding little Schr\"oder path. The number of up steps colored by $u_2$ in a $(2,3)$-Motzkin path is equal to that of high $udd$'s in the corresponding little Schr\"oder path. \end{coro} \section{ Statistics on Schr\"oder paths } In this section, we begin to study the statistics: ``number of $udd$'s" and ``number of $hd$'s" on Schr\"oder paths. Denote by $m_{n,k}$ the number of (2,3)-Motzkin paths of length $n$ and with $k$ up steps. Then we have the following consequence. \begin{lem}\label{lem1} $$ m_{n, k}=3^{n-2k}2^{k}{n\choose 2k}c_k, $$ where $c_k={1\over k+1}{2k\choose k}$ is the $k$-th Catalan number (\seqnum{A000108} in \cite{Seq}). \end{lem} \begin{proof} Given a Dyck path $P$ of length $2k$, we can construct a $(2,3)$-Motzkin path of length $n$ and with $k$ up steps as follows: firstly, insert $n-2k$ level steps between the $2k+1$ positions between the steps of $P$. The number of ways to inserting such steps is counted by ${2k+1+n-2k-1\choose n-2k}={n\choose 2k}$. Then assign the colors to level steps and up steps. There are $3^{n-2k}2^k$ ways to arrange colors. It is clear that the obtained path is a $(2,3)$-Motzkin path. Conversely, given a $(2,3)$-Motzkin path with $k$ up steps, we can remove all the colors of steps and all the level steps to get a Dyck path of length $k$. This completes the proof. \end{proof} Summing over all the possible $k$'s, we get $$ m_{n}=\sum_{0\leq k\leq \lfloor{ n\over 2}\rfloor}3^{n-2k}2^{k}{n\choose 2k}c_k, $$ which is another expression of the little Schr\"{o}der numbers. From the bijection $\tau$, we see that if there is no level step colored by $l_1$ in a restricted $(2,3)$-Motzkin path, then there is no $uddd$ or $hdd$ in its corresponding Schr\"{o}der path. While, by the same way as the proof of Lemma \ref{lem1}, we can get that the number of such $(2,3)$-Motzkin paths of length $n$ and with $k$ up steps is equal to $2^{n-k}{n\choose 2k}c_k$. Hence, by Theorem \ref{th1} and Corollary \ref{coro1}, the following conclusion holds immediately. \begin{coro} The number of Schr\"{o}der paths of semilength $n$ and with altogether $k$ $udd$ and $hd$'s but without $uddd$ or $hdd$ is equal to $$ 2^{n-k}{n\choose 2k}c_k. $$ \end{coro} Similarly, if there is no level step colored by $l_1$ and the up steps are only colored by $u_1$ (resp. $u_2$) in a restricted $(2,3)$-Motzkin path, then there is no $uddd$ and $hd$ (resp. $udd$)in its corresponding Schr\"{o}der path. By simple computation, the number of such $(2,3)$-Motzkin paths of length $n$ and with $k$ up steps is equal to $2^{n-2k}{n\choose 2k}c_k$. Hence, by Theorem \ref{th1} and Corollary \ref{coro1}, the following two conclusions are obtained. \begin{coro} The number of Schr\"{o}der paths of semilength $n$ and with $k$ $udd$'s but without $uddd$ or $hd$ is equal to $$ 2^{n-2k}{n\choose 2k}c_k. $$ \end{coro} \begin{coro} The number of Schr\"{o}der paths of semilength $n$ and with $k$ $hd$'s but without $udd$ or $hdd$ is equal to $$ 2^{n-2k}{n\choose 2k}c_k. $$ \end{coro} A $(2,3)$-Motzkin path with up steps colored by $u_2$ and level steps colored by $l_2$ can be reduced to an ordinary Motzkin path. It is well known that the number of ordinary Motzkin paths of length $n$ and with $k$ up steps is equal to ${n\choose 2k}c_k$. From the construction of the bijection $\tau$, a $(2,3)$-Motzkin path with up steps colored by $u_2$ and level steps colored by $l_2$ corresponds to a Dyck path without $uddd$. Hence, by Theorem \ref{th1} and Corollary \ref{coro1}, the following conclusion is obtained. \begin{coro} The number of Dyck paths of semilength $n$ and with $k$ $udd$'s but without $uddd$ is equal to ${n\choose 2k}c_k$. \end{coro} By Theorem \ref{th2}, Corollary \ref{coro2} and Lemma \ref{lem1}, we get the following result. \begin{coro} little Schr\"{o}der paths of semilength $n+1$ and with altogether $k$ high $udd$ and $hd$'s are counted by $$ 3^{n-2k}2^{k}{n\choose 2k}c_k. $$ \end{coro} If there is no up steps colored by $u_1$ (resp. $u_2$) in a $(2,3)$-Motzkin path, then there is no high $udd$ (resp. high $hd$) in its corresponding Schr\"{o}der path. It is easy to get that the number of such $(2,3)$-Motzkin paths of length $n$ and with $k$ up steps is equal to $3^{n-2k}{n\choose 2k}c_k$. By Theorem \ref{th2} and Corollary \ref{coro2}, we get the following two results. \begin{coro} The number of little Schr\"{o}der paths of semilength $n+1$ and with $k$ high $udd$'s but no high $hd$ is equal to $$ 3^{n-2k}{n\choose 2k}c_k. $$ \end{coro} \begin{coro} The number of little Schr\"{o}der paths of semilength $n+1$ and with $k$ high $hd$'s but no high $udd$ is equal to $$ 3^{n-2k}{n\choose 2k}c_k. $$ \end{coro} From the construction of the bijection $\phi$, a $(2,3)$-Motzkin path with up steps colored by $u_2$ and level steps colored by $l_1$ or $l_2$ corresponds to a Dyck path. It is easy to get that the number of such $(2,3)$-Motzkin paths of length $n$ and with $k$ up steps equals $2^{n-2k}{n\choose 2k}c_k$. Hence, by Theorem \ref{th2} and Corollary \ref{coro2}, the following conclusion is obtained. \begin{coro} The number of Dyck paths of length $2n+2$ and with $k$ high $udd$'s is equal to $$ 2^{n-2k}{n\choose 2k}c_k. $$ \end{coro} \vskip 5mm \noindent{\bf Acknowledgments.} The author would like to thank the referee for his helpful suggestions. \small %------------------------------------------------------------- \begin{thebibliography}{99} \bibitem{Don} R. Donaghey and L. W. Shapiro, Motzkin numbers, {\it J. Combin. Theory Ser. A } {\bf 23} (1977) 291--301. \bibitem{Kreweras} G. Kreweras, Joint distributions of three descriptive parameters of bridges. {\it Combinatoire Enumerative}, 177--191, Lecture Notes in Math., Vol.\ 1234, Springer, Berlin, 1986. \bibitem{Mansour} T.~ Mansour, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.html}{Statistics on Dyck paths}, {\em J. Integer Sequences} {\bf 9} (2006), Article 06.1.5. \bibitem{Mer} D. ~Merlini, R. ~Sprugnoli, and M. C. ~Verri, Some statistics on Dyck paths, {\em J. Statist. Plann. and Infer.} {\bf 101} (2002), 211--227. \bibitem{Seq} N. J. A.~Sloane, \href{http://www.research.att.com/~njas/sequences}{The On-Line Encyclopedia of Integer Sequences}, \\ \href{http://www.research.att.com/~njas/sequences}{\tt http://www.research.att.com/$\thicksim$njas/sequences}. \bibitem{sulanke1993} R. A. Sulanke, A symmetric variation of distribution of Kreweras and Poupard, {\it J. Statist. Plann. Inference}, {\bf 34} (1993) 291--303. \bibitem{sulanke1998} R. A. Sulanke, Catalan path statistics having the Narayana distribution, {\it Discrete Math.}, {\bf 180} (1998) 369--389. \bibitem{Sun} Y. Sun, The statistic of ``udu's" in Dyck paths, {\em Discrete Math.} {\bf 287} (2004), 177--186. \bibitem{Woan1} Wen-jin Woan, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Woan/woan11.html}{A recursive relation for weighted Motzkin sequences}, {\em J. Integer Sequences} {\bf 8} (2005), Article 05.1.6. \bibitem{Woan2} Wen-jin Woan, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Woan/woan206.html}{A relation between restricted and unrestricted weighted Motzkin paths}, {\em J. Integer Sequences} {\bf 9} (2006), Article 06.1.7. \bibitem{Zeilberger} D. Zeilberger, Six {\it \'Etudes} in generating functions, {\it Intern. J. Computer Math.}, {\bf 29} (1989) 201--215. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A19. \noindent \emph{Keywords: } Schr\"oder path, $(2,3)$-Motzkin path. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000108}, \seqnum{A001003}, and \seqnum{A006318}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 18 2007; revised version received August 24 2007. Published in {\it Journal of Integer Sequences}, August 24 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}