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

\usepackage{graphicx,amsthm,epsfig}
\usepackage{epstopdf}

\newtheorem{defn}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem*{lem}{Lemma}
\newcommand {\Z}{\mathbb{Z}}
\newcommand {\I}{\mathcal{I}}
\newcommand {\R}{\mathcal{R}}

\newcommand {\pred}{\mbox{pred}}
\newcommand {\suc}{\mbox{succ}}

\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 Semiorders and Riordan Numbers
}
\vskip 1cm
\large
Barry Balof and Jacob Menashe\\
Department of Mathematics \\
Whitman College \\
Walla Walla, WA  99362\\
USA \\
\href{mailto:balofba@whitman.edu}{\tt balofba@whitman.edu}\\
\href{mailto:menashjv@whitman.edu}{\tt menashjv@whitman.edu} \\
\end{center}

\vskip .2 in



\begin{abstract}
In this paper, we define a class of semiorders (or unit interval
orders) that arose in the context of polyhedral combinatorics.  In the
first section of the paper, we will present a pure counting argument
equating the number of these interesting (connected and irredundant)
semiorders on $n+1$ elements with the $n$th Riordan number.  In the
second section, we will make explicit the relationship between the
interesting semiorders and a special class of Motzkin paths, namely,
those Motzkin paths without horizontal steps of height 0, which are
known to be counted by the Riordan numbers.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}


\section{Counting Interesting Semiorders}

We begin with some basic definitions.  

\begin{defn}
A partially ordered set $(X, \prec)$ is a {\em semiorder} if it satisfies the following two properties for any $a, b, c, d\in X$.
\begin{itemize}
\item If $a \prec b$ and $c\prec d$, $a \prec d$ or $c\prec b$.  
\item If $a \prec b \prec c$,  then $d\prec c$ or $a \prec d$.  
\end{itemize}
\end{defn}

Semiorders are also known as {\em unit interval orders} in the
literature.  This name comes from the fact that each element $x\in X$
can be identified with an interval on the real line.  All intervals are
the same length, and two intervals intersect if and only if their
corresponding elements are incomparable.  If the intervals for $a$ and
$b$ do not intersect, and the interval for $a$ lies to the left of the
interval for $b$, then $a\prec b$.  We may assume without loss of
generality that the intervals in our representation have different
endpoints.  We define the predecessor ($\pred$) and successor ($\suc$)
sets intuitively:  $\pred(x)=\{a\in X \; | a \prec x\}$ and
$\suc(x)=\{a\in X \; | x \prec a\}$.  For a semiorder, the predecessor
and successor sets are weakly ordered (for different elements $x$ and
$y$, either $\pred(x)\subseteq \pred(y)$, $\pred(y)\subseteq \pred(x)$,
or both, with the same criterion for successor sets).  These impose two
weak orderings on the set $X$, and their intersection is a weak order
known as the {\em trace}.


A semiorder is {\em interesting} if it satisfies the following two properties.  
\begin{itemize}
\item ({\em Connectedness}) Each element is incomparable with its immediate predecessors in the trace.
\item ({\em Irredundancy}) No two elements have both the same predecessor sets and the same successor sets.
\end{itemize}

We use $\I_n$ to denote the set of all interesting semiorders on $n$ elements.  

The criterion of connectedness guarantees that the semiorder is
represented by a topologically connected set of distinct intervals on
the real line.  The criterion of irredundancy guarantees that the
semiorder has a linear order as its trace (i.e., no two elements are
incomparable in the trace).  These criteria came about from the study
of the polyhedral set of all representations of a semiorder.  This
polyhedron has one dimension for each element of the semiorder, save
for the smallest element in the trace, and one dimension for the length
of the intervals (which we denote the $r$-value).  The connectedness
criterion guarantees that the polyhedron is bounded along each
hyperplane corresponding to a fixed $r$ value (that is, if the interval
length is bounded, then so is any numeric representation of the
semiorder).  The irredundancy criterion guarantees that each dimension
will take on a different set of values for the polyhedron (that is, no
two elements may be represented by the same interval in any
representation of the semiorder).  Though the motivation comes from the
study of this polyhedron, the remainder of the paper will focus on the
properties of the semiorders and an exploration of the following
theorem.

\begin{thm}
The number of interesting semiorders on $n+1$ elements is the $n$th Riordan number, $r_n$.  That is, $|\I_n|=r_n$.  
\label{countbij}
\end{thm}

The Riordan numbers (1,0,1,1,3,6,15,36,91,...) are found at \cite{Slo}
(A005043) and explored in depth by Bernhart in \cite{Ber}.  This
theorem is an order-theoretic analog of a graph-theoretic result of
Hanlon \cite{Han}.

We prove the result by showing that the number of interesting semiorders on $n+1$ elements, which we will denote $\rho_n$, satisfies the same recurrence relation as do the Riordan numbers, namely that 
$$c_{n}=\sum_{k=0}^n {n\choose k} \rho_k \qquad \textrm{with} \qquad \rho_0=1$$
where $c_n=\frac{1}{n+1}{2n\choose n}$ is the $n$th Catalan number (sequence [A000108]).  The above recurrence for the Riordan numbers was proven in detail by Chen et. al. in \cite{Chen}.

\begin{proof}
We first check that the base case holds, namely that there is 1 interesting semiorder on 1 element ($\rho_0=1$), which is the only semiorder on one element.  

A semiorder on $n+1$ elements can be represented by an $n+1$ by $n+1$
0-1 matrix, $A$, with the rows and columns labeled by the semiorder
elements.  The entry $A_{i,j}$ is 1 if element $i$ is above element $j$
in the semiorder, and 0 otherwise.  If the labels on the rows and
columns are in accordance with the trace, then the matrix will be in
echelon form with each row beginning with a string of zeroes and ending
with a (possibly empty) string of ones.  The set of leading ones in
each row will form a `staircase' pattern, as in Figure
\ref{Fig:motzkin_example}.   We can move along the steps to obtain a
path from the upper right to the lower left corner of the matrix.
Since this path never goes below the diagonal, we have as many
semiorders on $n$ elements as we do lattice paths from $(0,0)$ to
$(n+1,n+1)$ that don't go below the line $y=x$, the number of which is
well known to be the $n+1$st Catalan number, $c_{n+1}$.

If we restrict our attention to connected semiorders, the matrix has no
non-zero entries in the sup-diagonal ($a_{i,i+1}$) or below.  Hence,
the lattice paths in question can be viewed as going from $(1,0)$ to
$(n,n+1)$ without crossing the line $y=x+1$, which are just counted by
the $n$th Catalan number, $c_n$.

Suppose that there are $\rho_k$ interesting semiorders on $k+1$
elements, and take an arbitrary connected semiorder on $n+1$ elements.
Either it is irredundant, or for some pairs of elements $x_i$ and
$x_{i+1}$ which are adjacent in the trace, $x_i$ and $x_{i+1}$ have the
same predecessor sets and successor sets.  There are $n$ such adjacent
pairs which might be `the same' in this way.  For each pair that is the
same, iteratively replace them with a single element.  If there are
$n-k$ such pairs the same, then what results is an interesting
semiorder on $n+1-(n-k)=k+1$ elements.  There are $\rho_k$ interesting
semiorders on $k+1$ elements, and hence there are ${n \choose
n-k}\rho_k={n \choose k}\rho_k$ orders on $n+1$ elements which reduce
to an interesting semiorder on $k+1$ elements.  Summing over all
possible values of $k$ gives the desired recursion.  Therefore
$\rho_n=r_n$, the $n$th Riordan number.

\end{proof}



\section{Semiorder/Motzkin Path Bijection}

It is known that the Riordan numbers count the number of Motzkin paths without horizontal steps of height zero.   In the remainder of the paper, we make explicit a bijection between semiorders and these Motzkin paths.  We begin with some more terminology about semiorders, and we follow definitions similar to those of Pirlot \cite{Pi} for two other relations on the elements of a semiorder, nose relations and hollow relations.

\subsection{Definitions and Terminology}

In terms of the matrix $A$, we have that $aNb$ if $A_{ab}=1$, and changing that 1 to a 0 leaves a staircase matrix pattern.  We have that $cHd$ if $A_{cd}=0$, and changing that 0 to a 1 leaves a staircase matrix pattern.  We make another definition in terms of predecessor and successor sets.  

\begin{defn}
The relations $N$ and $H$ are defined as follows, with $x_j \prec_T x_i$
\begin{itemize}
\item $x_i N x_j$ if $x_j \in \pred(x_i)$, $x_{j+1} \not\in \pred(x_i)$, and $x_{j}\not\in \pred(x_{i-1})$
\item $x_i H x_j$ if $x_j \not \in \textrm{pred}(x_i)$, $x_{j-1} \in \textrm{pred}(x_i)$, and $x_{j} \in \textrm{pred}(x_{i+1})$ {\footnote{The definition given here is the inverse of the relation defined in \cite{Pi}, but we use this for the ease in discussing the bijection in the remainder}}
\end{itemize}
\end{defn}
As shown in \cite{Pi}, and in explicit detail in \cite{Pi2}, the semiorder can be reconstructed in its entirety by its nose and hollow relations.      We also say that $x_i$ {\em noses} $x_j$ if $x_iNx_j$, and similarly, $x_i$ {\em hollows} $x_j$ if $x_iHx_j$. 




\begin{defn}
A {\bf Motzkin path} of order $n>0$ is a walk from the point $(0,0)$ to the point $(n,0)$ along integer lattice points, none of which lie below the $x$-axis,  consisting of three types of steps.  
\begin{itemize}
\item {\bf Up-steps} from a point $(i, j)$ to $(i+1, j+1)$
\item {\bf Horizontal steps} from a point $(i,j)$ to a point $(i+1, j)$
\item {\bf Down-steps} from a point $(i,j)$ to a point $(i+1, j-1)$.  
\end{itemize}

We denote by $P_i$ the point on the path with $x$-coordinate $i$ $(0\leq i \leq n)$ .  
\end{defn}

Motzkin paths are a generalization of the classic Catalan paths.  The
Catalan paths are often viewed as going from (0,0) to $(k,k)$, and
consisting of $k$ horizontal and $k$ vertical steps (that stay above
the `baseline' $y=x$).  By rotating 45$^\circ$ and using the described
up-steps and down-steps, a Catalan path can be viewed as  going from
$(0,0)$ to $(2k, 0)$ (and staying above the `baseline' $y=0$).  The
primary difference between Catalan and Motzkin paths is that Motzkin
paths allow for horizontal steps.  As such, we can construct such paths
from $(0,0)$ to $(n,0)$ for $n$ even or odd.  We further narrow our
focus to the set of paths that will correspond to our set of
semiorders.



\begin{defn}
A {\em{\bf Riordan path}} of order $n$ is a Motzkin path of order $n$ in which no horizontal steps occur on the horizontal axis of the plane. We will denote the set of Riordan paths of order $n$ by $\mathcal{R}_n$.
\end{defn}

We will make an explicit bijection between these Riordan paths and the
set of interesting semiorders.  We begin by closely examining the
Riordan paths.


\begin{defn}\label{Def:pttype}
Let $P_i$ represent the $i$th point in a Riordan path of order n, where $1<i<n$. There are nine possibilities for any given point $P_i$.
\begin{itemize}
\item[(i)] $P_i$ is a \bf hard peak \it if $P_i$ lies vertically above both of the points $P_{i-1}, P_{i+1}$.
\item[(ii-iii)] $P_i$ is a \bf positive (negative) soft peak \it if $P_i$ lies vertically above the point $P_{i-1}$ ($P_{i+1}$), and level with the point $P_{i+1}$ ($P_{i-1}$).
\item[(iv)] $P_i$ is a \bf hard dip \it if $P_i$ lies vertically below both of the points $P_{i-1}, P_{i+1}$.
\item[(v-vi)] $P_i$ is a \bf positive (negative) soft dip \it if $P_i$ lies vertically below the point $P_{i+1}$ ($P_{i-1}$), and level with the point $P_{i-1}$ ($P_{i+1}$).
\item[(vii-viii)] $P_i$ is a \bf positive (negative) slope \it if it lies vertically above (below) $P_{i-1}$ and vertically below (above) $P_{i+1}$.
\item[(ix)] $P_i$ is a \bf level point \it if it lies vertically level with $P_{i-1}$, $P_{i+1}$
\end{itemize}
\end{defn}

The nine types of points are shown graphically in Figure
\ref{Fig:pttype}.  Thus, each Riordan path is uniquely defined by its
list of point types.  We now define several operations on the Riordan
paths and some useful terminology associated with those operations.


\begin{figure}[htbp]
\centering
\epsfig{file=pttype.eps, width=\textwidth}
\caption{The nine possible types of points in a Riordan path.}
\label{Fig:pttype}
\end{figure}


\begin{defn}
The \bf sum \it of two Riordan paths $M_m,M_n$ of order $m,n$, respectively, is the Riordan path $M$ in which points $P_i$ for $(1\leq i<m)$ are identical to those of $M_m$, and points $P_{(m-1)+i}$ in $M$ are identical to points $P_i$ in $M_n$ for $1\leq i\leq n$. This sum is denoted $M_m+M_n$.
\end{defn}

\begin{defn}
A Riordan path $M$ is \bf splittable \it if it can be expressed as the sum of two Riordan paths of lesser order.
\end{defn}

\begin{defn}
Let $P_1,P_2,\ldots,P_n$ be the ordered set of points of $M$, where
$M\in\I_n$, and $P_i$ lies adjacently to the right of $P_{i-1}$ for
$i>1$.  The \bf reverse \it of $M$, denoted $M^r$, is the ordered set
of points $Q_n,Q_{n-1},\ldots,Q_1$ with the following property: the
steps of $M^r$ are defined by $(Q_{k-1},Q_k)=(P_{n-k+2},P_{n-k+1})$ and
$(Q_{k},Q_{k+1})=(P_{n-k},P_{n-k+1})$. Equivalently, if $P_{n-k+1}$ is
a positive (negative) soft peak or dip, then $Q_k$ is a negative
(positive) soft peak or dip. Similarly, if $P_{n-k+1}$ is positive
(negative) slope, then $Q_k$ is a negative (positive) slope. Finally,
if $P_{n-k+1}$ is either a hard peak, a hard dip, or a level point,
$Q_k$ is the same type of point. Note that this results in $M^r$
appearing graphically as the mirror image of $M$.

We will furthermore let $I^r$ denote the \bf reverse \it of a semiorder $I$, which we will define as being equivalent to its dual; that is, $I^r=I^{\partial}$ for any $I\in\I_n$, as defined in \cite{daveypriestley}.
\end{defn}

\subsection{Construction of the Bijection}

We will now define a mapping $F_n:\mathcal{I}_n\rightarrow
\mathcal{R}_n$.  Our bijection uses the nose and hollow relations on
the elements of the semiorder to explicitly construct a Riordan path.
We prove the bijectiveness of the mapping inductively, using our
operations to construct larger semiorders from smaller ones.

Let $I\in\mathcal{I}_n$, and let $x_i$ denote the $i$th element of $I$
where $1<i<n$. We will now define the nine possible cases for $x_i$,
and, for each, the type of point that $x_i$ will correspond to in the
Riordan path.

\begin{itemize}
\item 2 Hollows - There exist elements $a,b$ such that $aHx_i$, $x_iHb$, and there exists no element $c$ such that $cNx_i$ or $x_iNc$. In this case, we set the $i$th point in the path to a hard peak.
\item 2 Noses - There exist elements $a,b$ such that $aNx_i$, $x_iNb$, and there exists no element $c$ such that $cHx_i$ or $x_iHc$. In this case, we set the $i$th point in the path to a hard dip.
\item 2 Hollows, 1 Nose - There exist elements $a,b$ such that $aHx_i$, $x_iHb$, and there exists an element $c$ such that $x_iNc$ ($cNx_i$). In this case, we set the $i$th point in the path to a positive (negative) soft peak.
\item 2 Noses, 1 Hollow - There exist elements $a,b$ such that $aNx_i$, $x_iNb$, and there exists an element $c$ such that $x_iHc$ ($cHx_i$). In this case, we set the $i$th point in the path to a positive (negative) soft dip.
\item 1 Nose, 1 Hollow - There exist elements $a,b$ such that $x_iNa$ and $x_iHb$ ($aNx_i$ and $bHx_i$), and there exists no elements $c$ such that $cNx_i$ or $cHx_i$ ($x_iNc$ or $x_iHc$). In this case, we set the $i$th point in the path to a positive (negative) slope.
\item 2 Noses, 2 Hollows - There exist elements $a,b,c,d$ such that $aNx_i$,$bHx_i$,$x_iNc$,$x_iHd$. In this case, we set the $i$th point in the path to be a level point.
\end{itemize}

Since any two semiorders with different nose and hollow relations are
different (as shown by Pirlot in \cite{Pi}), as are any two paths with
a different list of point types, this gives a well-defined map from
$\mathcal{I}_n$ to $\mathcal{R}_n$.  Since we showed in part (i) that
$\mathcal{I}_n$ and $\mathcal{R}_n$ have the same size, we need only
show that the map is onto for each value of $n$ to prove each map $F_n$
is a bijection.  We formalize this here.

\begin{thm}\label{Thm:bijection}
Let $n>2$. If $F_n:\mathcal{I}_n\rightarrow \mathcal{R}_n$ is onto, then $F_n$ is a bijection.
\end{thm}


\begin{figure}[htbp]
\centering
\epsfig{file=motzkin_example.eps, scale=.6}
\caption{An example of an interesting semiorder $I$, given in matrix and interval representations, and its corresponding path.}
\label{Fig:motzkin_example}
\end{figure}


\begin{defn}
Let $x_i$ be the $i$th element in the trace of an interesting semiorder $I\in\I_n$.
\begin{itemize} 
\item We say that $x_i$ \bf initiates \it a nose (hollow) if there exists an element $b\in I$ such that $x_iNb$ ($x_iHb$) and no element $a\in I$ such that $aNx_i$ ($aHx_i$).
\item We say that $x_i$ \bf terminates \it a nose (hollow) if there exists an element $a\in I$ such that $aNx_i$ ($aHx_i$) and no element $b\in I$ such that $x_iNb$ ($x_iHb$).
\item We say that $x_i$ \bf continues \it a nose (hollow) if there exist elements $a,b\in I$ such that $aNx_i$ ($aHx_i$) and $x_iNb$ ($x_iHb$).
\end{itemize}
\end{defn}

Given that $I$ is an interesting semiorder, we see that there are {\em
a priori} 16 types of elements in our semiorder (Each point may be the
starting and/or ending point of a nose and/or a hollow, or not), yet
we've claimed there are only nine types of elements.  We now show that
there are no other possible cases for the element $x_i$ given that $I$
is an interesting semiorder. The following theorem provides a set of
restrictions on $x_i$ that follow from the properties of $I$.

\begin{thm}
Let $I$ be a semiorder of order $n$ and let $x_i$ be the $i$th element of $I$. If $I$ is interesting, then $x_i$ has the following properties:

\begin{itemize}
\item[(i)] If $x_i$ initiates a hollow, then $x_i$ does not terminate a nose.
\item[(ii)] If $x_i$ terminates a hollow, then $x_i$ does not initiate a nose.
\item[(iii)] $x_i$ shares a nose/hollow relationship with at least two distinct elements $a,b\in I$.
\end{itemize}
\end{thm}

\begin{proof}
Let $I\in\I_n$ and let $x_i$ be the $i$th element of $I$.
\begin{itemize}
\item[Case i:] Suppose $x_i$ initiates a hollow. Thus we have that no element hollows $x_i$, which implies that $\suc(x_i)=\suc(x_{i+1})$. Now suppose $x_i$ terminates a nose, implying that $x_i$ does not nose any element of $I$. Thus we have that $\pred(x_i)=\pred(x_{i+1})$. We have therefore shown that $x_i$ and $x_{i+1}$ are redundant elements, a contradiction. We conclude that $x_i$ does not terminate a nose.
\item[Case ii:] Suppose $x_i$ terminates a hollow. Thus we have that $x_i$ hollows no element of $I$, which implies that $\pred(x_i)=\pred(x_{i-1})$. Now suppose $x_i$ initiates a nose, implying that no element of $I$ noses $x_i$. Thus we have that $\suc(x_i)=\suc(x_{i-1})$. Again, this shows redundancy between elements $x_i$ and $x_{i-1}$, contradicting the fact that $I$ is interesting. We conclude that $x_i$ does not initiate a nose.
\item[Case iii:] This case follows directly from the arguments in the previous cases.
\end{itemize} 
\end{proof}




The following theorems will provide the necessary procedures for
building interesting semiorders from those of smaller order based on
the differences between their corresponding Riordan paths. Given two
Riordan paths of orders $m$ and $n$, respectively, we may use the
machinery provided in Theorem \ref{Thm:split}  to ``glue" these two
Riordan paths together at the ends, as well as construct the semiorder
associated with our result. Theorem \ref{Thm:mirror} will allow us to
take the mirror image of a Riordan path and find its associated
semiorder, based on the semiorder of the original. Using Theorem
\ref{Thm:mirror} in conjunction with the different cases of Theorem
\ref{Thm:horiz} we will be able to take any Riordan path and add a
horizontal step anywhere above the axis, and find the semiorder
associated with our result. Finally, Theorem \ref{Thm:upsteps} will
allow us to add an up-step and a down-step to the beginning and end of
a Riordan path (respectively) and, again, generate the corresponding
semiorder

By generating semiorders from paths of smaller order, we will be able to prove inductively that $F_n$ is onto for all $n>2$.



\begin{thm}\label{Thm:split}
If two Riordan paths $M_m\in\R_m,M_n\in\R_n$ have preimages under $F_m$ and $F_n$, respectively, the Riordan path $M_m+M_n$ has a preimage under $F_{m+n-1}$.
\end{thm}

\begin{proof}
Let $M_m$ and $M_n$ be the images of two interesting semiorders $I_m$, $I_n$ under $F_m$, $F_n$, respectively. We will now construct a semiorder $I\in\I_{m+n-1}$ and show that its image under $F_{m+n-1}$ is $M_m+M_n$ by constructing its incidence matrix, which we will denote $ A$. We will denote the incidence matrices of $I_m$ and $I_n$ as $B,C$, respectively.

Let $x_m$ denote the last element in the trace of $I_m$ and let $y_1$
denote the first element in the trace of $I_n$. In adding our two
Riordan paths together we are essentially combining the points $x_m$
and $y_1$ into one, with their corresponding element in $I$ being
denoted $x$. Since $I_m$ and $I_n$ are interesting semiorders, let
$\alpha Hx_m$ and $x_m N\beta$, where $\alpha$ is the $p$th element in
the trace of $I_m$ and $\beta$ is the $q$th element in the trace of
$I_n$. We have the entries of $ A$ as follows:

$$
 A_{i,j} = \left\{ 
\begin{array}{ll}
B_{(i,j)}, &\mbox{ if } i<p,j\leq m;\\
C_{(i-m+1,j-m+1)} &\mbox{ if } i>m,j\geq m;\\
0,&\mbox{ if } i>m,j<m;\\
0,&\mbox{ if } p<i\leq m,j<m+q-1;\\
1,&\mbox{ if } i<p,j>m;\\
1,&\mbox{ if } p<i\leq m,j\geq m+q-1\\
\end{array}\right.
$$ 

This procedure simply adds all elements of $I_n$ to the predecessor
sets of the first $p-1$ elements in $I_m$, and adds the last $n-q+1$
elements of $I_n$ to the predecessor sets of the last $m-p+1$ elements
of $I_m$. This is demonstrated in Figure 3. Since we are simply adding
elements to the predecessor sets of elements from $I_m$, we have that
the irredundancy and connectedness of $I$ follow necessarily from those
of $I_m$ and $I_n$. Thus our resultant semiorder $I$ is interesting.

Since $I\in\I_{m+n-1}$, we will now show that $F_{m+n-1}$ maps $I$ to
$M_m+M_n$. Note that when we restrict $ A$ to rows and columns
$1,\ldots,m$, we obtain the matrix $A$, and thus the only relationship
difference between the elements of $I_m$ and their corresponding
elements of $I$ is that $\alpha Hx_m$ in $I_m$ and $\alpha H\beta$ in
$I$.  Similarly, when restricting $ A$ to rows and columns
$m,\ldots,m+n-1$, we obtain the matrix $B$, and our only difference is
that $x_nH\beta$ in $I_n$ and $\alpha H\beta$ in $I$. Note that
$\alpha$ and $\beta$ are therefore mapped to the same type of point
(with reference to Definition \ref{Def:pttype}) as they were in $F_m$
and $F_n$, respectively, since $\alpha$ still hollows another element
and an element still hollows $\beta$.  Applying our function
$F_{m+n-1}$ to $I$, we therefore find that the shape of the first $m$
points of our path is equivalent to that of $M_m$. Since noses are
preserved by our procedure, $x$ is a hard dip. This implies that $x$ is
followed by an up-step, just as is $x_n$ in $M_n$. Finally, we find
that the shape of the last $n$ points of the path is equivalent to that
of $M_n$. We have therefore shown that $F_{m+n-1}(I)=M_m+M_n$.


\begin{figure}
\label{splitmatrix}
\begin{tabular}{ccc}
\begin{tabular}{c|c}
$I_m$&1\\
&\\
\hline
&\\
0&$I_n$\\
\end{tabular}
&
\begin{tabular}{c}
$\rightarrow$
\end{tabular}
&
\begin{tabular}{c|ccccc|c|cccc}
&1&2&$\cdots$&$\alpha$&$\cdots$&$x$&$\cdots$&$\beta$&$q$&$\cdots$\\
\hline
1&&&&&&&&\\
2&&&&&&&&\\
$\vdots$&&&&&&&&\\
$p$&0&0&$\cdots$&0&1&1&$\cdots$&1&1&$\cdots$\\
$\alpha$&0&0&$\cdots$&0&0&0&$\cdots$&0&1&$\cdots$\\
$\vdots$&0&0&$\cdots$&0&0&0&$\cdots$&0&1&$\cdots$\\
\hline
$x$&0&0&$\cdots$&0&0&0&$\cdots$&0&1&$\cdots$\\
\hline
$\vdots$&&&&&&0&$\cdots$&0&0&$\cdots$\\
$\beta$&&&&&&&&\\
\end{tabular}
\end{tabular}
\caption{Constructing the Preimage of $M_m+M_n$}
\end{figure}

\end{proof}

\begin{thm}\label{Thm:mirror}
If $M$ is a Riordan path of order $n$ and has a preimage $I$ under $F_n$, then $M^r$ has a preimage under $F_n$, namely $I^r$. 
\end{thm}

\begin{proof}
Let $M\in\R_n$, let $\{P_k\}_{k=1}^n$ be the ordered set of points of
$M$, and suppose $F_n(I)=M$, where $I\in\I_n$. Let $x\in I$. If $aHx$
for some element $a\in I$, then $xHa$ in $I^r$, since $\pred(x)$ in $I$
is equal to $\suc(x)$ in $I^r$. This applies analogously to the cases
of $aNx$, $xNa$, and $xHa$ in $I$. Thus if $x\in I$ is mapped to a
positive (negative) soft peak or dip, then $x\in I^r$ is mapped to a
negative (positive) soft peak or dip. Similarly, if $x\in I$ is mapped
to a positive (negative) slope, then $x\in I^r$ is mapped to a negative
(positive) slope. If $x\in I$ is mapped to either a hard peak, a hard
dip, or a level point, $x\in I^r$ is mapped to the same type of point.
Let $F_n(I^r)=M^{\prime}$ and let $\{Q_k\}_{k=1}^n$ represent the
ordered set of points of $M^{\prime}$.

Since the ordering of elements in the trace of $I^r$ is reversed with
respect to their ordering in the trace of $I$, we now have that each
point $Q_k$ of $M^{\prime}$ corresponds to that of $P_{n-k+1}$ with
respect to the element they represent in $I^r$ and $I$, respectively.
Thus we have shown that $M^{\prime}=M^r$, and that the preimage of
$M^r$ under $F_n$ is $I^r$.  \end{proof}

\begin{thm}\label{Thm:horiz}
Let $P_j$ denote the $j$th point in a Riordan path $M\in\R_n$ where $1<j<n$. Furthermore, let $M^{h}_j$ denote the path $P_1,\ldots,P_{j-1},P_a,P_b,P_{j+1},\ldots,P_n$ where $(P_{j-1},P_a)$ and $(P_b,P_{j+1})$ are the same types of steps as $(P_{j-1},P_j)$ and $(P_j,P_{j+1})$ in $M$, respectively, and $(P_a,P_b)$ is a horizontal step. We describe this process as adding a horizontal step to point $P_j$, which is shown graphically in Figures \ref{Fig:horiz_start} and \ref{Fig:horiz_finish}. If $M$ has a preimage under $F_n$, and $M^h_j$ is a Riordan path, then $M^h_j$ has a preimage under $F_{n+1}$.
\end{thm}


\begin{figure}
\begin{center}
{\bf Reassigning Noses and Hollows:  Specific Cases}
\begin{tabular}{|l|lcl|}
\hline
Hard Peak&if $\{p_i\}_{i=1}^k,\{q_i\}_{i=1}^k\neq\emptyset$&$\rightarrow$&Shift Summary Table\\&&&\\
&if $\{p_i\}_{i=1}^k=\{q_i\}_{i=1}^k=\emptyset$&$\rightarrow$&Set $x_0Hx_1$.\\
\hline
Positive Soft Peak&if $\{p_i\}_{i=1}^k,\{q_i\}_{i=1}^k\neq\emptyset$&$\rightarrow$&Shift Summary Table\\&&&\\
&if $\{p_i\}_{i=1}^k=\{q_i\}_{i=1}^k=\emptyset$&$\rightarrow$&Set $x_0Hx_1$.\\
\hline
Positive Soft Dip&$\{p_i\}_{i=1}^k,\{q_i\}_{i=1}^k\neq\emptyset$&$\rightarrow$&Shift Summary Table\\&&&\\
\hline
Positive Slope&$\{p_i\}_{i=1}^k,\{q_i\}_{i=1}^k\neq\emptyset$&$\rightarrow$&Shift Summary Table\\&&&\\
\hline
Hard Dip&Either Case&$\rightarrow$&Shift Summary Table\\&&&\\
\hline
\end{tabular}
\end{center}
\end{figure}

\begin{center}
{\bf Shift Summary Table}\\

\begin{tabular}{| c | c |}
\hline
{\bf $I$} & $I_j^h$\\
\hline
$aHb \; (a<b<x \; {\textrm or } \;  x<a<b)$ & $aHb$ \\
$aNb \; (a<b<x \;{\textrm or }\; x<a<b)$ & $aNb$ \\
\hline
 & $p_1 H x_0$ \\
 $p_iHq_i \; (p_i < x < q_i) $ & $p_i H q_{i-1}$ \\
  & $x_1 H q_k $ \\ 
\hline
 & $r_1 N x_0$ \\
 $r_iNs_i \; (r_i < x < s_i) $ & $r_i N s_{i-1}$ \\
  & $x_1 N s_l $ \\ 
\hline
\end{tabular}
\end{center}


\begin{proof}
Let $M\in\R_n$, $P_j$, and $M^h_j$ be as defined above, and suppose $M$
has a preimage $I$ under $F_n$. The following notation will be used
when applicable in each case: Let $x$ denote the element of $I$
corresponding to $P_j$. Let $\{p_i\}_{i=1}^k$ be the possibly empty set
of elements preceding $x$ in the trace of $I$ such that $p_iHq_i$,
where $\{q_i\}_{i=1}^k$ is a set of elements succeeding $x$ in the
trace of $I$. Let $\{r_i\}_{i=1}^l$ be the set of elements preceding
$x$ in the trace of $I$ such that $r_iNs_i$, where $\{s_i\}_{i=1}^l$ is
a set of elements succeeding $x$ in the trace of $I$. Note that in our
first four cases, this set is trivially nonempty. Let $\alpha Hx$,
$xH\beta$, $\gamma Nx$, $xN\delta$, if such elements exist.

Now, let $I^h_j$ denote the semiorder in which the first $j-1$ elements
and the last $n-j$ elements are obtained from their corresponding
elements in $I$. These elements will inherit all nose/hollow
relationships from $I$ with the exception of those involving
$\alpha,\beta,\gamma,\delta$, and $x$, those of the form $p_iHq_i$, and
those of the form $r_iNs_i$. Between these elements we will place two
elements $x_0,x_1$, in that order.

In each following case we set $p_iHq_{i-1}$, $r_iNs_{i-1}$ for $i>1$,
essentially ``shifting" our noses and hollows to make room for those of
the newly-added point. We will then construct the remaining nose/hollow
relationships of $I^h_j$, and show that $I^h_j\in\I_n$ and
$F_n(I^h_j)=M^h_j$.\newline

Case 1: $P_j$ is a hard peak. Let $I^h_j$ have the following
properties: $p_1Hx_1$, $x_1H\beta$, $\alpha Hx_0$, $x_0Hq_k$,
$r_1Nx_1$, and $x_0Ns_l$. If our sets $\{p_i\}_{i=1}^k$ is empty, we
set $x_0Hx_1$. By this construction every element in $I^h_j$, $x_0$ and
$x_1$, has the same number and type of nose/hollow relationships as
their corresponding elements of $I$. Furthermore, with the definition
of the nose/hollow relationships of $x_0$ and $x_1$, $(x_0,x_1)$ is now
a horizontal step, with $x_0$ mapping to a positive soft peak and $x_1$
mapping to a negative soft peak. Thus we have shown that if $I\in\I_n$,
then $F_{n+1}(I^h_j)=M^h_j$.

Let $ A$ denote the incidence matrix of $I$. We will investigate the
incidence matrix of $I$, which we will denote $ A^h_j$, with the
purpose of showing that $I\in\I_n$. $ A^h_j$ is constructed as follows:
We start with the matrix $ A$, and duplicate the row and column
corresponding to $x$, placing the copy next to the original. These two
duplicate rows and columns are $x_0$ and $x_1$. The resulting matrix
implies that $\alpha Hx_1$, so we add a ``1" in the row corresponding
to $\alpha$ so that we have $\alpha Hx_0$. Now let $r_i$ correspond to
the $z_i$th row in the matrix for all $i$. We add enough 1's in rows
$z_i$ through $z_{i+1}-1$ so that the nose $r_iNs_i$ has now become
$r_iNs_{i-1}$ and $r_1Nx_1$. Note that this furthermore shifts each
hollow such that we now have $p_iHq_{i-1}$. Finally, we add enough 1's
in the row corresponding to $x_0$ so that we have $x_0Ns_k$. This
procedure is exemplified in Figures \ref{Fig:horiz_hp_incidence},
\ref{Fig:horiz_start}, and \ref{Fig:horiz_finish}.

Let $a,b\in I^h_j$ where $a$ immediately precedes $b$ in the trace of
$I^h_j$. Since $p_1Hx_1$, $x_0Hq_k$, and the pair $x_0,x_1$ have
different predecessor sets, neither $a$ nor $b$ are the elements $x_0$
or $x_1$.  Suppose $\pred(a)=\pred(b)$ and $\suc(a)=\suc(b)$. Then $a$
does not nose any element, and no element hollows $a$ in $I^a$. These
statements are also true in $I$ by our construction of $I^h_j$. This
implies that $\pred(a)=\pred(b)$ and $\suc(a)=\suc(b)$ in $I$, a
contradiction. Thus, $I^h_j$ is irredundant. We must now verify the
connectedness of $I^h_j$. By our construction of $I^h_j$, no element
noses an element adjacent to it in the trace; the noses $r_1Nx_1$,
$x_0Ns_l$, and $r_iNs_{i-1}$ are all between non-adjacent elements.
Since all other nose relationships were inherited from $I$, this shows
that $I^h_j$ is connected. We conclude that $I^h_j\in\I_{n+1}$.

\begin{figure} \begin{tabular}{c}
\begin{tabular}{c|ccccccccccccccccccc}
&1&$\alpha$/$r_1$&$p_1$&$r_2$&$p_2/r_3$&$x$&$q_1/s_1$&$q_2/s_2$&$\beta/s_3$&10\\
\hline 1&0&0&0&1&1&1&1&1&1&1\\ $\alpha$/$r_1$&0&0&0&0&0&0&1&1&1&1\\
$p_1$&0&0&0&0&0&0&0&1&1&1\\ $r_2$&0&0&0&0&0&0&0&1&1&1\\
$p_2/r_3$&0&0&0&0&0&0&0&0&1&1\\ $x$&0&0&0&0&0&0&0&0&0&1\\
$q_1/s_1$&0&0&0&0&0&0&0&0&0&1\\ $q_2/s_2$&0&0&0&0&0&0&0&0&0&1\\
$\beta/s_3$&0&0&0&0&0&0&0&0&0&0\\ 10&0&0&0&0&0&0&0&0&0&0\\
\end{tabular}\\\\ The incidence matrix of a semiorder in $\I_{10}$. The
associated Riordan path is shown in\\ Figure \ref{Fig:horiz_start}.\\

\begin{tabular}{c|ccccccccccccccccccc}
&1&$\alpha$/$r_1$&$p_1$&$r_2$&$p_2/r_3$&$x_0$&$x_1$&$q_1/s_1$&$q_2/s_2$&$\beta/s_3$&10\\
\hline
1&0&0&0&1&1&1&1&1&1&1&1\\
$\alpha$/$r_1$&0&0&0&0&0&0&0&1&1&1&1\\
$p_1$&0&0&0&0&0&0&0&0&1&1&1\\
$r_2$&0&0&0&0&0&0&0&0&1&1&1\\
$p_2/r_3$&0&0&0&0&0&0&0&0&0&1&1\\
$x_0$&0&0&0&0&0&0&0&0&0&0&1\\
$x_1$&0&0&0&0&0&0&0&0&0&0&1\\
$q_1/s_1$&0&0&0&0&0&0&0&0&0&0&1\\
$q_2/s_2$&0&0&0&0&0&0&0&0&0&0&1\\
$\beta/s_3$&0&0&0&0&0&0&0&0&0&0&0\\
10&0&0&0&0&0&0&0&0&0&0&0\\
\end{tabular}\\\\

The incidence matrix after duplication.\\


\begin{tabular}{c|ccccccccccccccccccc}
&1&$\alpha$/$r_1$&$p_1$&$r_2$&$p_2/r_3$&$x_0$&$x_1$&$q_1/s_1$&$q_2/s_2$&$\beta/s_3$&10\\
\hline
1&0&0&0&1&1&1&1&1&1&1&1\\
$\alpha$/$r_1$&0&0&0&0&0&0&1&1&1&1&1\\
$p_1$&0&0&0&0&0&0&0&1&1&1&1\\
$r_2$&0&0&0&0&0&0&0&1&1&1&1\\
$p_2/r_3$&0&0&0&0&0&0&0&0&1&1&1\\
$x_0$&0&0&0&0&0&0&0&0&0&1&1\\
$x_1$&0&0&0&0&0&0&0&0&0&0&1\\
$q_1/s_1$&0&0&0&0&0&0&0&0&0&0&1\\
$q_2/s_2$&0&0&0&0&0&0&0&0&0&0&1\\
$\beta/s_3$&0&0&0&0&0&0&0&0&0&0&0\\
10&0&0&0&0&0&0&0&0&0&0&0\\
\end{tabular}\\\\

The incidence matrix after shifting rows $\alpha$ through $x_0$. The associated Riordan path is\\ shown in in Figure \ref{Fig:horiz_finish}.\\
\end{tabular}


\caption{Constructing the Incidence Matrix $ A^h_j$ from $ A$ with $j=6$}
\label{Fig:horiz_hp_incidence}
\end{figure}

Case 2: $P_j$ is a positive soft peak. Let $I^h_j$ have the following
properties: $p_1Hx_1$, $x_1H\beta$, $\alpha Hx_0$, $x_0Hq_k$,
$r_1Nx_1$, $x_1N\delta$, and $x_0Ns_k$. If $\{p_i\}_{i=1}^k$ is empty,
then set $x_0Hx_1$. Analogously to our previous case, this construction
implies that if $I^h_j\in\I_n$, then $F_{n+1}(I^h_j)=M^h_j$.

Furthermore, the construction of the incidence matrix of $I^h_j$ is
identical to that of the case of a hard peak. In duplicating the row
corresponding to $P_j$, the element $x_1$ is given the property
$x_1N\delta$, as required by our construction of $I^h_j$. Since the
procedure for constructing the incidence matrix of $I^h_j$ is the same
for both the case of the hard peak and the soft peak, we conclude that
$I^h_j$ is an interesting semiorder in the case of a soft peak as
well.\newline

Case 3: $P_j$ is a positive soft dip. Let $I^h_j$ have the following
properties: $p_1Hx_0$, $x_0Hq_k$, $x_1H\beta$, $r_1Nx_1$,
$x_1N_\delta$, $\gamma Nx_0$, and $x_0Ns_k$. Similar to the previous
cases, we have that f $I^h_j\in\I_n$, then $F_{n+1}(I^h_j)=M^h_j$.

In constructing our matrix, we proceed identically to the case of the
hard peak with one exception: rather than begin adding 1's with the row
corresponding to $\alpha$ (this element does not exist in this case),
we add a "1" to the row corresponding to $\gamma$ after duplication so
that $\gamma Nx_0$. We then proceed exactly as in the case of a hard
peak. Analogously, our resulting matrix represents an interesting
semiorder, and thus we have $F_{n+1}(I^h_j)=M^h_j$.\newline

Case 4: $P_j$ is a positive slope. Let $I^h_j$ have the following properties: $p_1Hx_0$, $x_0Hq_k$, $x_0Ns_k$, $r_1Nx_1$, $x_1N\delta$, and $x_1H\beta$. Similar to the previous cases, we have that f $I^h_j\in\I_n$, then $F_{n+1}(I^h_j)=M^h_j$.

Again, we construct our matrix in a manner identical to that of the case of the hard peak, with the following exception: Since $\alpha$ does not exist in this case, we simply ignore this element and begin adding 1's wherever necessary. This results in a matrix representing an interesting semiorder, proving that $F_{n+1}(I^h_j)=M^h_j$ for this case as well.\newline


Case 5: $P_j$ is a hard dip.

\begin{lem}\label{Lem:height}
Let $P$ be a hard dip of a Riordan path $M$ with preimage $I$ under $F_n$, let $n_i$ be the number of noses initiated prior to $P$, and let $n_t$ be the number of noses terminated prior to $P$. The height of $P$ is equal to $n_i-n_t-1$.
\end{lem}

\begin{proof}
Let $P_i$ denote the $i$th point in $M\in\R_n$, let $1<k<n$, let $u$ denote the number of up-steps prior to $P_k$, let $d$ denote the number of down-steps prior to $P_k$, let $h$ denote the number of hard peaks prior to $P_k$, and finally let $n_i$ and $n_t$ denote the number of noses initiated and terminated prior to $P_k$, respecitvely. 

For $i>1$, each point $P_i$ that initiates a nose is preceded by an up-step, and each point that terminates a nose precedes a downstep, which follows directly from our definition of $F_n$. Thus we can associate exactly one up-step to each nose initiated after $P_1$, and exactly one down-step to each nose terminated.

Each up-step that is not part of a hard peak immediately precedes a point that initiates a nose, and each down-step that is not part of a hard peak is immediately preceded by a point that terminates a nose. A hard peak neither initiates nor terminates a nose, and contains both an up-step and a down-step. We now note that $P_1$ initiates a nose but is not preceded by an up-step. 

Thus we arrive at the following two equations: $n_i=u-h+1$ (our ``+1" comes from the fact that we do not associate $P_1$ with an up-step) and $n_t=d-h$. Combining these, we get that $n_i-n_t=1+u-d$, or equivalently, $n_i-n_t-1=u-d$. We conclude that the height of $P_k$ is equal to $n_i-n_t-1$.
\end{proof}

In all previous cases, the fact that $M^h_j\in\R_{n+1}$ has been trivial. This case, however, provides the possibility of a horizontal step being added on the horizontal axis, which would result in $M^h_j$ not being a Riordan path. We will thus require that $P_j$ is of height greater than 0. Equivalently, this means that there are at least two unterminated noses initiated prior to the point $P_j$, by the previous lemma. One of these noses is initiated by the point corresponding to $\gamma$, and the rest ensure that our set $\{r_i\}^l_{i=1}$ is non-empty. 

For this case, we let $I^h_j$ have the following properties: $\gamma Nx_0$, $x_0Ns_k$, $r_1Nx_1$, and $x_1N\delta$. We add 1's to our incidence matrix just as in previous cases, starting with the row corresponding to $\gamma$ and ending with that corresponding to $x_0$. Since there are no noses between adjacent points, connectedness is guaranteed, and irredundancy is guaranteed by an argument analogous to that of each previous case.

Finally, we consider the cases of a level point, a negative soft peak, and negative soft dip, and a negative slope. If $P_j$ is a negative soft peak, negative soft dip, or negative slope, we have that $M^h_j$ has a preimage under $F_{n+1}$ by Theorem \ref{Thm:mirror}. If $P_j$ is a level point, then adding a horizontal step to the point $P_j$ is equivalent to adding a horizontal step to the point $P_{j-1}$. Continuing as necessary, we find that adding a horizontal step to $P_j$ is equivalent to adding a horizontal step to $P_{j-i}$ for some $1<i<j-2$, where $P_{j-i}$ is not a level point. Since we have proven that $F_{n+1}(I^h_j)=M^h_j$ for every other case, we have therefore proven it for this case as well.
\end{proof}

\begin{figure}[htbp]
\centering
\epsfig{file=horiz_start-2.eps, width=\textwidth}
\caption{An example of a Motzkin path $M$.}
\label{Fig:horiz_start}
\epsfig{file=horiz_finish-2.eps, width=\textwidth}
\caption{The Motzkin path $M^h_5$}
\label{Fig:horiz_finish}
\end{figure}


\begin{thm}\label{Thm:upsteps}
Let $M\in\R_n$, and let $P_1,P_2,\ldots,P_n$ denote the ordered set of points in $M$, where $P_1$ is the left-most point. Now let $M^a$ denote the path consisting of the ordered points $x,P_1,P_2,\ldots,P_n,y$, where $P_i$ in $M$ and $(x,P_1),(P_n,y)$ represent an up-step and a down-step, respectively. If $M$ has a preimage in $F_n$, then $M^a$ has a preimage under $F_{n+2}$.
\end{thm}

\begin{proof}
Let $I$ be a semiorder such that $F_n(I)=M$, and let $i_j$ denote the $j$th element in the trace of $I$ for $1\leq j\leq n$. Furthermore, let $\{p_i\}_{i=1}^k,\{q_i\}_{i=1}^k$ denote the set of elements of $I$ such that $p_iHq_i$, and let $\{r_i\}_{i=1}^l$,$\{s_i\}_{i=1}^l$ denote the set of elements of $I$ such that $r_iNs_i$. We will now define a semiorder $I^a$ as the set $i_x,i_1,\ldots,i_n,i_y$ with noses $r_iNs_{i+1}$, $i_xNs_1$, $r_lNi_y$, and hollows $p_iHq_{i+1}$, $i_xHq_1$, and $p_kHi_y$. Note that each element $i_1,\ldots,i_n$ has the same number and type of nose/hollow relationships in $I^a$ as in $I$.

We will first show that $I^a$ is an interesting semiorder. The connectedness of $I^a$ follows trivially from the connectedness of $I$, so we will focus on proving irredundancy. 

Let $a,b\in I^a$ where $a$ immediately precedes $b$ in the trace of $I^a$. Suppose $\pred(a)=\pred(b)$ and $\suc(a)=\suc(b)$. Then $a$ does not nose any element, and no element hollows $a$ in $I^a$. These statements are also true in $I$ by our construction of $I^a$. This implies that $\pred(a)=\pred(b)$ and $\suc(a)=\suc(b)$ in $I$, a contradiction. We conclude that $I^a\in\I_{n+2}$. 

We will now show that $F_{n+2}(I^a)=M^a$. By our construction of $I^a$, the elements $i_2,\ldots,i_{n-1}$ map to points $P_2,\ldots,P_{n-2}$ under $F_{n+2}$, respectively. The points $i_1$ and $i_n$ now map to positive and negative slopes, respectively, since $i_1$ necessarily hollows and noses two elements in $I^a$, and $i_n$ is necessarily nosed and hollowed by two elements in $I^a$. This furthermore shows that $(x,P_1)$ is an up-step and $(P_n,y)$ is a downstep. Finally, due to the noses and hollows constructed for elements $i_x,i_y$, we have that they properly correspond to the first and last elements of a Riordan path, namely $M^a$.
\end{proof}


\begin{thm}
The function $F_n$ is a bijection for all $n>2$.
\end{thm}

\begin{proof}

We will prove by induction on $n$ that $F_n$ is onto, with the case $n=3$ shown in Figure $\ref{Fig:basecase}$, and case $n=4$ given by Theorem \ref{Thm:horiz} and the case $n=3$. By Theorem \ref{Thm:bijection}, this will show that $F_n$ is a bijection for all $n>2$. 

Let $n\geq 5$ and assume that $F_k$ is a bijection for all $2<k<n$. Suppose $M$ has a horizontal step and let $M^{\prime}$ denote the Riordan path of length $n-1$ with this horizontal step deleted. By our inductive hypothesis, this shows that $M^{\prime}$ has a preimage under $F_{n-1}$. By Theorem \ref{Thm:horiz}, $M$ has a preimage under $F_n$.

Now suppose that $M$ has no horizontal steps, and suppose that there exists a point $P_i$ in $M$ such that $P_i$ is on the horizontal axis and $1<i<n$. Let $M_1,M_2$ denote the Riordan paths consisting of points $P_1,\ldots,P_i$ and $P_i,\ldots,P_n$, respectively. We have that $M_1+M_2=M$. By our inductive hypothesis and Theorem \ref{Thm:split}, we have that $M$ has a preimage under $F_n$.

Finally, suppose that $M$ has no horizontal steps and that there are no points other than $P_1$ and $P_n$ on the horizontal axis. Now let $M^{\prime\prime}$ denote the path with the first and last steps deleted. Since there are no horizontal steps and no points on the horizontal axis in $M$, this implies that $M^{\prime\prime}$ has no points below the axis and no horizontal steps on the axis, i.e., it is a Riordan path. By our inductive hypothesis and Theorem \ref{Thm:upsteps}, $M$ has a preimage under $F_n$.

Since these cover every possible case for $M$, we have shown that $F_n$ is onto. By Theorem \ref{Thm:bijection}, $F_n$ is a bijection for all $n>2$.
\end{proof}

\begin{figure}[htbp]
\centering
\epsfig{file=base.eps, width=\textwidth}
\caption{The Riordan path of base case $n=3$, as well as its interval representation.}
\label{Fig:basecase}
\end{figure}

\section{Acknowledgement}
We are thankful to Jean-Paul Doignon for many helpful comments in the preparation of this manuscript.  
We would also like to thank the referee for their comments regarding presentation and clarity.  

\begin{thebibliography}{8} 

\bibitem {daveypriestley}
B. A. Davey and H. A. Priestley,
{\em Introduction to Lattices and Order}, Cambridge, 1990.

\bibitem {Ber}
F. Bernhart, Catalan, Motzkin, and Riordan numbers,
\newblock {\em Discrete Math.} {\bf 204} (1999), 73--112.

\bibitem{Han}
P. Hanlon, Counting interval graphs,
\newblock {\em Trans. Amer. Math. Soc.} {\bf 272} (1982), 383--426.

\bibitem{Chen}W. Chen, E. Deng, and L. Yang,  Riordan paths and derangements,
\href{http://arxiv.org/abs/math/0602298}{\tt http://arxiv.org/abs/math/0602298}.

\bibitem{Slo} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,
\href{http://research.att.com/~njas/sequences}{\tt http://research.att.com/$\sim$njas/sequences}.

\bibitem{Pi} M. Pirlot, Minimal representation of a semiorder,
\newblock {\em Theory and Decision} {\bf 28} (1990), 109--141.

\bibitem{Pi2} M. Pirlot, Synthetic description of a semiorder,
\newblock {\em Discrete Math.} {\bf 31} (1991), 299--308.

\bibitem{Donaghey}
R. Donaghey, and L. W. Shapiro, Motzkin numbers,
\newblock {\em J. Combin. Theory, Ser. A} {\bf 23} (1977), 291--301.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 06A07.

\noindent \emph{Keywords: } 
Riordan numbers, interval orders, semiorders, lattice paths.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108} and
\seqnum{A005043}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 14 2007;
revised version received  July 18 2007.
Published in {\it Journal of Integer Sequences}, July 23 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}

                                                                                


.