\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{mathrsfs}
\usepackage{graphicx,pstricks}
\usepackage{amscd}
\usepackage{scalefnt,epsfig}

\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{amsfonts}
\usepackage{latexsym}
\usepackage{epsf,amscd,psfrag, eepic,colordvi}

\usepackage{amsthm}

%\documentclass[12pt,reqno]{article}
%
%\usepackage[usenames]{color}
%
%\usepackage{graphicx,pstricks}
%\usepackage{amscd}
%\usepackage{scalefnt}
%
%\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{amsfonts}
%\usepackage{latexsym}
%\usepackage{epsf}
%
%\usepackage{amsthm}

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


\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{sch}[thm]{Scholium}
\newtheorem{guess}[thm]{Guess}
\newtheorem{ex}[thm]{Example}
\theoremstyle{remark}
    \newtheorem*{rem}{{\bf Remark}}   %no numbering for remarks
    %\theoremstyle{remarks}
    \newtheorem*{rems}{{\bf Remarks}}

    \newtheorem*{note}{Note}
\theoremstyle{definition}
    \newtheorem{defn}[thm]{Definition}






%%\numberwithin{equation}{section}
%\def\ds{\displaystyle}\def\C{{\mathcal C}}
%\def\Z {{\mathbb Z}}
%\def\AM {{\mathcal A}}
%\def\BM {{\mathcal S}}
%\def\CM {{\mathcal T}}
%%\def\N{{\mathcal N}}
%%\def\Q {{\mathbb Q}}
%%\def\T {{\tilde T}}
%%\def\D {{\mathcal D}}
%%\def\N {{\mathcal N}}
%%\def\M {{\mathcal M}}
%%\def\H {{\mathcal H}}
%%\def\h {{\mathfrak h}}
%%\def\l {\left\langle}
%%\def\r {\right\rangle}
%%\def\bip{{\mathrm{Bip}}}
%\def\K{{\mathcal K}}
%%\def\k{{\mathbf k}}
%%\def\n{{\mathbf n}}

\begin{center}
\vskip 1cm{\LARGE\bf {A Bijection Between $3$-Motzkin Paths and\\
\vskip .1in Schr\"{o}der Paths With No Peak at Odd Height}}

\vskip 1cm
\large Louis W. Shapiro\footnote{All correspondence
should
be directed to this author.} \\
Mathematics Department \\
Howard University\\
Washington, DC 20059\\
 USA\\
\href{mailto:lshapiro@howard.edu}{\tt lshapiro@howard.edu}\\
\ \\
Carol J. Wang \\
Center for Combinatorics, LPMC-TJKLC\\
Nankai University, Tianjin 300071\\
P. R. China\\
\href{wangjian@cfc.nankai.edu.cn}{\tt wangjian@cfc.nankai.edu.cn}\\
\ \\

\end{center}

\begin{abstract}
A new bijection between $3$-Motzkin paths and Schr\"{o}der paths
with no peak at odd height is presented, together with numerous
consequences involving related combinatorial structures such as
$2$-Motzkin paths, ordinary Motzkin paths and Dyck paths.
\end{abstract}

\vskip .2in

\renewcommand{\theequation}{\arabic{equation}}

\renewcommand{\theequation}{\arabic{equation}}




\section{Introduction}%\label{Intro}

We define \textit{$k$-Motzkin paths} as paths from $(0,0)$ to
$(n,0)$ not going below $x$-axis using steps $U=(1,1),D=(1,-1)$ and
$L=(1,0)$ where the $L$ steps can be any of $k$ colors. The cases
with $k=0,1,2$ and $3$ counting these paths yield
\begin{itemize}
\item[] $k=0$, Catalan numbers, $1,0,1,0,2,0,5,0,14,0,\ldots$,
\seqnum{A097331};

\item[] $k=1$, Motzkin numbers, $1,1,2,4,9,21,51,127,\ldots$,
\seqnum{A001006};

\item[] $k=2$, Catalan numbers($C_{n+1}$), $1,2,5,14,42,132,\ldots$,
\seqnum{A000108};

\item[] $k=3$, Harary-Read Benzene numbers, $1,1,3,10,36,137,543,\ldots$,
\seqnum{A002212}.
\end{itemize}
The `A' numbers are from Sloane's {\it Encyclopedia} \cite{EIS}.

Harary-Read Benzene numbers count the number of restricted hexagonal
polyominoes with $n$ cells and equivalently rooted planar trees
where the outdegree of each vertex is $0,1$ or $2$. If the outdegree
is $1$, then it can be a left, right, or middle child. If the
outdegree is $2$, the vertex must have a left and right child.
Denote such trees by \textit{HR-trees}. This last condition
prohibits the configuration shown below.
\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{1.5mm}
\begin{picture}(20,10)
\qbezier(5,0)(6.5,0)(8,0)\qbezier(5,0)(4.25,1.3)(3.5,2.6)
\qbezier(3.5,2.6)(4.25,3.9)(5,5.2)\qbezier(5,5.2)(6.5,5.2)(8,5.2)
\qbezier(8,5.2)(8.75,3.9)(9.5,2.6)\qbezier(9.5,2.6)(8.75,1.3)(8,0)
\qbezier(5,5.2)(4.25,6.5)(3.5,7.8)\qbezier(3.5,7.8)(4.25,9.1)(5,10.4)
\qbezier(5,10.4)(6.5,10.4)(8,10.4)\qbezier(8,10.4)(8.75,9.1)(9.5,7.8)
\qbezier(9.5,7.8)(8.75,6.5)(8,5.2)\qbezier(9.5,7.8)(11,7.8)(12.5,7.8)
\qbezier(12.5,7.8)(13.25,6.5)(14,5.2)\qbezier(14,5.2)(13.25,3.9)(12.5,2.6)
\qbezier(12.5,2.6)(11,2.6)(9.5,2.6)
\end{picture}
\end{center}
\end{figure}

We denote the generating function ($GF$ for short) for the
$k$-Motzkin numbers as $M_{[k]}$. If we change the level step
requirement by one kind of level step of length $2$, we get the
\textit{Schr\"{o}der paths} and the sequence of numbers counting the
Schr\"{o}der paths starts $1,2,6,22,90,394,\ldots$,
\seqnum{A006318}.

Returning to the $k$-Motzkin paths but not allowing any level steps
at height $0$, we have the $k$-Riordan paths. This yields
\begin{itemize}
\item[] $k=1$, the Riordan numbers, $1,0,1,1,3,6,15,36,91,\ldots$,
\seqnum{A005043};
\item[] $k=2$, the Fine numbers, $1,0,1,2,6,18,57,\ldots$,
\seqnum{A000957};
\item[] $k=3$, the $3$-Riordan numbers,
$1,0,1,3,11,42,167,684,\ldots$, \seqnum{A117641}.
\end{itemize}

For Benzene molecules $A,B,C,D,\ldots$, the $3$-Riordan numbers
count the number of ways pasting Benzene rings with no attachments
occurring on the dark edges. The $3$-Riordan numbers also count the
number of $HR$-trees with no middle children on the rightmost
branch. Figure \ref{F1} is a small example to illustrate these
concepts.

\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{2mm}
\begin{picture}(60,18)
\qbezier(3,0)(4.5,0)(6,0) \qbezier(3,0)(2.25,1.3)(1.5,2.6)
\qbezier(1.5,2.6)(2.25,3.9)(3,5.2)\qbezier(3,5.2)(4.5,5.2)(6,5.2)
\qbezier(6,5.2)(6.75,3.9)(7.5,2.6)\qbezier(7.5,2.6)(6.75,1.3)(6,0)
\qbezier(7.5,2.6)(9,2.6)(10.5,2.6)\qbezier(10.5,2.6)(11.25,3.9)(12,5.2)
\qbezier(12,5.2)(11.25,6.5)(10.5,7.8)\qbezier(10.5,7.8)(8.25,7.8)(7.5,7.8)
\qbezier(7.5,7.8)(6.75,6.5)(6,5.2)\qbezier(10.5,7.8)(11.25,9.1)(12,10.4)
\qbezier(12,10.4)(13.5,10.4)(15,10.4)\put(11.5,11){Base}
\qbezier(15,10.4)(15.75,9.1)(16.5,7.8)\qbezier(16.5,7.8)(15.75,6.5)(15,5.2)
\qbezier(15,5.2)(15.75,3.9)(16.5,2.6)\qbezier(16.5,2.6)(18,2.6)(19.5,2.6)
\qbezier(21,5.2)(20.25,6.5)(19.5,7.8)\qbezier(19.5,7.8)(18,7.8)(16.5,7.8)
\qbezier(19.5,7.8)(20.25,9.1)(21,10.4)\qbezier(21,10.4)(22.5,10.4)(24,10.4)
\qbezier(25.5,7.8)(24.75,6.5)(24,5.2)\qbezier(24,5.2)(22.5,5.2)(21,5.2)
\qbezier(21,10.4)(20.25,11.7)(19.5,13)\qbezier(19.5,13)(20.25,14.3)(21,15.6)
\qbezier(24,15.6)(24.75,14.3)(25.5,13)\qbezier(25.5,13)(24.75,11.7)(24,10.4)
\qbezier(25.5,7.8)(27,7.8)(28.5,7.8)\qbezier(28.5,7.8)(29.25,6.5)(30,5.2)
\qbezier(30,5.2)(29.25,3.9)(28.5,2.6)\qbezier(28.5,2.6)(27,2.6)(25.5,2.6)
\qbezier(25.5,2.6)(24.75,3.9)(24,5.2)\qbezier(19.5,2.6)(20.25,1.3)(21,0)
\qbezier(21,0)(20.25,-1.3)(19.5,-2.6)\qbezier(19.5,-2.6)(18,-2.6)(16.5,-2.6)
\qbezier(16.5,-2.6)(15.75,-1.3)(15,0)\qbezier(15,0)(15.75,1.3)(16.5,2.6)
\qbezier(25.5,2.6)(24.75,1.3)(24,0)\qbezier(24,0)(24.74,-1.3)(25.5,-2.6)
\qbezier(25.5,-2.6)(27,-2.6)(28.5,-2.6)\qbezier(28.5,-2.6)(29.25,-1.3)(30,0)
\qbezier(30,0)(29.25,1.3)(28.5,2.6)

{\linethickness{1.8pt}
{\qbezier(15,5.2)(13.5,5.2)(12,5.2)%A
\qbezier(19.5,2.6)(20.25,3.9)(21,5.2)%B
\qbezier(24,10.4)(24.75,9.1)(25.5,7.8)%C
\qbezier(21,15.6)(22.5,15.6)(24,15.6)%D
}}
\put(12.8,7.3){A}\put(17.4,4.5){B}\put(21.8,7.2){C}\put(21.9,12.3){D}

\put(32,5.5){$\Longleftrightarrow$}
%{0,1,2}tree
\put(43,13){\circle*{0.3}}\put(43,14){A}\put(43,13){\line(-1,-1){3}}
\put(40,10){\circle*{0.3}}\put(40,10){\line(0,-1){3}}\put(40,7){\circle*{0.3}}
\put(37,4.5){\textit{middle}}\put(43,13){\line(1,-1){3}}
\put(46,10){\circle*{0.3}}
\put(46.5,10){B}\put(46,10){\line(-1,-1){3}}\put(43,7){\circle*{0.3}}
\put(46,10){\line(1,-1){3}}\put(49,7){\circle*{0.3}}\put(49.5,7){C}
\put(49,7){\line(-1,-1){3}}\put(46,4){\circle*{0.3}}\put(46,4){\line(-1,-1){3}}
\put(43,1){\circle*{0.3}}\put(42,-0.6){\textit{left}}
\put(49,7){\line(1,-1){3}}\put(52,4){\circle*{0.3}}\put(52.5,4){D}


\end{picture}
\end{center}
\caption{Benzene Molecules and the corresponding
$HR$-tree.}\label{F1}
\end{figure}


The $GF$ for counting $k$-Riordan paths is denoted $R_{[k]}$. More
detail can be found in \cite{ST2}. For information about $M_{[3]}$,
see also \cite{CCBB} and \cite{HR}.

The basic identities for these $GF$s are
$$M_{[k]}=1+kzM_{[k]}+z^2M_{[k]}^2\quad {\rm and}\quad R_{[k]}=1+z^2M_{[k]}R_{[k]}.$$

The two generating functions are linked by the identity
\begin{align*}
M_{[k]}&=R_{[k]}+R_{[k]}\cdot kz\cdot R_{[k]}+R_{[k]}\cdot kz\cdot
R_{[k]}\cdot kz\cdot R_{][k]}+\cdots\\
&=\frac{R_{[k]}}{1-kzR_{[k]}},
\end{align*}
where, for instance, $R_{[k]}\cdot kz \cdot R_{[k]}$ accounts for
$k$-Motzkin paths with one level step at height $0$.

This research started while investigating M\"{o}bius transformations
of generating functions. It was noticed that
$\frac{R_{[1]}}{1-zR_{[1]}}=M_{[1]}$ yields the Motzkin numbers, and
$\frac{R_{[2]}}{1-2zR_{[2]} }$ yields the Catalan numbers. Next in
the series is $M_{[3]}=\frac{R_{[3]}}{1-3zR_{[3]}}$. Consulting
Sloane \cite{EIS} yielded the peculiar fact that these numbers also
counted Schr\"{o}der paths with no peak at odd height. This fact was
noticed by Emeric Deutsch who outlined a proof via generating
function for us. However such a coincidence seemed worthy of a more
combinatorial approach.

In this paper, we present an easy bijection between the Schr\"{o}der
paths of length $2n$ with no peak at odd height and $3$-Motzkin
paths of length $n-1$. One consequence of this simple bijection is
that many new occurrences of paths counted by the Catalan, Motzkin,
Fine, and Riordan numbers can be found as Schr\"{o}der paths with
various restrictions. We will examine a few such cases in detail and
then list some of the others.

A recent paper of Yan~\cite{Yan} discusses a different bijection
between $(2,3)$-Motzkin paths and Schr\"{o}der paths for the purpose
of enumerating the $UDD$ and $LD$ subsequences. For more information
about the Fine number sequences, see~\cite{DS99} and~\cite{DS02}.
Some useful generating function identities are discussed
in~\cite{DS01}. Another paper of definite interest \cite{MSS} of
Mansour, Schork, and Sun discusses Motzkin paths where not only
level steps but also up and down steps are colored. In particular if
the up steps are bicolored and neither level nor down steps are,
then the sequence \seqnum{A025235} which starts $
1,1,3,7,21,61,191,\ldots$ is obtained. If both level and up steps
are bicolored the result is the sequence \seqnum{A071356} starting $
1,2,6,20,72,272,1064,\ldots$.


\section{The bijection}

We describe the bijection, denoted by $\phi$, between Schr\"{o}der
paths of length $2n$ with no peak at odd height and $3$-Motzkin
paths of length $n-1$. Let $\omega$ be a Schr\"{o}der path of length
$2n$ with no peak at odd height. First interchange peaks and level
steps. We will call this the \textit{toggle}. We now have a
Schr\"{o}der path with no level steps at even height. Next eliminate
the first step ($U$) and the last step ($D$), and denote the
remaining path by $\omega'$. Thus, $\omega'$ is a Schr\"{o}der path
except that it can go down to height $-1$. We call this step
\textit{push down}. At this point we have no level steps at odd
height. We define the bijection $\phi$ as follows. Traverse
$\omega'$ from left to right two steps at a time where $L$ is
regarded as two steps:
\begin{itemize}
\item for consecutive $UU$ (resp. $DD$) steps, set $\phi(UU)=
u$ (resp. $\phi(DD)=d$);
\item set $\phi(L)=l$;
\item set $\phi(UD)=\wedge$;
\item set $\phi(DU)=v$.
\end{itemize}

It is easy to see that we have obtained a $3$-Motzkin path and also
that the mapping can be easily reversed. More precisely, a
Schr\"{o}der path of length $2n$ without peaks at odd height
corresponds to a $3$-Motzkin path of length $n-1$.
\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{3.6mm}
\begin{picture}(35,20)
\put(5,0){\circle*{0.1}}\put(5,0){\line(1,-1){0.1}}\put(1.8,0){$(0,0)$}
\put(5.1,-0.1){\line(1,1){0.2}}\put(5.3,0.1){\line(1,-1){0.2}}
\put(5.5,-0.1){\line(1,1){0.2}}\put(5.7,0.1){\line(1,-1){0.2}}
\put(5.9,-0.1){\line(1,1){0.1}}\put(6,0){\circle*{0.1}}\qbezier[5](6,0)(6.5,0)(7,0)
\put(7,0){\circle*{0.1}}\put(7,0){\line(1,1){1}}\put(8,1){\circle*{0.1}}
\put(8,1){\line(1,0){1}}\put(9,1){\circle*{0.1}}\put(9,1){\line(1,-1){0.1}}
\put(9.1,0.9){\line(1,1){0.2}}\put(9.3,1.1){\line(1,-1){0.2}}
\put(9.5,0.9){\line(1,1){0.2}}\put(9.7,1.1){\line(1,-1){0.2}}
\put(9.9,0.9){\line(1,1){0.1}}\put(10,1){\circle*{0.1}}
\put(10,1){\line(1,-1){0.1}}
\put(10.1,0.9){\line(1,1){0.2}}\put(10.3,1.1){\line(1,-1){0.2}}
\put(10.5,0.9){\line(1,1){0.2}}\put(10.7,1.1){\line(1,-1){0.2}}
\put(10.9,0.9){\line(1,1){0.1}}\put(11,1){\circle*{0.1}}
\put(11,1){\line(1,-1){0.1}}
\put(11.1,0.9){\line(1,1){0.2}}\put(11.3,1.1){\line(1,-1){0.2}}
\put(11.5,0.9){\line(1,1){0.2}}\put(11.7,1.1){\line(1,-1){0.2}}
\put(11.9,0.9){\line(1,1){0.1}}\put(12,1){\circle*{0.1}}
\put(12,1){\line(1,0){1}}\put(13,1){\circle*{0.1}}\put(13,1){\line(1,-1){1}}
\put(14,0){\circle*{0.1}}\put(14,0){\line(1,0){1}}\put(15,0){\circle*{0.1}}
\qbezier[5](15,0)(15.5,0)(16,0)\put(16,0){\circle*{0.1}}\put(16,0){\line(1,0){1}}
\put(17,0){\circle*{0.1}}\put(17,0){\line(1,0){1}}\put(18,0){\circle*{0.1}}
\put(18,0){\line(1,-1){0.1}}\put(18.1,-0.1){\line(1,1){0.2}}\put(18.3,0.1){\line(1,-1){0.2}}
\put(18.5,-0.1){\line(1,1){0.2}}\put(18.7,0.1){\line(1,-1){0.2}}\put(18.9,-0.1){\line(1,1){0.1}}
\put(19,0){\circle*{0.1}}\put(19,0){\line(1,1){1}}\put(20,1){\circle*{0.1}}
\qbezier[5](20,1)(20.5,1)(21,1)\put(21,1){\circle*{0.1}}\qbezier[5](21,1)(21.5,1)(22,1)
\put(22,1){\circle*{0.1}}\put(22,1){\line(1,-1){0.1}}\put(22.1,0.9){\line(1,1){0.2}}
\put(22.3,1.1){\line(1,-1){0.2}}\put(22.5,0.9){\line(1,1){0.2}}\put(22.7,1.1){\line(1,-1){0.2}}
\put(22.9,0.9){\line(1,1){0.1}}\put(23,1){\circle*{0.1}}\put(23,1){\line(1,-1){1}}
\put(24,0){\circle*{0.1}}\put(24.5,0){$(19,0)$}

\put(8,-1.5){We get a $3$-Motzkin path from $(0,0)$ to $(19,0)$}
\put(13,-2.5){with}\put(16,-2.5){$v
:=$}\put(18.3,-2.3){\circle*{0.1}}\put(18.3,-2.3){\line(1,-1){0.1}}
\put(18.4,-2.4){\line(1,1){0.2}}\put(18.6,-2.2){\line(1,-1){0.2}}
\put(18.8,-2.4){\line(1,1){0.2}}\put(19,-2.2){\line(1,-1){0.2}}
\put(19.2,-2.4){\line(1,1){0.1}}\put(19.3,-2.3){\circle*{0.1}}
\put(15.85,-3.5){$\wedge
:=$}\put(18.3,-3.2){\circle*{0.1}}\put(18.3,-3.2){\line(1,0){1}}
\put(19.3,-3.2){\circle*{0.1}} \put(16,-4.5){$l\:
:=$}\put(18.3,-4.2){\circle*{0.1}}\put(19.3,-4.2){\circle*{0.1}}
\qbezier[5](18.3,-4.2)(18.8,-4.2)(19.3,-4.2)


\put(16.5,4){$L\:\longleftrightarrow l$} \put(13,5){peak\;
$(UD)\longleftrightarrow \wedge$}\put(13,6){valley
$(DU)\longleftrightarrow v$}\put(-1,8.5){$(0,0)$}
\put(0,8){\circle*{0.1}}\put(0,8){\line(1,-1){1}}\put(1,7){\circle*{0.1}}
\put(1,7){\line(1,1){1}}\put(2,8){\circle*{0.1}}\put(2,8){\line(1,0){1}}
\put(3,8){\circle*{0.1}}\put(3,8){\line(1,1){3}}\put(4,9){\circle*{0.1}}
\put(5,10){\circle*{0.1}}\put(6,11){\circle*{0.1}}\put(6,11){\line(1,-1){2}}
\put(7,10){\circle*{0.1}}\put(8,9){\circle*{0.1}}\put(8,9){\line(1,1){1}}
\put(9,10){\circle*{0.1}}\put(9,10){\line(1,-1){1}}\put(10,9){\circle*{0.1}}
\put(10,9){\line(1,1){1}}\put(11,10){\circle*{0.1}}\put(11,10){\line(1,-1){1}}
\put(12,9){\circle*{0.1}}\put(12,9){\line(1,1){2}}\put(13,10){\circle*{0.1}}
\put(14,11){\circle*{0.1}}\put(14,11){\line(1,-1){3}}\put(15,10){\circle*{0.1}}
\put(16,9){\circle*{0.1}}\put(17,8){\circle*{0.1}}\put(17,8){\line(1,1){1}}
\put(18,9){\circle*{0.1}}\put(18,9){\line(1,-1){1}}\put(19,8){\circle*{0.1}}
\put(19,8){\line(1,0){1}}\put(20,8){\circle*{0.1}}\put(20,8){\line(1,1){1}}
\put(21,9){\circle*{0.1}}\put(21,9){\line(1,-1){1}}\put(22,8){\circle*{0.1}}
\put(22,8){\line(1,1){1}}\put(23,9){\circle*{0.1}}\put(23,9){\line(1,-1){2}}
\put(24,8){\circle*{0.1}}\put(25,7){\circle*{0.1}}\put(25,7){\line(1,1){3}}
\put(26,8){\circle*{0.1}}\put(27,9){\circle*{0.1}}\put(28,10){\circle*{0.1}}
\put(28,10){\line(1,0){2}}\put(29,10){\circle*{0.1}}\put(30,10){\circle*{0.1}}
\put(30,10){\line(1,-1){1}}\put(31,9){\circle*{0.1}}\put(31,9){\line(1,1){1}}
\put(32,10){\circle*{0.1}}\put(32,10){\line(1,-1){2}}\put(33,9){\circle*{0,1}}
\put(34,8){\circle*{0.1}}\put(33,7){$(38,0)$}

\put(8,13.3){Start with a Schr\"{o}der path from $(0,0)$ to
$(40,0)$}\put(9,12.3){and do the toggle and push down steps}

\put(1,15){\circle*{0.1}}\put(1,15){\line(1,0){1}}\put(-1,15.5){$(0,0)$}
\put(2,15){\line(1,1){2}}\put(2,15){\circle*{0.1}}\put(3,16){\circle*{0.1}}
\put(4,17){\circle*{0.1}}\put(4,17){\line(1,-1){1}}\put(5,16){\circle*{0.1}}
\put(5,16){\line(1,1){2}}\put(6,17){\circle*{0.1}}\put(7,18){\circle*{0.1}}
\put(7,18){\line(1,0){1}}\put(8,18){\circle*{0.1}}\put(8,18){\line(1,-1){1}}
\put(9,17){\circle*{0.1}}\put(9,17){\line(1,0){2}}\put(10,17){\circle*{0.1}}
\put(11,17){\circle*{0.1}}\put(11,17){\line(1,1){1}}\put(12,18){\circle*{0.1}}
\put(12,18){\line(1,0){1}}\put(13,18){\circle*{0.1}}\put(13,18){\line(1,-1){2}}
\put(14,17){\circle*{0.1}}\put(15,16){\circle*{0.1}}\put(15,16){\line(1,0){1}}
\put(16,16){\circle*{0.1}}\put(16,16){\line(1,1){1}}\put(17,17){\circle*{0.1}}
\put(17,17){\line(1,-1){1}}\put(18,16){\circle*{0.1}}\put(18,16){\line(1,0){2}}
\put(19,16){\circle*{0.1}}\put(20,16){\circle*{0.1}}\put(20,16){\line(1,-1){1}}
\put(21,15){\circle*{0.1}}\put(21,15){\line(1,1){4}}\put(22,16){\circle*{0.1}}
\put(23,17){\circle*{0.1}}\put(24,18){\circle*{0.1}}\put(25,19){\circle*{0.1}}
\put(25,19){\line(1,-1){1}}\put(26,18){\circle*{0.1}}\put(26,18){\line(1,1){1}}
\put(27,19){\circle*{0.1}}\put(27,19){\line(1,-1){2}}\put(28,18){\circle*{0.1}}
\put(29,17){\circle*{0.1}}\put(29,17){\line(1,0){1}}\put(30,17){\circle*{0.1}}
\put(30,17){\circle*{0.1}}\put(30,17){\line(1,-1){2}}\put(31,16){\circle*{0.1}}
\put(32,15){\circle*{0.1}}\put(32.3,15){$(40,0)$}
\end{picture}
\end{center}
\vspace{13mm}\caption{The bijection $\phi$} \label{F2}
\end{figure} For an example,
see Figure \ref{F2}.

\begin{table}[tp]
\begin{tabular}{c|c}
Schr\"{o}der paths  & $3$-Motzkin paths \\
(with no peaks at odd height) & \\
\hline

$L$ steps at height $0$ & $vv$ consecutive  steps at height $0$ \\
&or\\ & a $v$ at either end of the path\\ \\ $L$ steps at even
height $2k$ ($k\geq 1$) & $uv$, $vd$, $vv$, $ud$ consecutive steps
\\ &where either $u$ or $v$ is at height $k-1$ ($k\geq 1$)
\\ \\ $L$ steps at odd height & $\wedge$ steps\\  \\
peaks   & $l$ steps \\ \\ $UU$ or $UL$ & $u$ steps \\
where the first $U$ is at odd
height & \\ \\ $DD$ or $LD$ & $d$ steps \\
where the second $D$ is at odd height
\end{tabular}
\caption{Bijective correspondences.} \label{T1}
\end{table}

\textbf{Bijective correspondences.} Table \ref{T1} lists features
carried by the bijection $\phi$ from Schr\"{o}der paths to
$3$-Motzkin paths. For instance, a level step at height $0$ becomes
a peak at height $1$ after the toggle. After the push down we have a
peak at height $0$. Counting two steps at a time splits the peak
into parts of two consecutive valleys. If the original level step is
at either end of the Schr\"{o}der path then half of it would be
taken by the push down and the other half would contribute to one
valley.

The other cases follow by similar reasoning.



\section{Special Cases}
Recall that $2$-Motzkin paths are counted by the Catalan numbers,
$C_{n+1}$. If we allow no level steps at height $0$, we have the
Fine numbers. Similarly we get Motzkin paths by allowing just one
kind of level step. If we then forbid level steps at height $0$, we
obtain the Riordan paths. Thus applying the $\phi^{-1}$ algorithm
will carry all these variations simultaneously.

As one example, we consider the case where the level steps for the
$2$-Motzkin paths are labeled $l$ and $v$. Starting to apply
$\phi^{-1}$ gives us the building blocks $UU$, $L$, $DU$ and $DD$
with the Catalan condition that the number of $DD$s never exceeds
the number of $UU$s. We now have $L$ steps possible at even height,
peaks at even height. At this stage, the paths could go as low as
the line $y = -1$.

We add a single $U$ step at the beginning, a $D$ step at the end
(the \textit{push up}) and we now have Schr\"{o}der paths with level
steps and peaks only at odd height. These are counted by the Catalan
number, $C_n$. If we complete the $\phi^{-1}$ algorithm by
interchanging level steps and peaks (the \textit{toggle}), we again
have peaks and level steps allowed only at even height. The $5$ such
(Catalan) Schr\"{o}der paths from $(0,0)$ to $(6,0)$ are in Figure
\ref{F3}.


\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{3.8mm}
\begin{picture}(40,8)
\put(0,0){\line(1,1){2}}\put(0,0){\circle*{0.1}}\put(1,1){\circle*{0.1}}
\put(2,2){\circle*{0.1}}\put(2,2){\line(1,0){2}}\put(4,2){\circle*{0.1}}
\put(4,2){\line(1,-1){2}}\put(5,1){\circle*{0.1}}\put(6,0){\circle*{0.1}}
\put(8,0){\circle*{0.1}}\put(8,0){\line(1,1){2}}\put(9,1){\circle*{0.1}}
\put(10,2){\circle*{0.1}}\put(10,2){\line(1,-1){1}}\put(11,1){\circle*{0.1}}
\put(11,1){\line(1,1){1}}\put(12,2){\circle*{0.1}}\put(12,2){\line(1,-1){2}}
\put(13,1){\circle*{0.1}}\put(14,0){\circle*{0.1}}\put(16,0){\line(1,0){6}}
\put(16,0){\circle*{0.1}}\put(18,0){\circle*{0.1}}\put(20,0){\circle*{0.1}}
\put(22,0){\circle*{0.1}}\put(24,0){\circle*{0.1}}\put(24,0){\line(1,1){2}}
\put(25,1){\circle*{0.1}}\put(26,2){\circle*{0.1}}\put(26,2){\line(1,-1){2}}
\put(27,1){\circle*{0.1}}\put(28,0){\circle*{0.1}}\put(28,0){\line(1,0){2}}
\put(30,0){\circle*{0.1}}\put(32,0){\circle*{0.1}}\put(32,0){\line(1,0){2}}
\put(34,0){\circle*{0.1}}\put(34,0){\line(1,1){2}}\put(35,1){\circle*{0.1}}
\put(36,2){\circle*{0.1}}\put(36,2){\line(1,-1){2}}\put(37,1){\circle*{0.1}}
\put(38,0){\circle*{0.1}}

\put(18,3){\line(0,0){2}}\put(18,3){\line(-1,1){0.4}}\put(18,3){\line(1,1){0.4}}
\put(19,4){\textit{toggle}}

\put(0,6){\line(1,1){3}}\put(0,6){\circle*{0.1}}\put(1,7){\circle*{0.1}}
\put(2,8){\circle*{0.1}}\put(3,9){\circle*{0.1}}\put(3,9){\line(1,-1){3}}
\put(4,8){\circle*{0.1}}\put(5,7){\circle*{0.1}}\put(6,6){\circle*{0.1}}
\put(8,6){\circle*{0.1}}\put(8,6){\line(1,1){1}}\put(9,7){\circle*{0.1}}
\put(9,7){\line(1,0){4}}\put(11,7){\circle*{0.1}}\put(13,7){\circle*{0.1}}
\put(13,7){\line(1,-1){1}}\put(14,6){\circle*{0.1}}\put(16,6){\circle*{0.1}}
\put(16,6){\line(1,1){1}}\put(17,7){\circle*{0.1}}\put(17,7){\line(1,-1){1}}
\put(18,6){\circle*{0.1}}\put(18,6){\line(1,1){1}}\put(19,7){\circle*{0.1}}
\put(19,7){\line(1,-1){1}}\put(20,6){\circle*{0.1}}\put(20,6){\line(1,1){1}}
\put(21,7){\circle*{0.1}}\put(21,7){\line(1,-1){1}}\put(22,6){\circle*{0.1}}
\put(24,6){\circle*{0.1}}\put(24,6){\line(1,1){1}}\put(25,7){\circle*{0.1}}
\put(25,7){\line(1,0){2}}\put(27,7){\circle*{0.1}}\put(27,7){\line(1,-1){1}}
\put(28,6){\circle*{0.1}}\put(28,6){\line(1,1){1}}\put(29,7){\circle*{0.1}}
\put(29,7){\line(1,-1){1}}\put(30,6){\circle*{0.1}}\put(32,6){\circle*{0.1}}
\put(32,6){\line(1,1){1}}\put(33,7){\circle*{0.1}}\put(33,7){\line(1,-1){1}}
\put(34,6){\circle*{0.1}}\put(34,6){\line(1,1){1}}\put(35,7){\circle*{0.1}}
\put(35,7){\line(1,0){2}}\put(37,7){\line(1,-1){1}}\put(37,7){\circle*{0.1}}
\put(38,6){\circle*{0.1}}

\end{picture}
\end{center}
\caption{(Catalan) Schr\"{o}der paths of length $6$.}\label{F3}
\end{figure}

If we also prohibit $L$ steps at height $0$, we get the Fine
numbers, $1,0,1,2,6,18,57,\ldots$. The $6$ (Fine) Schr\"{o}der paths
from $(0,0)$ to $(8,0)$ without toggle and push up steps are shown
in Figure \ref{F5}. After the toggle and the push up, we have the
elevated Schr\"{o}der paths with level steps at height $2k$ ($k\geq
1$) and peaks at height $2k$ ($k\geq 2$).

\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{2.7mm}
\begin{picture}(80,4)
\put(0,0){\circle*{0.1}}\put(0,0){\line(1,1){4}}\put(1,1){\circle*{0.1}}
\put(2,2){\circle*{0.1}}\put(3,3){\circle*{0.1}}\put(4,4){\circle*{0.1}}
\put(4,4){\line(1,-1){4}}\put(5,3){\circle*{0.1}}\put(6,2){\circle*{0.1}}
\put(7,1){\circle*{0.1}}\put(8,0){\circle*{0.1}}\put(10,0){\circle*{0.1}}
\put(10,0){\line(1,1){2}}\put(11,1){\circle*{0.1}}\put(12,2){\circle*{0.1}}
\put(12,2){\line(1,0){2}}\put(14,2){\circle*{0.1}}\put(14,2){\line(1,-1){1}}
\put(15,1){\circle*{0.1}}\put(15,1){\line(1,1){1}}\put(16,2){\circle*{0.1}}
\put(16,2){\line(1,-1){2}}\put(17,1){\circle*{0.1}}\put(18,0){\circle*{0.1}}
\put(20,0){\circle*{0.1}}\put(20,0){\line(1,1){2}}\put(21,1){\circle*{0.1}}
\put(22,2){\circle*{0.1}}\put(22,2){\line(1,-1){1}}\put(23,1){\circle*{0.1}}
\put(23,1){\line(1,1){1}}\put(24,2){\circle*{0.1}}\put(24,2){\line(1,0){2}}
\put(26,2){\circle*{0.1}}\put(26,2){\circle*{0.1}}\put(26,2){\line(1,-1){2}}
\put(27,1){\circle*{0.1}}\put(28,0){\circle*{0.1}}\put(30,0){\circle*{0.1}}
\put(30,0){\line(1,1){2}}\put(31,1){\circle*{0.1}}\put(32,2){\circle*{0.1}}
\put(32,2){\line(1,0){4}}\put(34,2){\circle*{0.1}}\put(36,2){\circle*{0.1}}
\put(36,2){\line(1,-1){2}}\put(37,1){\circle*{0.1}}\put(38,0){\circle*{0.1}}
\put(40,0){\circle*{0.1}}\put(40,0){\line(1,1){2}}\put(41,1){\circle*{0.1}}
\put(42,2){\circle*{0.1}}\put(42,2){\line(1,-1){1}}\put(43,1){\circle*{0.1}}
\put(43,1){\line(1,1){1}}\put(44,2){\circle*{0.1}}\put(44,2){\line(1,-1){1}}
\put(45,1){\circle*{0.1}}\put(45,1){\line(1,1){1}}\put(46,2){\circle*{0.1}}
\put(46,2){\line(1,-1){2}}\put(47,1){\circle*{0.1}}\put(48,0){\circle*{0.1}}
\put(50,0){\circle*{0.1}}\put(50,0){\line(1,1){2}}\put(51,1){\circle*{0.1}}
\put(52,2){\circle*{0.1}}\put(52,2){\line(1,-1){2}}\put(53,1){\circle*{0.1}}
\put(54,0){\circle*{0.1}}\put(54,0){\line(1,1){2}}\put(55,1){\circle*{0.1}}
\put(56,2){\circle*{0.1}}\put(56,2){\line(1,-1){2}}\put(57,1){\circle*{0.1}}
\put(58,0){\circle*{0.1}}
\end{picture}
\end{center}
\caption{(Fine) Schr\"{o}der paths of length $8$.}\label{F5}
\end{figure}

To obtain one of the settings for the Motzkin numbers, we eliminate
$l$ also. This gives us Schr\"{o}der paths without level steps and
peaks only at odd height. If we interchange peaks and level steps we
get Schr\"{o}der paths with no peaks, and level steps only at even
height. Here in Figure \ref{F7} are the four (Motzkin) Schr\"{o}der
paths from $(0,0)$ to $(8,0)$.

\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{4mm}
\begin{picture}(38,9)

\put(0,6){\circle*{0.1}}\put(0,6){\line(1,1){1}}\put(1,7){\circle*{0.1}}
\put(1,7){\line(1,-1){1}}\put(2,6){\circle*{0.1}}\put(2,6){\line(1,1){1}}
\put(3,7){\circle*{0.1}}\put(3,7){\line(1,-1){1}}\put(4,6){\circle*{0.1}}
\put(4,6){\line(1,1){1}}\put(5,7){\circle*{0.1}}\put(5,7){\line(1,-1){1}}
\put(6,6){\circle*{0.1}}\put(6,6){\line(1,1){1}}\put(7,7){\circle*{0.1}}
\put(7,7){\line(1,-1){1}}\put(8,6){\circle*{0.1}}\put(10,6){\circle*{0.1}}
\put(10,6){\line(1,1){1}}\put(11,7){\circle*{0.1}}\put(11,7){\line(1,-1){1}}
\put(12,6){\circle*{0.1}}\put(12,6){\line(1,1){3}}\put(13,7){\circle*{0.1}}
\put(14,8){\circle*{0.1}}\put(15,9){\circle*{0.1}}\put(15,9){\line(1,-1){3}}
\put(16,8){\circle*{0.1}}\put(17,7){\circle*{0.1}}\put(18,6){\circle*{0.1}}
\put(20,6){\circle*{0.1}}\put(20,6){\line(1,1){3}}\put(21,7){\circle*{0.1}}
\put(22,8){\circle*{0.1}}\put(23,9){\circle*{0.1}}\put(23,9){\line(1,-1){3}}
\put(24,8){\circle*{0.1}}\put(25,7){\circle*{0.1}}\put(26,6){\circle*{0.1}}
\put(26,6){\line(1,1){1}}\put(27,7){\circle*{0.1}}\put(27,7){\line(1,-1){1}}
\put(28,6){\circle*{0.1}}\put(30,6){\circle*{0.1}}\put(30,6){\line(1,1){3}}
\put(31,7){\circle*{0.1}}\put(32,8){\circle*{0.1}}\put(33,9){\circle*{0.1}}
\put(33,9){\line(1,-1){1}}\put(34,8){\circle*{0.1}}\put(34,8){\line(1,1){1}}
\put(35,9){\circle*{0.1}}\put(35,9){\line(1,-1){3}}\put(36,8){\circle*{0.1}}
\put(37,7){\circle*{0.1}}\put(38,6){\circle*{0.1}}

\put(17,3){\line(0,1){2}}\put(17,3){\line(-1,1){0.3}}\put(17,3){\line(1,1){0.3}}
\put(17.5,3.7){\textit{toggle}}

\put(0,0){\line(1,0){8}}\put(0,0){\circle*{0.1}}\put(2,0){\circle*{0.1}}
\put(4,0){\circle*{0.1}}\put(6,0){\circle*{0.1}}\put(8,0){\circle*{0.1}}
\put(10,0){\circle*{0.1}}\put(10,0){\line(1,0){2}}\put(12,0){\circle*{0.1}}
\put(12,0){\line(1,1){2}}\put(13,1){\circle*{0.1}}\put(14,2){\circle*{0.1}}
\put(14,2){\line(1,0){2}}\put(16,2){\circle*{0.1}}\put(16,2){\line(1,-1){2}}
\put(17,1){\circle*{0.1}}\put(18,0){\circle*{0.1}}\put(20,0){\circle*{0.1}}
\put(20,0){\line(1,1){2}}\put(21,1){\circle*{0.1}}\put(22,2){\circle*{0.1}}
\put(22,2){\line(1,0){2}}\put(24,2){\circle*{0.1}}\put(24,2){\line(1,-1){2}}
\put(25,1){\circle*{0.1}}\put(26,0){\circle*{0.1}}\put(26,0){\line(1,0){2}}
\put(28,0){\circle*{0.1}}\put(30,0){\circle*{0.1}}\put(30,0){\line(1,1){2}}
\put(31,1){\circle*{0.1}}\put(32,2){\circle*{0.1}}\put(32,2){\line(1,0){4}}
\put(34,2){\circle*{0.1}}\put(36,2){\circle*{0.1}}\put(36,2){\line(1,-1){2}}
\put(37,1){\circle*{0.1}}\put(38,0){\circle*{0.1}}
\end{picture}
\end{center}
\caption{(Motzkin) Schr\"{o}der paths of length $8$.}\label{F7}
\end{figure}

In these last two settings we can eliminate peaks at height $1$
(respectively, level steps at height $0$). For paths from $(0,0)$ to
$(10,0)$, we get three (Riordan) Schr\"{o}der paths. We show these
in Figure \ref{F8} with and without the toggle.

\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{3.5mm}
\begin{picture}(35,11)
\put(0,0){\circle*{0.1}}
\put(0,0){\line(1,1){2}}\put(1,1){\circle*{0.1}}\put(2,2){\circle*{0.1}}
\put(2,2){\line(1,0){6}}\put(4,2){\circle*{0.1}}\put(6,2){\circle*{0.1}}
\put(8,2){\circle*{0.1}}\put(8,2){\line(1,-1){2}}\put(9,1){\circle*{0.1}}
\put(10,0){\circle*{0.1}}\put(12,0){\circle*{0.1}}\put(12,0){\line(1,1){2}}
\put(13,1){\circle*{0.1}}\put(14,2){\circle*{0.1}}\put(14,2){\line(1,0){2}}
\put(16,2){\circle*{0.1}}\put(16,2){\line(1,-1){1}}\put(17,1){\circle*{0.1}}
\put(17,1){\line(1,1){1}}\put(18,2){\circle*{0.1}}\put(18,2){\line(1,0){2}}
\put(20,2){\circle*{0.1}}\put(20,2){\line(1,-1){2}}\put(21,1){\circle*{0.1}}
\put(22,0){\circle*{0.1}}\put(24,0){\circle*{0.1}}\put(24,0){\line(1,1){4}}
\put(25,1){\circle*{0.1}}\put(26,2){\circle*{0.1}}\put(27,3){\circle*{0.1}}
\put(28,4){\circle*{0.1}}\put(28,4){\line(1,0){2}}\put(30,4){\circle*{0.1}}
\put(30,4){\line(1,-1){4}}\put(31,3){\circle*{0.1}}\put(32,2){\circle*{0.1}}
\put(33,1){\circle*{0.1}}\put(34,0){\circle*{0.1}}

\put(0,7){\circle*{0.1}}\put(0,7){\line(1,1){3}}\put(1,8){\circle*{0.1}}
\put(2,9){\circle*{0.1}}\put(3,10){\circle*{0.1}}\put(3,10){\line(1,-1){1}}
\put(4,9){\circle*{0.1}}\put(4,9){\line(1,1){1}}\put(5,10){\circle*{0.1}}
\put(5,10){\line(1,-1){1}}\put(6,9){\circle*{0.1}}\put(6,9){\line(1,1){1}}
\put(7,10){\circle*{0.1}}\put(7,10){\line(1,-1){3}}\put(8,9){\circle*{0.1}}
\put(9,8){\circle*{0.1}}\put(10,7){\circle*{0.1}}\put(12,7){\circle*{0.1}}
\put(12,7){\line(1,1){3}}\put(13,8){\circle*{0.1}}\put(14,9){\circle*{0.1}}

\put(15,10){\circle*{0.1}}\put(15,10){\line(1,-1){2}}\put(16,9){\circle*{0.1}}
\put(17,8){\circle*{0.1}}\put(17,8){\line(1,1){2}}\put(18,9){\circle*{0.1}}
\put(19,10){\circle*{0.1}}\put(19,10){\line(1,-1){3}}\put(20,9){\circle*{0.1}}
\put(21,8){\circle*{0.1}}\put(22,7){\circle*{0.1}}\put(24,7){\circle*{0.1}}
\put(24,7){\line(1,1){5}}\put(25,8){\circle*{0.1}}\put(26,9){\circle*{0.1}}
\put(27,10){\circle*{0.1}}\put(28,11){\circle*{0.1}}\put(29,12){\circle*{0.1}}
\put(29,12){\line(1,-1){5}}\put(30,11){\circle*{0.1}}\put(31,10){\circle*{0.1}}
\put(32,9){\circle*{0.1}}\put(33,8){\circle*{0.1}}\put(34,7){\circle*{0.1}}

\put(15,4){\line(0,1){2.5}}\put(15,4){\line(-1,1){0.3}}
\put(15,4){\line(1,1){0.3}}\put(15.5,5){\textit{toggle}}
\end{picture}
\end{center}
\caption{(Riordan) Schr\"{o}der paths of length $10$.}\label{F8}
\end{figure}


\subsection{Remarks}
\quad \: We now list some of the other possibilities. We have
${{3}\choose{2}}$ ways to choose $2$ of $3$ kinds of level steps
each leading to a Catalan setting and with it a Fine setting. By
then eliminating one of the two kinds of level steps, we obtain two
settings for the Motzkin numbers and then Riordan numbers. By not
using the toggle, we double the numbers of possibilities. When the
$v$ step is not one of the level steps, we can eliminate the push
down-push up steps. Since we proceed two steps  at a time this also
yields new settings.

The complete $\phi^{-1}$ algorithm consists of both the push up and
toggle steps. As fascinating as each setting is individually, the
list gets quite long quite quickly.

\subsection{Catalan numbers}
\quad \:We call a path is elevated if the path is strictly above the
$x$-axis except the initial and end points.

If the level steps for the $2$-Motzkin paths are labeled $\wedge$
and $l$, then by the complete $\phi^{-1}$ algorithm, we have the
elevated Schr\"{o}der paths with no peaks at odd height, no valley
at even height and each $L$ at even height occurring as part of a
$ULD$ subsequence.

If the level steps are either $\wedge$ or $v$, then the complete
$\phi^{-1}$ algorithm will give us the Schr\"{o}der paths with no
peaks.

Eliminating all the level steps from $3$-Motzkin paths, we have Dyck
paths, which are counted by aerated Catalan numbers, whose first
several terms are $1,0,1,0,2,0,5,0,\ldots$. By the complete
$\phi^{-1}$ algorithm, we have the elevated Schr\"{o}der paths with
no peaks, valleys only at odd height and level steps only at height
$2k$ ($k\geq 1$) and occurring as part of a $ULD$ subsequence.

\subsection{Motzkin numbers}
\quad \: In this section, we consider Motzkin paths, first with
$\wedge$ as the level step, then with $l$.

If the level steps of Motzkin paths are labeled $\wedge$, then the
complete $\phi^{-1}$ algorithm produces the elevated Schr\"{o}der
paths with neither valley at even height nor peaks and where each
$L$ at even height occurs as part of a $ULD$ subsequence.

If we denote the level steps in Motzkin paths by $l$ and apply the
complete inverse algorithm, then we obtain the elevated Schr\"{o}der
paths with no peaks at odd height, no valley at even height and $L$
steps only at height $2k$ ($k\geq 1$) occurring as part of $ULD$
subsequences.

\subsection{Fine numbers}
\quad \: We next consider $2$-Riordan (i.e., Fine) paths with two
kinds of level steps, $\wedge$ and $l$, allowed except at height $0$
where there are no level steps. Applying the complete $\phi^{-1}$
algorithm, we have the elevated Schr\"{o}der paths with no valley at
even height, peaks only at height $2k$ ($k\geq 2$), $L$ steps at
height $\geq 2$ and each $L$ at even height occurring as part of a
$ULD$ subsequence.

If the level steps are either $\wedge$ and $v$ and we apply the
complete $\phi^{-1}$ algorithm, we end up with elevated Schr\"{o}der
paths with no peaks and $L$ steps at height $k\geq 2$ .

Eliminating all level steps in $3$-Motzkin paths and forbidding
peaks at height $1$, we will also have the Fine numbers. By applying
the complete $\phi^{-1}$ algorithm, we have the elevated
Schr\"{o}der paths with no peaks, no valleys at even height, $L$
steps only at height $2k$ ($k\geq 2$) and occurring as part of $ULD$
subsequences.

\subsection{Riordan numbers}
\quad \: If we eliminate the level steps at height $0$ in Motzkin
paths, we have the Riordan paths.

If the level steps in Riordan paths are $v$'s, then by the complete
$\phi^{-1}$ algorithm, we have elevated Schr\"{o}der paths with no
peaks and $L$ steps at height $2k$ ($k\geq 1$).

If the level steps are all labeled $\wedge$, then the complete
$\phi^{-1}$ algorithm leads to the elevated Schr\"{o}der paths with
no peaks, no valleys at even height, level steps at height $\geq 2$
and level steps at even height occurring as part of $ULD$
subsequences.

If we consider the case where level steps are $l$'s and apply the
complete $\phi^{-1}$ algorithm, then we have the elevated
Schr\"{o}der paths with peaks only at even height $\geq 4$, no
valley at even height, level steps only at height $2k$ ($k\geq 1$)
and occurring as part of $ULD$ subsequences.

Some results, similar to ours, but not in a Schr\"{o}der context
appear in a recent paper of Eu, Liu and Yeh \cite{Yeh}.


\section{Acknowledgments}
This work was supported by the 973 Project, the PCSIRT Project of
the Ministry of Education, the Ministry of Science an Technology,
and the National Science Foundation of China. The first author was
also supported by the NSF grant HRD 0401697.

\begin{thebibliography}{99}

\bibitem{CCBB} S. J. Cyvin, B. N. Cyvin, J. Brunvoll, and E. Brendsdal,
Enumeration and classification of certain polygonal systems
representing polycyclic conjugated hydrocarbons: annelated
catafusenes, \textit{J. Chem. Inf. Comput. Sci.} \textbf{34} (1994),
1174--1180.

\bibitem{DS99} E. Deutsch and 
L. Shapiro, A survey of the Fine numbers, \textit{%
Discrete Math.} \textbf{204} (1999), 167--202.

\bibitem{DS01} E. Deutsch and
L. Shapiro, Seventeen Catalan identities, \textit{%
Bulletin of the ICA} \textbf{31} (2001), 31--38.

\bibitem{DS02} E. Deutsch and L. Shapiro, A bijection between ordered trees
and $2$-Motzkin paths and its many consequences, \textit{Discrete
Math.} \textbf{256} (2002), 655--670.

\bibitem{Yeh} S. Eu, S. Liu, and Y. N. Yeh, Dyck paths with peaks
avoiding or restricted to a given set, \textit{Studies in App.
Math.} \textbf{111} (2003), 453--465.

\bibitem{HR} F. Harary and R. C. Read, The enumeration of tree-like
polyhexes, \textit{Proc. Edinb. Math. Soc.} \textbf{17} (1970),
1--13.

\bibitem{MSS} T. Mansour, M. Schork and Y. Sun, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Schork/schork3.html}{Motzkin
numbers of higher rank: generating function}\\\
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Schork/schork3.html}{and
explicit expression}, \textit{J. Integer Seq.} {\bf 10} (2007),
Article 07.7.4.

\bibitem{EIS} N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer
Sequences, Academic Press, San Diego, 1995. Also on-line at
\href{http://www.research.att.com/~njas/sequences/}{The On-Line
Encyclopedia of Integer Sequences},
\href{http://www.research.att.com/~njas/sequences/}{http://www.research.att.com/$^{\sim}$njas/sequences/index.html}.

\bibitem{ST2}
R. P. Stanley, \textit{Enumerative Combinatorics}, Vol. \textbf{2},
Chapter $6$, Cambridge Uiversity Press, 1999, and see also
website:\newline http://www-math.mit.edu/$\sim$rstan/ec, the
\textit{Catalan Addendum}.

\bibitem{Yan}
S. H. F. Yan,
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Yan/yan7.html
}{From $(2,3)$-Motzkin paths to Schr\"{o}der Paths}, {\it J. Integer
Seq.} {\bf 10} (2007), Article 07.9.1.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 05A05,
05A15, 05A19.

\noindent \emph{Keywords: } $3$-Motzkin paths, Schr\"{o}der paths,
$2$-Motzkin paths, Motzkin paths, Dyck paths, Fine paths, Riordan
paths, Catalan numbers.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000108},
\seqnum{A000957}, \seqnum{A001006}, \seqnum{A002212},
\seqnum{A005043}, \seqnum{A006318}, \seqnum{A097331},
\seqnum{A117641}.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 2 2008;
revised version received February 21 2009.
Published in {\it Journal of Integer Sequences}, March 14 2009.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

.