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