\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Combinatorial Results for Semigroups of
\\ \vskip .05in
Orientation-Preserving Partial \\
\vskip .12in 
Transformations } \vskip 1cm \large
A. Umar \\
Department of Mathematics and Statistics\\
Sultan Qaboos University\\
Al-Khod, PC 123 \\
Sultanate of Oman \\
\href{mailto:aumarh@squ.edu.om}{\tt aumarh@squ.edu.om} \\
\end{center}

\vskip .2 in

\def\dom{\mathop{\rm Dom}\nolimits}

%%%%%%%%%%%%%%%%%%%%%% Macros %%%%%%%%%%%%%%%%%%

\newcommand{\Cp}[1]{\ensuremath{\mathcal{C}^*(#1)}}

\newcommand{\SP}[1]{\ensuremath{\mathcal{S}^*(#1)}}

\newcommand{\Cpm}[1]{\ensuremath{\overline{\mathcal{C}^*}(#1)}}

\newcommand{\Spm}[1]{\ensuremath{\overline{\mathcal{S}^*}(#1)}}

\newcommand{\B}[3]{\ensuremath{\mathcal{B}_{{#1}\dots{#2}}^{#3}}}

\newcommand{\Bp}[3]{\ensuremath{\mathcal{B}_{{#1}\dots{#2}}^{*{#3}}}}

\newcommand{\Cpx}[2]{\ensuremath{\mathcal{C}^*(#1,#2)}}

\newcommand{\Spmx}[2]{\ensuremath{\overline{\mathcal{S}^*}(#1,#2)}}

\newcommand{\cp}[1]{\ensuremath{{c}^*(#1)}}

\newcommand{\sP}[1]{\ensuremath{{s}^*(#1)}}

\newcommand{\cpm}[1]{\ensuremath{\overline{{c}^*}(#1)}}

\newcommand{\spm}[1]{\ensuremath{\overline{{s}^*}(#1)}}

\newcommand{\bp}[3]{\ensuremath{{b}_{{#1}\dots{#2}}^{*{#3}}}}

\newcommand{\cpx}[2]{\ensuremath{{c}^*(#1,#2)}}

\newcommand{\spmx}[2]{\ensuremath{\overline{{s}^*}(#1,#2)}}

\begin{abstract}
Let $X_n = \{1, 2, \ldots , n\}$.  On a partial transformation
$\alpha : \dom \alpha \subseteq  X_n \rightarrow \mbox{Im }\alpha
\subseteq X_n$ of $X_n$ the following parameters are defined: the
{\em breadth or width} of $\alpha$ is $\mid {\rm Dom}\ \alpha\mid$,
the {\em height} of $\alpha$ is $\mid \mbox{Im }\alpha\mid$, and the
{\em right (resp., left) waist} of $\alpha$ is $\max(\mbox{Im } \alpha)$
 (resp., $\min(\mbox{Im } \alpha)$). We compute the cardinalities of some
equivalences defined by equalities of these parameters on ${\cal
OP}_n$, the semigroup of orientation-preserving full transformations
of $X_n$, ${\cal POP}_n$ the semigroup of orientation-preserving
partial transformations of $X_n$, ${\cal OR}_n$ the semigroup of
orientation-preserving/reversing full transformations of $X_n$, and
${\cal POR}_n$ the semigroup of orientation-preserving/reversing
partial transformations of $X_n$, and their partial one-to-one
analogue semigroups, ${\cal POPI}_n$ and ${\cal PORI}_n$.
\end{abstract}


\section{Introduction and Preliminaries}\label{sec1}
\setcounter{equation}{0} Let $X_n = \{1, 2, \ldots , n\}$. A
(partial) transformation $\alpha :\mbox{Dom }\alpha \subseteq  X_n
\rightarrow \mbox{Im }\alpha \subseteq X_n$ is said to be {\em full}
or {\em total} if $\mbox{Im }\alpha = X_n$; otherwise it is called
{\em strictly} partial. The {\em breadth or width} of $\alpha$ is
denoted and defined by $b(\alpha)= \mid {\rm\ Dom\ } \alpha\mid$.
The {\em height} or {\em rank} of $\alpha$ is denoted and defined by
$h(\alpha)= \mid {\rm Im}\ \alpha\mid$. The {\em right (resp., left) waist}
of $\alpha$ is denoted and defined by $w^+(\alpha) = \max(\mbox{Im }
\alpha)$ (resp., $w^-(\alpha) = \min(\mbox{Dom }\alpha)$). Of course, other
parameters have been defined and many more could still be defined
but we shall restrict ourselves to only these in this paper. It is
worth noting that to define the left (right) waist of a
transformation the base set $X_n$ must be totally ordered. The main
objects of study in this paper are ${\cal OP}_n$, the semigroup of
orientation-preserving full transformations of $X_n$, ${\cal POP}_n$
the semigroup of orientation-preserving partial transformations of
$X_n$, ${\cal OR}_n$ the semigroup of
orientation-preserving/reversing full transformations of $X_n$, and
${\cal POR}_n$ the semigroup of orientation-preserving/reversing
partial transformations of $X_n$, and their partial one-to-one
analogue semigroups, ${\cal POPI}_n$ and ${\cal PORI}_n$. For basic
and standard concepts in transformation semigroup theory the reader
may consult one of Howie \cite{How2}, Higgins \cite{Hig1} or
Ganyushkin and Mazorchuk \cite{Gan}.

Enumerative results of an essentially combinatorial nature in the
study of semigroups of transformations are now numerous and
interesting to warrant sections and plenty of exercises in
\cite{Gan} and survey articles \cite{How1, Fer4, Uma1, Uma2}. These
enumeration problems lead to many numbers in Sloane's encyclopaedia
of integer sequences \cite{Slo} but there is also the likelihood of
finding others that may not yet be recorded in \cite{Slo}. Motivated
by Higgins \cite{Hig2}, Laradji and Umar wrote a series of papers
\cite{Lar1, Lar2, Lar3, Lar4, Lar5} dealing exclusively with
combinatorial questions.

Let $S$ be a set of partial transformations on $X_n$. Next, let \\
$$F(n;r,p,k)= \mid\{\alpha \in S: b(\alpha)=r\wedge
h(\alpha)=p\wedge w^+(\alpha)=k\}\mid ,$$
and let $P=\{r,p,k\}$ be the set of counters for the
breadth, height, and right waist of a transformation. Then any
3-parameter combinatorial function can be expressed as
$F(n;a_1,a_2)$, where $\{a_1,a_2\} \subset P$. For example,
$$F(n;r,p)= \mid\{\alpha \in S: b(\alpha)=r\wedge
h(\alpha)=p\}\mid.$$

Similarly, any 2-parameter combinatorial function can be
expressed as $F(n;a_1)$. It is not difficult to see that
$$|S|= \sum_{a_1}{F(n;a_1)}, \,\, F(n;a_1)=
\sum_{a_2}{F(n;a_1,a_2)}.$$

We note also that certain special cases of these
combinatorial functions, when two or more parameters are equal or
when these parameters take extreme values are worth pointing out,
see for example, \cite{Lar3, Lar4}.

In Section $\ref{sec2}$ we consider the  semigroups of
orientation-preserving full and partial transformations ${\cal
OP}_n$ and ${\cal POP}_n$, while in Section $\ref{sec3}$ we consider
${\cal OR}_n$ and ${\cal POR}_n$, the semigroups of
orientation-preserving/reversing full and partial transformations of
$X_n$, respectively. And finally, in Section $\ref{sec4}$ we
consider the partial one-to-one analogues of the earlier considered
classes of semigroups, ${\cal POPI}_n$ and ${\cal PORI}_n$. We
conclude this section with a list of results that will be needed in
our proofs.

\begin{lemma} Let $\alpha$ be a partial transformation of $X_n=\{1,2, \ldots,n\}$.
Let $r=b(\alpha)$, $p=h(\alpha)$ and $k=w^+(\alpha)$. Then we have
the following:
\begin{enumerate}
    \item $n\geq r\geq p\geq 0$;
    \item $n\geq k\geq p\geq 0$;
    \item $r=1 \implies p=1$;
    \item $k=1 \implies p=1$;
    \item $r=0 \Leftrightarrow p=0 \Leftrightarrow k=0$.
\end{enumerate}
\end{lemma}

\begin{lemma}\label{lem1}
For all natural number $n$ we have
$$\sum_{i=1}^{n}(i-1){n\choose i}=(n-2)2^{n-1}+1.$$
\end{lemma}

\begin{proof} $$\sum_{i=1}^{n}(i-1){n\choose i}= n\sum_{i=1}^{n}{n-1\choose
i-1}-\sum_{i=1}^{n}{n\choose i}=n2^{n-1}-(2^n-1)=(n-2)2^{n-1}+1.$$
\end{proof}

\begin{lemma}\label{lem2}(Vandemonde's Convolution Identity,
\cite[(3a), p.\ 8]{Rio}).
For all natural numbers $m$, $n$ and $p$ we have

$$\sum_{k=0}^{n}{{n\choose {m-k}}{p\choose k}}={n+p\choose m}.$$

\end{lemma}

\begin{lemma}\label{lem3}\cite[Lemma 1.3]{Lar3}
For all natural numbers $n$ and $p$ we have
$$\sum_{k=p}^{n}{k-1\choose p-1}={n\choose p}.$$
\end{lemma}

\section{Orientation-Preserving Partial Transformations}\label{sec2}


Let $a=(a_1,a_2, \ldots,a_t)$ be a sequence of $t$ ($t>0$) elements
from the chain $X_n$. We say that $a$ is {\em cyclic} if there
exists no more than one index $i \in \{1,2, \ldots,t\}$ such that
$a_i > a_{i+1}$, where $a_{t+1}$ denotes $a_1$. For a partial
transformation $\alpha$ of $X_n$, suppose that $\dom \alpha =
\{a_1,a_2, \ldots,a_t\}$, with $t \geq 0$ and $a_1<a_2< \ldots
<a_t.$ We say that $\alpha$ is {\em orientation-preserving} if
$(a_1\alpha,a_2\alpha, \ldots,a_t\alpha)$ is cyclic. The semigroups
of orientation-preserving full and partial transformations of $X_n$
will be denoted by ${\cal OP}_n$ and ${\cal POP}_n$, respectively.
Moreover, note that for all $\alpha\in {\cal POP}_n$ and $y\in
\mbox{Im }\alpha$, $y\alpha^{-1}$ is convex with respect to $\dom
\alpha$ and the circular order. Further note that to partition $\dom
\alpha$ into $p$ nonempty convex subsets, we insert $p$ symbols
between the $r=|\dom \alpha|$ spaces. Then we have the principal
result of this section.

\begin{proposition}\label{prop1} Let $S = {\cal POP}_n$. Then
$$
F(n;r,p,k)=
\begin{cases}
{n\choose r}{k-1\choose p-1}{r\choose p}p,\,&\,n \geq r,k
\geq p > 1; \\
{n\choose r},\,&\,r=1\,or\,k=1\,or\,p=1.
\end{cases}
$$
\end{proposition}

\begin{proof} First, note that we can choose the $r$ elements of $\dom \alpha$
from $X_n$ in ${n\choose r}$ ways, and the $p$ elements of $\mbox{Im
}\alpha$ from $\{1,2, \ldots,k\}$ in ${k-1\choose p-1}$ ways, since
$k$ must be one of the choices. Next, we partition the $r$ chosen
elements of the domain into $p$-convex subsets in ${r\choose p}$
ways. It is clear that that there are exactly $p$ ways of tying
these $p$-subsets to the $p$-images. Hence the result follows.
\end{proof}

Let $a \in P=\{r,p,k\}$. Then for all $i\in \{0,1,
\ldots,n\}$ if $a=i$ we shall denote this by $a_i$.

\begin{corollary}\label{cor18} Let $S={\cal POP}_n$. Then
$$
F(n;r,p)=
\begin{cases}
{n\choose r}{n\choose p}{r\choose p}p,\,&\,n \geq r
\geq p > 1; \\
n{n\choose r},\,&\,r=1\,or\,p=1.
\end{cases}$$
\end{corollary}

\begin{proof} \begin{eqnarray*} F(n;r,p) & = & \sum_{k=p}^{n}F(n;r,p,k)=
\sum_{k=p}^{n}{n\choose r}
{k-1\choose p-1}{r\choose p}p \,\,(r\geq p\geq 2) \\
 & = & p{n\choose r}{r\choose p}\sum_{k=p\geq 2}^{n}
{k-1\choose p-1}={n\choose r}{r\choose p}{n\choose p}p\,\,\,(by\,
Lemma\,\ref{lem3}).
 \end{eqnarray*}
Moreover, it is not difficult to see that $F(n;r_1,p_1)=n^2$
 and $F(n;r,p_1)=n{n\choose r}$. Hence the result follows.\end{proof}


\begin{corollary}\label{cor19} Let $S={\cal POP}_n$. Then
$$ F(n;r,k)= r{n\choose r}{r+k-2\choose r-1}-(r-1){n\choose
r},$$ \noindent for\,$n \geq r,k\geq 1$.
\end{corollary}

\begin{proof} \begin{eqnarray*} F(n;r,k) & = & \sum_{p=1}^{k}F(n;r,p,k)=
{n\choose r}+\sum_{p=2}^{n}{n\choose r}
{k-1\choose p-1}{r\choose p}p \,\,(r,k\geq 2) \\
 & = & {n\choose r}+\sum_{p=1}^{n}{n\choose r}
{k-1\choose p-1}{r\choose p}p-r{n\choose r} \\
& = & r{n\choose r}\sum_{p=1}^{n}{k-1\choose p-1}{r-1\choose p-1}-(r-1){n\choose r}\\
 & = & r{n\choose r}{r+k-2\choose r-1}-(r-1){n\choose r}\,\,\,(by\,
Lemma\,\ref{lem2}).
 \end{eqnarray*}
Moreover, it is not difficult to see that $F(n;r_1,k)=n$ and
 $F(n;r,k_1)={n\choose r}$. Hence the result follows.\end{proof}


\begin{corollary}\label{cor20} Let $S={\cal POP}_n$. Then
$$
F(n;p,k)=
\begin{cases}
p2^{n-p}{n\choose p}{k-1\choose p-1},\,&\,n \geq k \geq p > 1; \\
2^n-1,\,&\,k=1\,or\,p=1.
\end{cases}
$$
\end{corollary}

\begin{proof} \begin{eqnarray*} F(n;p,k) & = & \sum_{r=p}^{k}F(n;r,p,k)=
\sum_{r=2}^{n}{n\choose r}
{k-1\choose p-1}{r\choose p}p \,\,(k\geq p\geq 2) \\
 & = & p{k-1\choose p-1}\sum_{r=2}^{n}{n\choose r}{r\choose p}
 = p{k-1\choose p-1}{n\choose p}\sum_{r=2}^{n}{n-p\choose r-p}\\
& = & p2^{n-p}{k-1\choose p-1}{n\choose p}.
 \end{eqnarray*}
Moreover, it is not difficult to see that $F(n;p_1,k)=F(n;p,k_1)=2^n-1$.
 Hence the result follows.\end{proof}

\begin{corollary}\label{cor21} Let $S={\cal POP}_n$. Then
$$
F(n;r)=
\begin{cases}
r{n\choose r}{n+r-1\choose n-1}-n(r-1){n\choose r},\,&\,n \geq r\geq 1; \\
1,\,&\,r=0.
\end{cases}$$
\end{corollary}

\begin{proof} \begin{eqnarray*} F(n;r) & = & \sum_{p=1}^{r}F(n;r,p)=
 n{n\choose r}+\sum_{p=2}^{r}{n\choose r}
{r\choose p}{n\choose p}p \,\,(r\geq 2) \\
& = &  n{n\choose r}+{n\choose r}\sum_{p=1}^{r}
{r\choose p}{n\choose p}p -rn{n\choose r} \\
 & = & r{n\choose r}\sum_{p=1}^{r}
{r-1\choose p-1}{n\choose p}-n(r-1){n\choose r} \\
& = & r{n\choose r}{n+r-1\choose r}-n(r-1){n\choose r}\,\,\,(by\,
Lemma\,\ref{lem2}).
 \end{eqnarray*}
Moreover, it is not difficult to see that $F(n;r_1)=n^2$ and
 $F(n;r_0)=1$. Hence the result follows. Alternatively,
 we can get the same result from $F(n;r) = \sum_{k=1}^{n}F(n;r,k)$.\end{proof}

 \begin{corollary}\label{cor22} Let $S={\cal POP}_n$. Then
$$
F(n;p)=
\begin{cases}
p 2^{n-p}{n\choose p}^2,\,&\,n \geq p > 1; \\
n(2^n-1),\,&\,p=1;\\
1,\,&\,p=0.
\end{cases}$$
\end{corollary}

\begin{proof} \begin{eqnarray*} F(n;p) & = & \sum_{r=p}^{n}F(n;r,p)=
\sum_{r=p}^{n}{n\choose r}
{r\choose p}{n\choose p}p \,\,(p\geq 2) \\
 & = & p{n\choose p}\sum_{r=p}^{n}{n\choose r}{r\choose p}
 = p{n\choose p}^2\sum_{r=p}^{n}{n-p\choose r-p}\\
& = & p2^{n-p}{n\choose p}^2.
 \end{eqnarray*}
It is not difficult
 to see that $F(n;p_1)=n(2^n-1)$ and $F(n;p_0)=1$. Hence the result
 follows. Alternatively, we can get the same result from
 $F(n;p) = \sum_{k=p}^{n}F(n;p,k)$.\end{proof}

 \begin{corollary}\label{cor23} Let $S={\cal POP}_n$. Then
$$
F(n;k)=
\begin{cases}
n\sum_{r=1}^{n}{n-1\choose r-1}{r+k-2\choose r-1}-(n-2)2^{n-1}-1,\,&\,n \geq k\geq 1; \\
1,\,&\,k=0.
\end{cases}$$
\end{corollary}

\begin{proof} \begin{eqnarray*} F(n;k) & = & \sum_{r=1}^{n}F(n;r,k)=
n+\sum_{r=2}^{n}[r{n\choose r}
{r+k-2\choose r-1}-(r-1){n\choose r}] \,\,(k\geq 2) \\
 & = & n+n\sum_{r=2}^{n}{n-1\choose r-1}
{r+k-2\choose r-1}-((n-2)2^{n-1}+1) \,\,\,(by\,
Lemma\,\ref{lem1})\\
& = & n\sum_{r=1}^{n}{n-1\choose r-1} {r+k-2\choose
r-1}-(n-2)2^{n-1}-1.
 \end{eqnarray*}
It is not difficult
 to see that $F(n;k_1)=n(2^n-1)$ and for convenience we set $F(n;k_0)=1$.
 Hence the result follows. Alternatively, we get
\begin{eqnarray*}F(n;k) & = &\sum_{p=1}^{k}F(n;p,k)
=(2^n-1)+\sum_{p=2}^{k}p{k-1\choose p-1}
{n\choose p}2^{n-p} \,\,(k\geq 2) \\
 & = & (2^n-1)+n\sum_{p=2}^{k}{k-1\choose p-1}
{n-1\choose p-1}2^{n-p}\\
& = & (2^n-1)+n\sum_{p=1}^{k}{k-1\choose p-1}
{n-1\choose p-1}2^{n-p}-n2^{n-1}\\
& = & n\sum_{p=1}^{k}{k-1\choose p-1} {n-1\choose
p-1}2^{n-p}-(n-2)2^{n-1}-1. \end{eqnarray*}\end{proof}

From the proof of Corollary $\ref{cor23}$ we deduce the
following non-trivial identity.

\begin{proposition} For all natural numbers $n$ and $k$ we have
$$\sum_{r=1}^{n}{n-1\choose r-1} {r+k-2\choose
r-1}=\sum_{r=1}^{k}{k-1\choose r-1} {n-1\choose r-1}2^{n-r}.$$
\end{proposition}

We can now deduce the order of ${\cal POP}_n$. The first
expression is \cite[Proposition 1.9]{Fer3}.

\begin{corollary} For all
natural number $n$ we have
\begin{eqnarray*}\mid {\cal POP}_n\mid & = &
1+n(2^n-1)+\sum_{p=2}^{n}p2^{n-p}{n\choose
p}^2\\
& = &1+n\sum_{r=1}^{n}{n-1\choose r-1} {n+r-1\choose
n-1}-n(n-2)2^{n-1}-n.\end{eqnarray*}
\end{corollary}

\begin{corollary}\label{cor24} Let $S={\cal OP}_n$. Then
$$
\begin{cases}
{k-1\choose p-1}{n\choose p}p,\,&\,n \geq k \geq p > 1; \\
\,\,1,\,&\,k=1\,or\,p=1.
\end{cases}$$
\end{corollary}

\begin{proof} The result follows by the substitution $r=n$ in
Proposition $\ref{prop1}$.
\end{proof}

\begin{corollary}\label{cor25}\cite[p. 198]{Cat} Let $S={\cal OP}_n$. Then
$$
F(n;p)=
\begin{cases}
p{n\choose p}^2,\,&\,n \geq p > 1; \\
n,\,&\,p=1.
\end{cases}$$
\end{corollary}

\begin{corollary}\label{cor26} Let $S={\cal OP}_n$. Then
$$
F(n;k)=
\begin{cases}
n{n+k-2\choose k-1}-(n-1),\,&\,n \geq k > 1; \\
1,\,&\,k=1.
\end{cases}$$
\end{corollary}

\begin{corollary}\cite[Theorem 4.3]{Mac} \& \cite[p. 194]{Cat} For any natural
number $n$ we have
$$\mid {\cal OP}_n\mid =\frac{n}{2}{2n\choose n}-n(n-1).$$
\end{corollary}

\begin{remark} The triangles of numbers $F_{POP}(n;r)$, $F_{POP}(n;p)$,
$F_{POP}(n;k)$, $F_{OP}(n;p)$ and $F_{OP}(n;k)$ are as at the time
of submitting this paper not in Sloane \cite{Slo}. However, note
that $F_{POP}(n,p_1)$ is \cite[\seqnum{A066524}]{Slo} and
$F_{OP}(n,k_1)$ is \cite[\seqnum{A002061}]{Slo}.
\end{remark}

{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}r&0&1&2&3&4&5&6&\sum F(n;r)=\mid {\cal POP}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&4&4&&&&&9
\\
\hline 3&1&9&27&24&&&&61
\\
\hline 4&1&16&96&208&128&&&449
\\
\hline 5&1&25&250&950&1325&610&&3161
\\
\hline 6&1&36&540&3120&7290&7416&2742&21145
\\
\hline
\end{array}$$}
\begin{center} Table 2.1 \end{center}

\bigbreak

{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}p&0&1&2&3&4&5&6&\sum F(n;p)=\mid {\cal POP}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&6&2&&&&&9
\\
\hline 3&1&21&36&3&&&&61
\\
\hline 4&1&60&288&96&4&&&449
\\
\hline 5&1&155&1600&1200&200&5&&3161
\\
\hline 6&1&378&7200&9600&3600&360&6&21145
\\
\hline
\end{array}$$}
\begin{center} Table 2.2 \end{center}


{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}k&0&1&2&3&4&5&6&\sum F(n;k)=\mid {\cal POP}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&3&5&&&&&9
\\
\hline 3&1&7&19&34&&&&61
\\
\hline 4&1&15&63&135&235&&&449
\\
\hline 5&1&31&191&471&911&1556&&3161
\\
\hline 6&1&63&543&1503&3183&5883&9969&21145
\\
\hline
\end{array}$$}
\begin{center} Table 2.3 \end{center}


{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}p&1&2&3&4&5&6&7&\sum F(n;p)=\mid {\cal OP}_n \mid
 \\ \hline 1&1&&&&&&&1
 \\ \hline 2&2&2&&&&&&4
\\
\hline 3&3&18&3&&&&&24
\\
\hline 4&4&72&48&4&&&&128
\\
\hline 5&5&200&300&100&5&&&610
\\
\hline 6&6&450&1200&900&180&6&&2742
\\
\hline 7&7&882&3675&4900&2205&294&7&11970
\\
\hline
\end{array}$$}
\begin{center} Table 2.4 \end{center}


{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}k&1&2&3&4&5&6&7&\sum F(n;k)=\mid {\cal OP}_n \mid
 \\ \hline 1&1&&&&&&&1
 \\ \hline 2&1&3&&&&&&4
\\
\hline 3&1&7&16&&&&&24
\\
\hline 4&1&13&37&77&&&&128
\\
\hline 5&1&21&71&171&346&&&610
\\
\hline 6&1&31&121&331&751&1507&&2742
\\
\hline 7&1&43&190&582&1464&3228&6462&11970
\\
\hline
\end{array}$$}
\begin{center} Table 2.5 \end{center}

\bigskip

\section{Orientation-Preserving or Reversing Partial Transformations}\label{sec3}

Let $a=(a_1,a_2, \ldots,a_t)$ be a sequence of $t$ ($t>0$) elements
from the chain $X_n$. We say that $a$ is {\em anti-cyclic} if there
exists no more than one index $i \in \{1,2, \ldots,t\}$ such that
$a_i < a_{i+1}$, where $a_{t+1}$ denotes $a_1$. For a partial
transformation $\alpha$ of $X_n$, suppose that $\dom \alpha =
\{a_1,a_2, \ldots,a_t\}$, with $t \geq 0$ and $a_1<a_2< \ldots
<a_t.$ We say that $\alpha$ is {\em orientation-reversing} if
$(a_1\alpha,a_2\alpha, \ldots,a_t\alpha)$ is anti-cyclic. The
semigroups of orientation-preserving or reversing full and partial
transformations of $X_n$ will be denoted by ${\cal OR}_n$ and ${\cal
POR}_n$, respectively.


\begin{remark}
\label{rem4} For $p=1,2$ every orientation-preserving transformation
is also orientation-reversing but distinct otherwise \cite[Lemma
1.1]{Cat}. However, there is a bijection between the set of
orientation-preserving transformations and that of
orientation-reversing transformations \cite[Lemma 5.1]{Cat}.
\end{remark}

The proofs of all the results in this section are similar
to the proofs of the corresponding results in Section $\ref{sec2}$,
taking into account Remark $\ref{rem4}$.

\begin{proposition}\label{prop2} Let $S = {\cal POR}_n$. Then
$$
F(n;r,p,k)= \left\{
\begin{array}{lll}
2{n\choose r}{k-1\choose p-1}{r\choose p}p,\,&\,n \geq r,k
\geq p > 2; \\
2(k-1){n\choose r}{r\choose 2},\,&\,n \geq r,k
\geq p = 2; \\
{n\choose r},\,&\,r=1\,or\,k=1\,or\, p=1.
\end{array}
\right.
$$
\end{proposition}

\begin{corollary}\label{cor36} Let $S={\cal POR}_n$. Then
$$
F(n;r,p)= \left\{
\begin{array}{llll}
2{n\choose r}{n\choose p}{r\choose p}p,\,&\,r\geq p > 2; \\
2{n\choose r}{r\choose 2}{n\choose 2},\,&\,n\geq r\geq p=2; \\
n{n\choose r},\,&\,r=1\,or\,p=1.
\end{array}
\right.
$$
\end{corollary}

\begin{corollary}\label{cor37} Let $S={\cal POR}_n$. Then
$$F(n;r,k)= \left\{
\begin{array}{lllll}
{n\choose r}[2r{r+k-2\choose k-1}-(2r-1)
-2(k-1){r\choose 2}],\,&\,r,k > 2; \\
(2k-1){n\choose 2},\,&\,k\geq r=2; \\
{n\choose r}+2{n\choose r}{r\choose 2},\,&\,r\geq k=2; \\
{n\choose r},\,&\,r=1\,or\,k=1.
\end{array}
\right.$$
\end{corollary}

\begin{corollary}\label{cor38} Let $S={\cal POR}_n$. Then
$$F(n;p,k)= \left\{
\begin{array}{llll}
p2^{n-p+1}{k-1\choose p-1}{n\choose p}p,\,&\,k\geq p > 2; \\
2^{n-1}{n\choose 2}+2^n-1,\,&\,k=2; \\
(k-1)2^{n-1}{n\choose 2},\,&\,p=2; \\
2^n-1,\,&\,k=1\,or\,p=1.
\end{array}
\right.$$
\end{corollary}

\begin{corollary}\label{cor39} Let $S={\cal POR}_n$. Then
$$F(n;r)= 2r{n\choose r}{n+r-1\choose n-1}-n(2r-1){n\choose r}
-2{n\choose r}{r\choose 2}{n\choose 2},\,for\,r \geq 1.$$
\end{corollary}

\begin{corollary}\label{cor40} Let $S={\cal POR}_n$. Then
$$
F(n;p)= \left\{
\begin{array}{lll}
p 2^{n-p+1}{n\choose p}^2,\,&\,p > 2; \\
2^{n-1}{n\choose 2}^2,\,&\,p=2; \\
n(2^n-1),\,&\,p=1.
\end{array}
\right.
$$
\end{corollary}

\begin{corollary}\label{cor41} Let $S={\cal POR}_n$. Then
\begin{eqnarray*} F(n;k) & = & 2n\sum_{r=1}^{n}{n-1\choose r-1}{r+k-2\choose
r-1}-(n-1)2^n-1-(k-1)2^{n-1}{n\choose 2} \\
 & = & 2n\sum_{p=1}^{k}{k-1\choose p-1}{n-1\choose p-1}2^{n-p}
 -(n-1)2^n-1-(k-1)2^{n-1}{n\choose 2},
 \end{eqnarray*}
\noindent for $k\geq 1$.
\end{corollary}

We can now deduce the order of ${\cal POR}_n$. The first
expression is \cite[Proposition 1.10]{Fer3}.

\begin{corollary} For all natural number $n$ we have
\begin{eqnarray*}\mid {\cal POR}_n\mid & = &
1+n(2^n-1)=2^{n-1}{n\choose 2}^2+\sum_{p=3}^{n}p2^{n-p+1}{n\choose
p}^2\\
& = &1+2n\sum_{r=1}^{n}{n-1\choose r-1} {n+r-1\choose
n-1}-2^{n-3}n(n-1)(n^2-n+8)-n.\end{eqnarray*}
\end{corollary}

\begin{corollary}\label{cor42} Let $S={\cal OR}_n$. Then
$$F(n;p,k)= \left\{
\begin{array}{llll}
2{k-1\choose p-1}{n\choose p}p,\,&\,k\geq p > 2; \\
{k-1\choose p-1}{n\choose p}p,\,&\,k\geq p=2;\\
1,\,&\,k=1\, or\,p=1.
\end{array}
\right.$$
\end{corollary}

\begin{corollary}\label{cor43} Let $S={\cal OR}_n$. Then
$$
F(n;p)= \left\{
\begin{array}{ll}
2p{n\choose p}^2,\,&\,p > 2; \\
2{n\choose 2}^2,\,&\,p=2; \\
n,\,&\,p=1.
\end{array}
\right.
$$
\end{corollary}

\begin{corollary}\label{cor44} Let $S={\cal OR}_n$. Then
$$F(n;k)=2n{n+k-2\choose k-1}-2(k-1){n\choose 2}-2n+1,$$
\noindent for $k\geq 1$.
\end{corollary}

\begin{corollary} \cite[Theorem 5.2]{Mac} \& \cite[Theorem 5.5]{Cat}
For any natural number $n$ we have
$$\mid {\cal OR}_n\mid=n{2n\choose n}-n^2(n^2-2n+5)/2+n.$$
\end{corollary}

\begin{remark} The triangles of numbers $F_{POR}(n;r)$, $F_{POR}(n;p)$,
$F_{POR}(n;k)$, $F_{OR}(n;p)$ and $F_{OR}(n;k)$ are as at the time
of submitting this paper not in Sloane \cite{Slo}. However, note
that $F_{POR}(n;r_1)$ is \cite[\seqnum{A000290}]{Slo},
$F_{POR}(n;p_1)$ is \cite[\seqnum{A066524}]{Slo}, $F_{POR}(n;k_1)$
is \cite[\seqnum{A000225}]{Slo}, $F_{OR}(n;p_1)$ is
\cite[\seqnum{A163102}]{Slo} and $F_{OR}(n;k_1)$ is
\cite[\seqnum{A002061}]{Slo}.
\end{remark}

{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}r&0&1&2&3&4&5&6&\sum F(n;r)=\mid {\cal POR}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&4&4&&&&&9
\\
\hline 3&1&9&27&27&&&&64
\\
\hline 4&1&16&96&256&180&&&549
\\
\hline 5&1&25&250&1250&2025&1015&&4566
\\
\hline 6&1&36&540&4320&11790&12996&5028&34711
\\
\hline
\end{array}$$}
\begin{center} Table 3.1 \end{center}

\bigskip

{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}p&0&1&2&3&4&5&6&\sum F(n;p)=\mid {\cal POR}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&6&2&&&&&9
\\
\hline 3&1&21&36&6&&&&64
\\
\hline 4&1&60&288&192&8&&&549
\\
\hline 5&1&155&1600&2400&400&10&&4566
\\
\hline 6&1&378&7200&19200&7200&720&12&34711
\\
\hline
\end{array}$$}
\begin{center} Table 3.2 \end{center}


{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}k&0&1&2&3&4&5&6&\sum F(n;k)=\mid {\cal POR}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&3&5&&&&&9
\\
\hline 3&1&7&19&37&&&&64
\\
\hline 4&1&15&63&159&311&&&549
\\
\hline 5&1&31&191&591&1311&2441&&4566
\\
\hline 6&1&63&543&1983&4863&9783&17475&34711
\\
\hline
\end{array}$$}
\begin{center} Table 3.3 \end{center}


{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}p&1&2&3&4&5&6&7&\sum F(n;p)=\mid {\cal OR}_n \mid
 \\ \hline 1&1&&&&&&&1
 \\ \hline 2&2&2&&&&&&4
\\
\hline 3&3&18&6&&&&&27
\\
\hline 4&4&72&96&8&&&&180
\\
\hline 5&5&200&600&200&10&&&1015
\\
\hline 6&6&450&2400&1800&360&12&&5028
\\
\hline 7&7&882&7350&9800&4410&588&14&23051
\\
\hline
\end{array}$$}
\begin{center} Table 3.4 \end{center}


{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}k&1&2&3&4&5&6&7&\sum F(n;k)=\mid {\cal OR}_n \mid
 \\ \hline 1&1&&&&&&&1
 \\ \hline 2&1&3&&&&&&4
\\
\hline 3&1&7&19&&&&&27
\\
\hline 4&1&13&49&117&&&&180
\\
\hline 5&1&21&101&281&611&&&1015
\\
\hline 6&1&31&181&571&1381&2863&&5028
\\
\hline 7&1&43&295&1037&2759&6245&12671&23051
\\
\hline
\end{array}$$}
\begin{center} Table 3.5 \end{center}

\bigskip

\section{Orientation-Preserving or Orientation-Reversing
Partial One-to-one Transformations}\label{sec4}

The semigroups of orientation-preserving and orientation-preserving
or reversing partial one-to-one transformations of $X_n$  will be
denoted by ${\cal POPI}_n$ and ${\cal PORI}_n$, respectively.

\begin{proposition}\label{prop5} Let $S = {\cal POPI}_n$. Then
$ F(n;p,k)= {n\choose p}{k-1\choose p-1}p,\,for\,n \geq k \geq p >
0.$
\end{proposition}


\begin{proof} First observe that the $p$ elements of $\dom \alpha$ can be
chosen from $X_n$ in ${n\choose p}$ ways, and since $k$ is the
maximum element in $\mbox{Im }\alpha$ then the remaining $p - 1$
elements of $\mbox{Im }\alpha$ can be chosen from $\{1,2, \ldots,
k-1\}$ in ${k-1\choose p-1}$ ways. Finally, observe that if $p>0$,
then the $p$ elements of $\dom \alpha$ can be tied to the $p$ images
in a one-to-one fashion (whilst preserving the orientation), in $p$
ways. The result now follows. \end{proof}


The following corollaries can be deduced in exactly the same manner
as their corresponding results in Section $\ref{sec2}$:

\begin{corollary}\label{cor7} Let $S = {\cal POPI}_n$. Then
$$
F(n;p)= \left\{
\begin{array}{ll}
{n\choose p}^2p,\,&\,n\geq p > 1; \\
n^2,\,&\,p=1.
\end{array}
\right.
$$
\end{corollary}

\begin{corollary}\label{cor8} Let $S = {\cal POPI}_n$. Then
$F(n;k)= n{n+k-2\choose k-1},\,for\,n \geq k \geq 1.$
\end{corollary}

\begin{corollary}\label{cor9} Let $S = {\cal POPI}_n$. Then
$F(n;k_n)= n{2n-2\choose n-1},\,for\,n \geq 1.$
\end{corollary}

\begin{corollary} \cite[Corollary 2.8]{Fer1} For any natural number $n$ we have
$$\mid {\cal POPI}_n\mid=1+ \frac{n}{2}{2n\choose n}.$$
\end{corollary}

\begin{proposition}\label{prop6} Let $S = {\cal PORI}_n$. Then
$$
F(n;p,k)= \left\{
\begin{array}{ll}
2{n\choose p}{k-1\choose p-1}p,\,&\,n \geq k \geq p > 2; \\
n^2,\,&\,k=2;\\
2(k-1){n\choose 2},\,&\,p=2;\\
n,\,&\,k=1\,or\, p=1.
\end{array}
\right.
$$
\end{proposition}

\begin{proof} The proof is similar to that of Proposition $\ref{prop5}$. \end{proof}

\begin{corollary}\label{cor10} Let $S = {\cal PORI}_n$. Then
$$
F(n;p)= \left\{
\begin{array}{ll}
2{n\choose p}^2p,\,&\,n\geq p > 2; \\
2{n\choose 2}^2,\,&\,p=2;\\
n^2,\,&\,p=1.
\end{array}
\right.
$$
\end{corollary}

\begin{corollary}\label{cor11} Let $S = {\cal PORI}_n$. Then
$$F(n;k)= 2n{n+k-2\choose n-1}-n-n(n-1)(k-1),\, for\,n\geq k > 0.$$
\end{corollary}

\begin{corollary}\label{cor12} Let $S = {\cal PORI}_n$. Then
$$F(n;k_n)= 2n{2n-2\choose n-1}-n-n(n-1)^2,\, for\, n \geq 1.$$
\end{corollary}

\begin{corollary} \cite[Proposition 5.2]{Fer2} For any natural number $n$ we have
$$\mid {\cal PORI}_n\mid=1+n{2n\choose n}-n^2(n^2-2n+3)/2.$$
\end{corollary}

\begin{remark} The triangular arrays of numbers  $F_{POPI}(n;p)$,
$F_{POPI}(n;k)$, $F_{PORI}(n;p)$ and $F_{PORI}(n;k)$ are as at the
time of submitting this paper not in Sloane \cite{Slo}. However,
note that $F_{PORI}(n;p_2)$ is \cite[\seqnum{A163102}]{Slo}.
\end{remark}

\bigskip

{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}p&0&1&2&3&4&5&6&\sum F(n;p)=\mid {\cal POPI}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&4&2&&&&&7
\\
\hline 3&1&9&18&3&&&&31
\\
\hline 4&1&16&72&48&4&&&141
\\
\hline 5&1&25&200&300&100&5&&631
\\
\hline 6&1&36&450&1200&900&180&6&2773
\\
\hline
\end{array}$$}
\begin{center} Table 4.1 \end{center}

\bigbreak

{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}k&0&1&2&3&4&5&6&\sum F(n;k)=\mid {\cal POPI}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&2&4&&&&&7
\\
\hline 3&1&3&9&18&&&&31
\\
\hline 4&1&4&16&40&80&&&141
\\
\hline 5&1&5&25&75&175&350&&631
\\
\hline 6&1&6&36&126&336&756&1512&2773
\\
\hline
\end{array}$$}
\begin{center} Table 4.2 \end{center}


{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}p&0&1&2&3&4&5&6&\sum F(n;p)=\mid {\cal PORI}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&4&2&&&&&7
\\
\hline 3&1&9&18&6&&&&34
\\
\hline 4&1&16&72&96&8&&&193
\\
\hline 5&1&25&200&600&200&10&&1036
\\
\hline 6&1&36&450&2400&1800&360&12&5059
\\
\hline
\end{array}$$}
\begin{center} Table 4.3 \end{center}

{\tt
$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 \,\,\,\,\,n{\backslash}k&0&1&2&3&4&5&6&\sum F(n;k)=\mid {\cal PORI}_n \mid
 \\ \hline 0&1&&&&&&&1
 \\ \hline 1&1&1&&&&&&2
\\
\hline 2&1&2&4&&&&&7
\\
\hline 3&1&3&9&21&&&&34
\\
\hline 4&1&4&16&52&120&&&193
\\
\hline 5&1&5&25&105&285&615&&1036
\\
\hline 6&1&6&36&166&576&1386&2868&5059
\\
\hline
\end{array}$$}
\begin{center} Table 4.4 \end{center}
\medskip

\section{Acknowledgements}

I would like to thank the
anonymous referee whose corrections helped remove many errors and
suggestions that greatly improve the clarity of some statements in
the paper.

\medskip

\begin{thebibliography}{99}

\bibitem{Cat} P. M. Catarino and P. M. Higgins, The monoid
of orientation-preserving mappings on a chain, {\em Semigroup Forum}
{\bf 58} (1999), 190--206.

\bibitem{Fer1} V. H. Fernandes, The monoid of all injective
orientation-preserving partial transformations on a finite chain,
{\em Comm. Algebra} {\bf 32} (2000), 3401--3426.

\bibitem{Fer2} V. H. Fernandes, G. M. S. Gomes, and M. M. Jesus,
 Presentations for some monoids of injective partial
transformations on a finite chain, {\em Southeast Asian Bull. Math.}
{\bf 28} (2004),  903--918.

\bibitem{Fer3} V. H. Fernandes, G. M. S. Gomes, and M. M. Jesus,
Congruences on monoids of transformations preserving the orientation
of a finite chain, {\em J. Algebra} {\bf 321} (2009), 743--757.

\bibitem{Fer4} V. H. Fernandes, G. M. S. Gomes, and M. M. Jesus,
The cardinal and idempotent number of various monoids of
transformations on a finite chain, submitted.

\bibitem{Gan} O. Ganyushkin and V. Mazorchuk, {\em Classical Finite
Transformation Semigroups: An Introduction}, Springer, 2009.

\bibitem{Hig1} P. M. Higgins, {\em Techniques of Semigroup Theory},
Oxford University Press, 1992.

\bibitem{Hig2} P. M. Higgins, Combinatorial results for semigroups of
order-preserving mappings, {\em Math. Proc. Camb. Phil. Soc.}, {\bf
113} (1993), 281--296.

\bibitem{How1} J. M. Howie, Combinatorial and probabilistic results in
transformation semigroups, in Masami Ito and H. J\"urgensen,
eds., {\em Words, Languages and Combinatorics}, World Sci. Publ.,
1994, pp.\ 200--206.

\bibitem{How2} J. M. Howie, {\em Fundamentals of Semigroup Theory,} 
Clarendon Press, 1995.

\bibitem{Lar1} A. Laradji and A. Umar, On certain finite semigroups of
order-decreasing transformations I, {\em Semigroup Forum}, {\bf 69}
(2004), 184--200.

\bibitem{Lar2} A. Laradji and A. Umar, Combinatorial results for semigroups
of order-preserving partial transformations, {\em J.\ Algebra},
{\bf 278} (2004), 342--359.

\bibitem{Lar3} A. Laradji and A. Umar, Combinatorial results for semigroups
of order-decreasing partial transformations, {\em J. Integer Seq.},
{\bf 7} (2004), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Umar/um.html}{Article 04.3.8}.

\bibitem{Lar4} A. Laradji and A. Umar, Combinatorial results for semigroups
of order-preserving full transformations, {\em Semigroup Forum},
{\bf 72} (2006), 51--62.

\bibitem{Lar5} A. Laradji and A. Umar, Some combinatorial properties of the
symmetric monoid, {\em Int. Journal of Alg. and Computations}, (to
appear).

\bibitem{Mac} D. B. McAlister, Semigroups generated by a group
and an idempotent, {\em Comm. Algebra}, {\bf 26} (1998), 515--547.

\bibitem{Rio} J. Riordan, {\em Combinatorial Identities}, John Wiley
and Sons, 1968.

\bibitem{Slo} N.\ J.\ A. Sloane, {\em The On-Line Encyclopedia of Integer
Sequences}, \href{http://oeis.org}{\tt http://oeis.org}.

\bibitem{Uma1} A. Umar, Some combinatorial problems in the theory of
symmetric inverse semigroups, {\em Algebra Discrete Math.}, {\bf 9} (2010),
115--126.

\bibitem{Uma2} A. Umar, Some combinatorial problems in the theory of
partial transformation semigroups, submitted.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary
20M18; Secondary 20M20, 05A10, 05A15.

\noindent \emph{Keywords: } full transformation, partial
transformation,  partial one-to-one transformation,
orientation-preserving transformation, orientation-reversing transformation,
breadth, height, right waist, left waist, cyclic
sequence, anti-cyclic sequence.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000225},
\seqnum{A000290}, \seqnum{0002061}, \seqnum{066524}, and
\seqnum{A163102}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 19 2010;
revised version received  July 9 2011.
Published in {\it Journal of Integer Sequences}, September 5 2011.

\bigskip
\hrule
\bigskip

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


\end{document}