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