\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{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}

\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 
Combinatorial Results for Semigroups of Order-Decreasing
Partial Transformations
}
\vskip 1cm
\large
A. Laradji and A. Umar \\
Department of Mathematical Sciences\\
King Fahd University of Petroleum and Minerals\\
Dhahran 31261 \\
Saudi Arabia \\
\href{mailto:aumar@kfupm.edu.sa}{\tt aumar@kfupm.edu.sa} \\
\end{center}


\begin{abstract}
Let ${\cal PC}_n$ be the semigroup of all decreasing and
order-preserving partial transformations of a finite chain.  It is
shown that $|{\cal PC}_n| = r_n$, where $r_n$ is the large (or
double) Schr\"{o}der number. Moreover, the total number of
idempotents of ${\cal PC}_n$ is shown to be $(3^n+1)/2$.
\end{abstract}


%\documentclass[amsfonts,12pt]{article}
%\usepackage{latexsym,epsfig,graphpap,graphics,amsmath}
%\usepackage{amssymb}
 \def \ed{\end{document}}
%\usepackage{amsmath}
%\newcounter{corollary}
%\newcounter{proposition}
%\newcounter{definition}
%\newcounter{remark}
%\newcounter{lemma}
%\newcounter{theorem}
%\textheight=9.85in %8.85in
%\textwidth=15.5cm \oddsidemargin=.175in \footskip=.3in
%\topmargin=-.25in
%\textheight=25.25cm %8.85in
%\topmargin=-.55in
\renewcommand{\theequation}{\thesection.\arabic{equation}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usepackage{graphicx}
%\usepackage{amsmath}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Created=Mon Sep 16 11:21:11 2002}
%TCIDATA{LastRevised=Mon Sep 16 11:21:32 2002}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="General\Blank
%Document">}
%TCIDATA{CSTFile=LaTeX article (bright).cst}

%\newtheorem{acknowledgement}[theorem]{Acknowledgement}
%\newtheorem{theorem}[theorem]{Theorem}
%\newtheorem{algorithm}[theorem]{Algorithm}
%\newtheorem{axiom}[theorem]{Axiom}
%\newtheorem{case}[theorem]{Case}
%\newtheorem{claim}[theorem]{Claim}
%\newtheorem{conclusion}[theorem]{Conclusion}
%\newtheorem{condition}[theorem]{Condition}
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{criterion}[theorem]{Criterion}
%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{example}[theorem]{Example}
%\newtheorem{exercise}[theorem]{Exercise}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{notation}[theorem]{Notation}
%\newtheorem{problem}[theorem]{Problem}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{solution}[theorem]{Solution}
%\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof] {\textbf{#1.}}{}
%\textheight=9.85in \textwidth=15.5cm \oddsidemargin=.175in
%\footskip=.3in \topmargin=-.25in \textheight=25.25cm
%\topmargin=-.55in
%\textheight=9.85in %8.85in
%\textwidth=15.5cm \oddsidemargin=.175in \footskip=.3in
%\topmargin=-.25in
%\renewcommand{\thetheorem}{\thesection.\arabic{theorem}}
%\renewcommand{\theproposition}{\thesection.\arabic{proposition}}
%\renewcommand{\thecorollary}{\thesection.\arabic{corollary}}
%\renewcommand{\thelemma}{\thesection.\arabic{lemma}}
%\renewcommand{\theremark}{\thesection.\arabic{remark}}
%one
%documentclass[amsfonts,12pt]{article}
%\usepackage{amssymb}
%\usepackage{amssymb}
%\usepackage{amsmath}
%\textheight=9.85in %8.85in
%\textwidth=15.5cm \oddsidemargin=.175in \footskip=.3in
%\topmargin=-.25in
%\textheight=25.25cm %8.85in
%\topmargin=-.55in
\renewcommand{\theequation}{\thesection.\arabic{equation}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usepackage{graphicx}
%\usepackage{amsmath}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Created=Mon Sep 16 11:21:11 2002}
%TCIDATA{LastRevised=Mon Sep 16 11:21:32 2002}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="General\Blank
%Document">}
%TCIDATA{CSTFile=LaTeX article (bright).cst}

%\textheight=9.85in \textwidth=15.5cm \oddsidemargin=.175in
%\footskip=.3in \topmargin=-.25in \textheight=25.25cm
%\topmargin=-.55in
%\usepackage{amssymb}

%\begin{document}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}


%\baselineskip=20pt

\section{Introduction and Preliminaries}
\setcounter{equation}{0} 
Consider a finite chain, say $X_n =
\{1,2,\ldots,n\}$ under the natural ordering and let $T_n$ and
$P_n$ be the full transformation semigroup and the semigroup of
all partial transformations on $X_n$, under the usual composition,
respectively.  We shall call a partial transformation $\alpha: X_n
\rightarrow X_n$, {\em order-decreasing (order-increasing)} or
simply {\em decreasing (increasing)} if $x\alpha \leq x \,(x\alpha
\geq x)$ for all $x$ in $\mbox{Dom }\alpha$, and $\alpha$ is {\em
order-preserving} if $x\leq y$ implies $x\alpha \leq y\alpha$ for
$x,y$ in $\mbox{Dom }\alpha$. The semigroup of all decreasing full
transformations is denoted by $D_n$, while the semigroup of all
order-preserving full transformations is denoted by ${\cal O}_n$,
and $D_n \cap {\cal O}_n$ is denoted by ${\cal C}_n$.

Various enumerative problems of an essentially combinatorial
nature have been considered for certain classes of semigroups of
transformations. For example, Howie \cite{Howie2} showed that the
order and number of idempotents of ${\cal O}_n$ are, respectively,
\[
|{\cal O}_n| =  \left(\begin{array}{c} 2n-1\\
n-1\end{array} \right)  \mbox{ and } |E({\cal O}_n)| = F_{2n},\]

\noindent where $F_{2n}$ is the alternate Fibonacci number given
by $F_1 = F_2 = 1$. More recently, Higgins \cite{Higgins2} showed
in particular, that $|{\cal C}_n|$ is the $n$-th Catalan number
given by
\[
|{\cal C}_n| = \frac{1}{n+1} \left(\begin{array}{c} 2n\\
n\end{array} \right)
\]
and  $|E({\cal C}_n)| =2^{n-1}$. Further combinatorial properties
for ${\cal C}_n$ were investigated by Laradji and Umar
\cite{Laradji}, where they showed that the number of maps in
${\cal C}_n$ such that $|\mbox{Im }\alpha| = r$ is the triangle of
Narayana \cite[A001263]{Sloane}  numbers given by
\[
|\{\alpha\in {\cal C}_n: |\mbox{Im } \alpha| = r \}|=
\frac{1}{n-r+1}\left(\begin{array}{c} n-1 \\ r-1 \\ \end{array}
\right)\left(\begin{array}{c} n \\ r \end{array} \right).
\]
This paper investigates combinatorial properties of ${\cal PC}_n$,
the semigroup of all decreasing and order-preserving partial
transformations, along the lines of \cite{Laradji}. An alternative
approach to finding the order and number of idempotents in ${\cal
PC}_n$ is given in \cite{Laradji2}, however, the advantage of the
approach given in this paper is that we get along the way some
known triangular arrays of integers as well as some new ones,
which are not yet listed in \cite{Sloane}. Ironically, it is this
paper that motivated \cite{Laradji2} and \cite{Laradji3}. The
following is a list (which is by no means exhaustive) of papers
and books \cite{Clifford, Garba, Garba2, Gomes, Higgins, Higgins2,
Howie, Howie2, Tainiter, Umar, Umar2} each of which contains some
interesting combinatorial results pertaining to semigroups of
transformations. Initially, the only reference we could find about
${\cal PC}_n$ is Higgins \cite[theorem 4.2]{Higgins3}, where it is
shown that any finite ${\cal R}$ -trivial semigroup $S$ divides
some monoid ${\cal PC}_n$. However, the referee drew our attention
to \cite{Popova} and \cite{Solomon} where presentations of ${\cal
PC}_n$ on a chain and trees, respectively, were studied and also
to \cite{Pin} where ${\cal PC}_n$ is studied in connection with
theoretical computer science.

In Section 2, we give the necessary definitions that we need in
the paper.  In Section 3, we obtain the order of ${\cal PC}_n$ as
the large or double Schr\"{o}der number \cite{Pergola}, via some
natural equivalences on ${\cal P}{\cal C}_n$. In Section 4, we
show that the set of all idempotents of ${\cal PC}_n$ is of
cardinality $(3^n+1)/2$, again, via some natural equivalences on
$E({\cal PC}_n)$.

For standard terms and concepts in transformation semigroup theory
see \cite{Higgins} or \cite{Howie}.  We now recall some
definitions and notations to be used in the paper.  Consider $X_n
= \{1,2,\ldots,n\}$ and let $\alpha: X_n\rightarrow X_n$ be a
partial transformation. We shall denote by $\mbox{Dom }\alpha$ and
$\mbox{Im }\alpha$, the {\em domain} and {\em image set} of
$\alpha$, respectively. The semigroup $P_n$, of all partial
transformations contains two important subsemigroups which have
been studied recently.  They are $PD_n$ and ${\cal PO}_n$ the
semigroups of all order-decreasing and order-preserving partial
transformations, respectively (see \cite{Umar3} and \cite{Garba2,
Gomes}). Now let
\begin{equation}
{\cal PC}_n = PD_n \cap {\cal PO}_n
\end{equation}
be the semigroup of all decreasing and order-preserving partial
transformations of $X_n$.

\section{The order of ${\cal PC}_n$}

\setcounter{equation}{0} 
%\setcounter{lemma}{0}
%\setcounter{theorem}{0} \setcounter{corollary}{0}
%\setcounter{proposition}{0} \setcounter{remark}{0} 
Our main
objective in this section is to obtain a formula for $|{\cal
PC}_n|$. We initiate our investigation by considering two natural
equivalences on ${\cal PC}_n$. The first equivalence is defined by
equality of widths ({\em width} of $\alpha : = |\mbox{Dom
}\alpha|)$, while the second equivalence is defined by equality of
waists ({\em waist} of $\alpha : = \max(\mbox{Im }\alpha))$.
Taking the intersection of these two equivalences leads to the
following definition of $f(n,r,k)$ as
\begin{equation}
f(n,r,k) = |\{\alpha\in {\cal PC}_n: |\mbox{Dom }\alpha| = r
\wedge \max(\mbox{Im }\alpha) = k\}|.
\end{equation}
Then clearly we have
\[
f(n,0,0) = 1, f(n,n,1) = 1
\]
and
\[
f(n,r,0) = 0 \mbox{ (if } r > 0), f(n,0,k) = 0 \,(\mbox{if } k >
0).
\]
Slightly less clearly, we have
\begin{equation}
f(n,1,k) = n-(k-1) = n - k + 1
\end{equation}
and
\begin{equation}
f(n,r,1) = \left(\begin{array}{c} n \\ r \end{array} \right)
\end{equation}
In fact, $f(n,1,k)$ corresponds to the number of maps $\alpha$ (in
${\cal PC}_n)$ with singleton domain and hence $\mbox{Im }\alpha =
\{k\}$. Since by the order-decreasing property, $x\in \mbox{Dom
}\alpha$ implies $x\in \{k,k+1, \ldots, n\}$, the result now
follows. As for $f(n,r,1)$, it corresponds to all subsets of $X_n$
of size $r$. A more general result is
\begin{lemma}
For all $n\geq r, k \geq 0$, we have
\[
f(n,r,k) = f(n-1,r,k) + \sum^k_{t=0} f(n-1, r-1, t).
\]
\end{lemma}
\begin{proof}{}
Essentially there are two cases to consider: $n\not\in \mbox{Dom
}\alpha$ and $n\in \mbox{Dom }\alpha$. In the former case there
are clearly $f(n-1,r,k)$ maps of this type.  In the latter case,
since $n\alpha = k$, it is not difficult to see that there are
\[
\sum^k_{t=0} f(n-1, r-1, t)\] maps of this type. Hence the result
follows.
\end{proof}

A closed formula for $f(n,r,k)$ is possible, but before we propose
this formula we would like to state this lemma from \cite[lemma
3.3]{Laradji} which is obtained by combining equations (3) and
(3b) from \cite[p.~8]{Riordan}.
\begin{lemma}
For any $c\in {\mathbb R}$, and $q,m\in {\mathbb N}\cup \{0\}$, we
have
\[
\sum^m_{j=0} (c-j) \left(\begin{array}{c} q+j \\ j \end{array}
\right) = (c-m-1) \left(\begin{array}{c} m+q+1\\ m \end{array}
\right) + \left(\begin{array}{c} m+q+2 \\ m \end{array} \right).
\]
\end{lemma}

\begin{proposition}
Let $f(n,r,k)$ be as defined in (2.1). Then for $n \geq r, k > 0$,
we have
\begin{eqnarray*}
f(n,r,k)  =  \frac{n-k+1}{r} \left(\begin{array}{c} n-1 \\ r-1
\end{array} \right) \left(\begin{array}{c} k+r-2\\ r-1 \end{array}
\right)
 =  \frac{n-k+1}{n} \left(\begin{array}{c} n \\ r \end{array}
\right) \left(\begin{array}{c} k+r-2\\ r-1 \end{array} \right).
\end{eqnarray*}
\end{proposition}
\begin{proof}{}
The proof is by induction, and by virtue of (2.2) and (2.3) which
agree both with the assertion we may suppose that the result is
true for all $1 \leq r, k \leq n$. We now prove that it is true
for all $1 \leq r, k \leq n+1$. By Lemma 2.1 and the induction
hypothesis successively, we have
\begin{eqnarray*}
f(n+1,r,k) & = & f(n,r,k) + \sum^k_{t=0} f(n,r-1,t)\\
& = & \frac{n-k+1}{n} \left(\begin{array}{c} n \\ r\end{array}
\right) \left(\begin{array}{c} k+r-2\\ r-1 \end{array} \right) +
\sum^k_{t=0} \frac{n-t+1}{n} \left(\begin{array}{c} n \\ r-1
\end{array} \right) \left(\begin{array}{c}
r+t-3\\ r-2 \end{array} \right)\\
& = & \frac{1}{n}\left\{ \frac{n!(n-k+1)}{(n-r)!r(r-1)!}
\left(\begin{array}{c} k+r-2\\ r-1 \end{array} \right) +
(n+1)\left(\begin{array}{c} n\\ r-1 \end{array} \right)
\sum^k_{t=1} \left(\begin{array}{c}
r+t-3 \\ r-2 \end{array} \right) \right.\\
&& \left. - \left(\begin{array}{c} n \\ r-1 \end{array} \right)
\sum^k_{t=1}t\left(\begin{array}{c}
r+t-3\\ r-2 \end{array} \right)\right\} \\
& = & \frac{1}{n} \left(\begin{array}{c} n \\ r-1 \end{array}
\right)\left\{ \frac{n-r+1}{r} (n-k+1)\left(\begin{array}{c}
k+r-2\\ r-1 \end{array} \right) + (n+1) \sum^{k-1}_{t=0}
\left(\begin{array}{c}
r-2+t\\ r-2\end{array} \right)\right.\\
& & \left. - \sum^{k-1}_{t=0} (t+1)\left( \begin{array}{c} r-2+t\\
r-2
\end{array} \right)\right\}. \\
& = & \frac{1}{n} \left(\begin{array}{c} n \\ r-1 \end{array}
\right) \left\{ \frac{(n-r+1)(n-k+1)}{r} \left(\begin{array}{c}
k+r-2\\ r-2 \end{array} \right) \right.\\
&& \left.   + \sum^{k-1}_{t=0} (n-t)\left(\begin{array}{c} r-2+t\\
r-2 \end{array} \right)\right\}.
\end{eqnarray*}
However, by Lemma 2.2
\[
\sum^{k-1}_{t=0} (n-t) \left(\begin{array}{c} r-2+t\\ r-2
\end{array} \right) = (n-k) \left(\begin{array}{c} k+r-2\\ k-1
\end{array} \right) + \left(\begin{array}{c} k+r-1\\ k-1
\end{array} \right)\] and so
\begin{eqnarray*}
f(n+1, r, k) & = & \frac{1}{n} \left(\begin{array}{c} n \\ r-1
\end{array} \right) \left\{ \frac{(n-r+1)(n-k+1)}{r}
\left(\begin{array}{c} k+r-2\\ r-1 \end{array} \right) \right. \\
&& \left. + (n-k) \left(\begin{array}{c} k+r-2 \\ r-1 \end{array}
\right) + \left(\begin{array}{c}
k+r-1\\ r\end{array} \right)\right\}\\
& = & \frac{1}{n} \left(\begin{array}{c} n \\ r-1 \end{array}
\right) \left(\begin{array}{c} k+r-2\\ r-1 \end{array} \right)
\left\{\frac{(n-r+1)(n-k+1)}{r} \right. \\
&& \left.
+ (n-k) + \frac{k+r-1}{r}\right\}\\
& = & \frac{1}{r} \left(\begin{array}{c} n \\ r-1 \end{array}
\right) \left(
\begin{array}{c} k+r-2\\ r-1 \end{array} \right)(n+2-k)
\end{eqnarray*}
as required. To complete the induction step we still need to
verify the result for $f(n+1, n+1, k)$ and $f(n+1, r, n+1)$.  By
using Lemmas 2.1 and 2.2 and the induction hypothesis these could
be routinely verified. Thus the proof of Proposition 2.3 is
complete.
\end{proof}

Immediately, we have
\begin{corollary}
{\rm \cite[proposition 3.10]{Laradji}}. Let ${\cal C}_n$ be the
semigroup of all decreasing and order-preserving full
transformations of $X_n$. Then
\[
|\{\alpha\in {\cal C}_n:\max(\mbox{Im }\alpha) = k\}| = f(n,n,k)
= \frac{n-k+1}{n} \left(\begin{array}{c} n+k-2 \\
n-1 \end{array} \right).
\]
\end{corollary}
\begin{corollary} For $n \geq r \geq 1$, we have
\[ f(n,r,r) =  \frac{n-r+1}{n} \left(\begin{array}{c} n
\\ r \end{array} \right) \left(\begin{array}{c} 2r-2\\ r-1
\end{array} \right).
\]

\end{corollary}
\begin{lemma} Let $G(n,k)  =  \sum^n_{r=0} f(n,r,k)$. Then
\begin{eqnarray*}G(n, k) =  \frac{n-k+1}{n}\sum^n_{r=0} \left(\begin{array}{c} n \\
r \end{array} \right) \left(\begin{array}{c} k+r-2\\ r-1
\end{array} \right).
\end{eqnarray*}
\end{lemma}

\begin{proposition}
Let $G(n,k) = \displaystyle \sum^n_{r=0} f(n,r,k)$. Then $G(n,0) =
1, \,G(n, 1)=\\ 2^n-1, \,G(n, n) =
\frac{1}{n}\sum^n_{r=0}\left(\begin{array}{c} n \\ r \end{array}
\right) \left(\begin{array}{c} n+r-2\\ r-1 \end{array} \right)$,
and for $2 \leq k \leq n$, we have
\[
G(n,k) = 2G(n-1, k)-G(n-1, k-1) + G(n, k-1).\]
\end{proposition}
\begin{proof}{} Since the initial and boundary conditions are
clear it remains to show the recurrence:
\begin{eqnarray}
G(n,k) & = & \sum^n_{r=0} f(n,r,k)\nonumber
 =  \sum^n_{r=0} \left\{ f(n-1, r, k)+\sum^k_{t=1}
f(n-1, r-1, t)\right\}\nonumber\\[2mm]
& = & \sum^{n-1}_{r=0}
f(n-1, r, k)+\sum^k_{t=0} \sum^n_{r=0} f(n-1,r-1,t) \nonumber\\[2mm]
& = & G(n-1, k) + \sum^k_{t=0} G(n-1, t) \\
& = & 2G(n-1, k) + \sum^{k-1}_{t=0} G(n-1, t). \nonumber
\end{eqnarray}
Thus from (2.4) we have
\[
G(n,k-1) = G(n-1, k-1) + \sum^{k-1}_{t=0} G(n-1, t)\] and so
\[
G(n,k) - G(n,k-1) = 2G(n-1, k) - G(n-1, k-1)\] from which the
result follows.
\end{proof}
\begin{proposition}
Let $\displaystyle F(n,r) = \sum^n_{k=0} f(n,r,k)$. Then
\[
F(n,r) = \frac{1}{n} \left(\begin{array}{c} n \\ r \end{array}
\right)
 \left(\begin{array}{c} n+r\\ n-1 \end{array} \right).\]
\end{proposition}
\begin{proof}{}
The proof is direct by using Lemma 2.2 and Proposition 2.3. Thus
we have
\begin{eqnarray*}
F(n,r) & = & \sum^n_{k=0} f(n,r,k)  =  \sum^n_{k=0}
\frac{n-k+1}{n} \left(\begin{array}{c}
n \\ r\end{array} \right) \left(\begin{array}{c} k+r-2\\ r-1 \end{array} \right)\\
& = & \frac{1}{n} \left(\begin{array}{c} n \\ r \end{array}
\right) \sum^n_{k=0}
[n-(k-1)]\left(\begin{array}{c} k+r-2\\ k-1 \end{array} \right)\\
& = & \frac{1}{n} \left(\begin{array}{c} n \\ r \end{array}
\right) \sum^n_{k=0} [n-(k-1)]\left(\begin{array}{c} (r-1)+(k-1)\\
k-1 \end{array} \right)
\\
& = & \frac{1}{n} \left(\begin{array}{c} n \\ r \end{array}
\right) \sum^{n-1}_{t=0} (n-t)\left(\begin{array}{c}
(r-1)+t\\
t \end{array} \right)
 =  \frac{1}{n} \left(\begin{array}{c} n \\ r \end{array}
\right) \left(
\begin{array}{c} n+r \\ r-1 \end{array} \right)
\end{eqnarray*}
as required.
\end{proof}
\begin{corollary}
{\rm \cite[theorem 3.1]{Higgins2}}. Let ${\cal C}_n$ be the
semigroup of all decreasing and order-preserving full
transformations of $X_n$. Then
\[
|{\cal C}_n| = F(n,n) = \frac{1}{n} \left(\begin{array}{c} 2n \\
n-1 \end{array} \right).
\]
\end{corollary}
\begin{remark} {\rm
The triangular array of numbers $G(n,k)$, $f(n, r, r)$ and
$F(n,r)$ are not yet listed in Sloane's encyclopaedia of integer
sequences \cite{Sloane}. For some selected values of these
numbers, see Tables 1-3}.
\end{remark}

From \cite{Pergola} and \cite{Stanley} we deduce that the large
(or double) Schr\"{o}der number denoted by $r_n$ could be defined
as
\[
r_n = \frac{1}{n+1} \sum^n_{r=0} \left(\begin{array}{c} n+1 \\ n-r
\end{array} \right) \left(\begin{array}{c} n+r \\ r \end{array}
\right).\] Moreover, $r_n$ satisfies the recurrence:
\begin{equation}
(n+2)r_{n+1} = 3(2n+1) r_n - (n-1)r_{n-1}
\end{equation}
for $n\geq 1$, with initial conditions $r_0 = 1$ and $r_1 = 2$.
The (small) Schr\"{o}der number is usually denoted by $s_n$ and
defined as $s_0 = 1, s_n = r_n/2 \, (n \geq 1)$ and so it
satisfies the same recurrence as $r_n$.

\begin{figure}
\begin{center}
\epsfig{file=tab1.eps,width=10cm,height=5cm}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\epsfig{file=tab2.eps,width=10cm,height=5cm}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\epsfig{file=tab3.eps,width=10cm,height=5cm}
\end{center}
\end{figure}

\begin{remark}
{\rm The double Schr\"{o}der number is the number of all lattice
paths in the Cartesian plane that start at $(0,0)$, end at
$(n,n)$, contain no points above the line $y=x$, and are composed
only of steps $(1,0), (0,1)$ and $(1,1)$, i.e., $\rightarrow,
\uparrow$ and $\nearrow$. The authors \cite{Laradji2} established
a bijection between the set of all such paths and ${\cal PC}_n$,
and hence the order of ${\cal PC}_n$ was deduced.}
\end{remark}
We now have the main result of this section:
\begin{theorem}
Let ${\cal PC}_n$ be as defined in (1.1). Then $|{\cal PC}_n| =
r_n$, the double Schr\"{o}der number.
\end{theorem}
\noindent
\begin{proof}{}
It is clear from Proposition 2.8 that
\begin{eqnarray*}
|{\cal PC}_n| & = & \sum^n_{r=0}F(n,r)= \sum^n_{r=0}
\frac{1}{n}\left(\begin{array}{c} n \\ r \end{array} \right)
\left(\begin{array}{c} n+r \\ n-1
\end{array} \right) =  \frac{1}{n+1} \sum^n_{r=0}
\left(\begin{array}{c} n+1 \\ n-r
\end{array} \right) \left(\begin{array}{c}
n+r \\ r \end{array} \right)  =  r_n.
\end{eqnarray*}
\end{proof}

We conclude the section with the following congruence result.
\begin{proposition}
If $n$ is prime then $r_n \equiv 4$ (mod $n$).
\end{proposition}
\begin{proof}{}
Since $\displaystyle r_n = \sum^n_{r=0} \frac{1}{r+1}
\left(\begin{array}{c} n \\ r \end{array} \right)
\left(\begin{array}{c} n+r \\ n \end{array} \right)$ and if $n$ is
prime then $n|\left(\begin{array}{c} n \\ r \end{array} \right)$,
it follows that the only values of $r$ that may not produce terms
divisible by $n$ in the sum are: $0, n-1$ and $n$. Hence
\begin{eqnarray*}
r_n & \equiv & 1 + \frac{1}{n}\cdot n \left(\begin{array}{c} 2n-1
\\ n
\end{array} \right) +
\frac{1}{n+1} \left(\begin{array}{c} 2n \\ n \end{array} \right) (\mbox{mod }n) \\
    & =      & 1 +
\left(\begin{array}{c} 2n-1 \\ n \end{array} \right) +
\frac{1}{n+1}
            \left(\begin{array}{c} 2n \\ n \end{array} \right) (\mbox{mod }n). \end{eqnarray*}
Now let $A = \left(\begin{array}{c} 2n-1 \\ n \end{array}
\right)$, then $n!(n-1)!A = (2n-1)!$, that is
\[
(n-1)! A = (n+1)(n+2) \cdot \cdots \cdot [n+(n-1)] \equiv (n-1)!
\quad (\mbox{mod } n).\] Thus since $(n,(n-1)!) = 1$, it follows
that
\[
A \equiv 1 \quad (\mbox{mod } n).\] Clearly, $2A =
\left(\begin{array}{c} 2n \\ n \end{array} \right)$ so that
\[
\frac{1}{n+1} \left(\begin{array}{c} 2n \\ n \end{array} \right)
\equiv 2A \quad (\mbox{mod } n)
\]
and hence
\[
r_n \equiv 4 \quad (\mbox{mod n}).\]
\end{proof}

\section{The number of idempotents}
\setcounter{equation}{0} 
%\setcounter{lemma}{0}
%\setcounter{theorem}{0} \setcounter{corollary}{0}
%\setcounter{proposition}{0} \setcounter{remark}{0} 
As stated in
the introduction the number of idempotents of various classes of
semigroups of transformations has been computed.  For further
results see \cite{Clifford, Laradji3, Tainiter, Umar, Umar2}. Our
main task in this section is to compute the number of all
idempotents in ${\cal P}{\cal C}_n$. As in the previous section,
we consider
\begin{equation}
e(n,r,k) = |\{\alpha \in {\cal P}{\cal C}_n: \alpha^2 = \alpha,
|\mbox{Dom }\alpha| = r \wedge \max(\mbox{Im } \alpha) = k\}|.
\end{equation}
Then clearly we have
\[
e(n,r,0) = \left\{\begin{array}{ll} 1 & (r=0); \\
0 & (r > 0); \end{array} \right. , e(n,0,k) =
\left\{\begin{array}{ll}
1 & (k=0); \\
0 & (k > 0); \end{array} \right.\] and
\[
e(n,r,1) = \left(\begin{array}{c} n-1 \\ r-1 \end{array}
\right).\] The latter corresponds to the number of all idempotents
$\alpha$ in ${\cal P}{\cal C}_n$ of width $r$ and $\mbox{Im
}\alpha = \{1\}$, that is the number of all subsets of $X_n$ each
containing the element 1 and of size $r$. More generally, we have

\begin{lemma} For all  $n \geq r, k\geq 1$  and  $n > k$, we have
\[ e(n,r,k) = e(n-1, r, k) + e(n-1, r-1, k).\]
\end{lemma}
\begin{proof}{}
If $n\not\in \mbox{Dom }\alpha$ then $n\not\in \mbox{Im } \alpha$,
by idempotency and so there are $e(n-1, r,k)$ idempotents of this
type.  If on the other hand $n \in \mbox{Dom } \alpha$ then
$n\alpha = k < n$ and of course $k\alpha = k$. It is now not
difficult to see that the number of such idempotents is $e(n-1,
r-1, k)$. Hence the result follows.
\end{proof}
\begin{lemma} For $n \geq r \geq 1, \,e(n, r, n) = \displaystyle \sum^{n-1}_{t=0}
e(n-1,r-1,t)$ .
\end{lemma}
\begin{proof}{} Since $n=\max(\mbox{Im } \alpha)$, it
follows by the order-decreasing property that $n\alpha^{-1}=\{n\}$
and so there is no interference with the elements of
$X_n\setminus\{n\}$ of which there are $\displaystyle
\sum^{n-1}_{t=0} e(n-1,r-1,t)$ possible idempotents.
\end{proof}
\begin{proposition} Let $e(n,r) = \displaystyle \sum^n_{k=0} e(n,r,k)$.
For $n\geq r > 0$, we have
\[
e(n,r) = 2^{r-1}\left(\begin{array}{c} n \\ r \end{array}
\right).\]
\end{proposition}
\begin{proof}{}
First note that $e(n,1)$ is the number of all idempotents of width
1, that is of the form $\mbox{Dom } \alpha = \{x\}$ of which there
are $n$ of them and this agrees with the assertion of the
proposition. Suppose now by way of induction $e(n,r)$ is true for
all $n > r > 0$. Then using Lemmas 3.1 and 3.2 and the induction
hypothesis successively, we have
\begin{eqnarray*}
e(n,r) & = & \sum^n_{k=0} e(n,r,k)
        =  e(n,r,n) + \sum^{n-1}_{k=0} e(n,r,k) \\
       & = &            \sum^{n-1}_{t=0} e(n-1, r-1, t) +
\sum^{n-1}_{k=0} \{e(n-1,r,k) + e(n-1, r-1,k)\} \\
& = & 2e(n-1, r-1) + e(n-1, r) \qquad (r \geq 2)\\
& = & 2\cdot 2^{r-2} \left(\begin{array}{c} n-1 \\ r-1 \end{array}
\right) + 2^{r-1} \left(\begin{array}{c} n-1 \\ r \end{array}
\right)  =  2^{r-1} \left(\begin{array}{c} n \\ r \end{array}
\right)
\end{eqnarray*}
as required.
\end{proof}
\begin{corollary}{\rm \cite[theorem 3.19]{Higgins2}}.
Let ${\cal C}_n$ be the semigroup of all decreasing and
order-preserving full transformations of $X_n$. Then
\[
|E({\cal C}_n)| = e(n,n) = 2^{n-1}.
\]
\end{corollary}
We now have the main result of this section:
\begin{proposition} Let ${\cal P}{\cal C}_n$ be as defined in (1.1).
Then $|E({\cal P}{\cal C}_n)| = \frac{1}{2}(3^n + 1)$.
\end{proposition}
\begin{proof}{}
\begin{eqnarray*}
|E({\cal P}{\cal C}_n)| & = & \sum^n_{r=0} e(n,r)
 =  1 + \sum^n_{r=1} e(n,r)
=  1 + \sum^n_{r=1} 2^{r-1}\left(\begin{array}{c} n \\ r \end{array} \right)\\
& = & 1 + \frac{1}{2} \sum^n_{r=1} 2^r \left(\begin{array}{c} n \\
r \end{array} \right)
 =  1 + \frac{1}{2} (3^n - 1)
 =      \frac{1}{2} (3^n + 1). \end{eqnarray*} \end{proof}

Let $g(n, k)$ be the number of maps in ${\cal P}{\cal C}_n$ of
waist $k$. Then $\displaystyle g(n,k) = \sum^n_{r=0} e(n,r,k)$,
and a closed formula for $g(n,k)$ is now possible. First we show
the following lemma:
\begin{lemma} For all $n \geq k > 0, \,
g(n,k) = 2^{n-k}g(k,k)$.
\end{lemma}
\begin{proof}{}
\begin{eqnarray*}
g(n,k) & = & \sum^n_{r=0} e(n,r,k)
        =  \sum^n_{r=0} \{e(n-1,r,k) + e(n-1, r-1, k)\}
 =  2g(n-1, k).
\end{eqnarray*}
By iteration we have
\[
g(n,k) = 2^{n-k} g(k,k) \] as required.
\end{proof}

Now let $\displaystyle e_n = \sum^n_{k=0} g(n,k)$. Then we have

\begin{lemma}
$g(n,n) = e_{n-1}$.
\end{lemma}

\begin{proof}{}
\begin{eqnarray*}
g(n,n) & = & \sum^n_{r=0} e(n,r,n) = \sum^n_{r=0} \sum^n_{t=0}
e(n-1, r-1, t) \\
       & = & \sum^n_{t=0} \sum^n_{r=0} e(n-1, r-1,t) = \sum^n_{t=0}
g(n-1, t)
 =  e_{n-1}. \end{eqnarray*}
\end{proof}

\begin{proposition}
Let $\displaystyle g(n,k) = \sum^n_{r=0} e(n,r,k)$. For $n\geq k >
0$, we have
\[
g(n,k) = 2^{n-k-1} (3^{k-1} + 1).\]
\end{proposition}

\begin{proof}{}
By Lemmas 3.6 and 3.7 and Proposition 3.5 successively we have
\begin{eqnarray*}
g(n,k) & = & 2^{n-k} g(k,k)  =  2^{n-k} \cdot 2^{-1} (3^{k-1} + 1)
=  2^{n-k-1} (3^{k-1} + 1) \qquad ( k < n),
\end{eqnarray*}
as required.  Moreover, by Lemma 3.7 and Proposition 3.5
\begin{eqnarray*}
g(n,n) & = & e_{n- 1}
 =  \frac{1}{2} (3^{n-1} + 1)
 =  2^{-1} (3^{n-1}+1)
\end{eqnarray*}
as required.  Hence the proof is complete.
\end{proof}
\begin{remark}{\rm
The triangular array of numbers $e(n,r)$ is referred to in
\cite[A082137]{Sloane} as square arrays of transforms of binomial
coefficients, read by anti-diagonals.  But the triangular array of
numbers $g(n,k)$ is not yet listed in \cite{Sloane}. For some
selected values of these numbers, see Tables 4 and 5.}
\end{remark}
\newpage
\begin{figure}
\begin{center}
\epsfig{file=tab4.eps,width=10cm,height=5cm}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\epsfig{file=tab5.eps,width=10cm,height=5cm}
\end{center}
\end{figure}

\noindent {\bf Acknowledgment}. We would like to gratefully
acknowledge support from the King Fahd University of Petroleum and
Minerals. We wish to also thank the referee for some invaluable
comments and for bringing references \cite{Pin, Popova, Solomon}
to our attention.

\baselineskip=13pt
\begin{thebibliography}{99}

\bibitem{Clifford}
A. H. Clifford and G. B. Preston, {\em The Algebraic Theory of
Semigroups}, Vol. 1, Mathematical Surveys 7 (Providence, R. I.:
American Math. Soc., 1961).

\bibitem{Garba}
G.U. Garba, Idempotents in partial transformation semigroups. {\em %
Proc. Roy. Soc. Edinburgh} {\bf 116} (1990), 359--366.

\bibitem{Garba2}
G. U. Garba, On the idempotent ranks of certain semigroups
of order-preserving transformations,  {\em %
Portugal. Math.} {\bf 51} (1994), 185--204.

\bibitem{Gomes}
G. M. S. Gomes and J. M. Howie, On the ranks of certain semigroups
of order-preserving transformations, \emph{Semigroup Forum},
\textbf{45} (1992), 272--282.

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

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

\bibitem{Higgins3}
P. M. Higgins, Divisors of semigroups of order-preserving mappings
on a finite chain, {\em Intern. Journal of Algebra and
Computations} {\bf 5} (1995), 725--742.

\bibitem{Howie}
J. M. Howie, {\em Fundamentals of Semigroup Theory} (Oxford:
Clarendon Press, 1995).

\bibitem{Howie2}
J. M. Howie, Products of idempotents in certain semigroups of
order-preserving transformations, {\em Proc. Edinburgh Math. Soc.}
(2) {\bf 17}(1971), 223--236.

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

\bibitem{Laradji2}
A. Laradji and A. Umar, Lattice paths and order-preserving
partial transformations, {\em submitted}.

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

\bibitem{Pergola}
E. Pergola and R. A. Sulanke, Schr\"{o}der Triangles, Paths and
Parallelogram Polyominoes, {\em J. Integer Sequences} 
{\bf 1} (1998), 98.1.7.

\bibitem{Pin}
J. E. Pin, {\em Varieties of formal languages}, translated from
the French by A. Howie, (Plenum Pub. Corp., New York, 1986).

\bibitem{Popova}
L. M. Popova, Defining relations of a semigroup of partial
endomorphisms of a finite linearly ordered set, {\em Leningrad.
Gos. Ped. Inst. U\v{c}en. Zap} {\bf 238} (1962), 78--88.

\bibitem{Riordan}
J. Riordan, {\em Combinatorial Identities},  (John Wiley
and Sons, New York, 1968).

\bibitem{Sloane}
N. J. A. Sloane, The On-Line Encyclopedia of Integer
Sequences, available at
\\http://www.research.att.com/~njas/sequences/

\bibitem{Solomon}
A. Solomon, Catalan monoids, monoids of local endomorphisms, and
their presentations, {\em Semigroup Forum} {\bf 53} (1996),
351--368.

\bibitem{Stanley}
R. P. Stanley, Hipparchus, Plutarch, Schr\"{o}der and
Hough, {\em Amer. Math. Monthly}  {\bf 104} (1997), 344-350.

\bibitem{Tainiter}
M. Tainiter, A characterization of idempotents in semigroups, {\em
J. Combin.\ Theory} {\bf 5} (1968), 370--373.

\bibitem{Umar}
A. Umar, On the semigroups of order-decreasing finite full
transformations, {\em Proc. Roy. Soc. Edinburgh Sect.} A {\bf 120}
(1992), 129--142.

\bibitem{Umar2}
A. Umar, Enumeration of certain finite semigroups of
transformations, {\em Discrete Math.} {\bf 189} (1998), 291--297.

\bibitem{Umar3}
A. Umar, On certain infinite semigroups of order-decreasing
transformations I, {\em Commun. Algebra} {\bf 25}
(9) (1997), 2987--2999.

\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\bigskip

\noindent \emph{Keywords: }
Semigroup, order-preserving,
order-decreasing, partial transformation, full transformation,
Catalan number, Fibonacci number, Narayana numbers,
Schr\"{o}der numbers.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001263} and \seqnum{A082137}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 25 2003;
revised version received July 31 2004; 
Published in {\it Journal of Integer Sequences}, October 17 2004.

\bigskip
\hrule
\bigskip

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

\end{document}