Combinatorial Results for Semigroups of Order-Decreasing Partial Transformations

A. Laradji and A. Umar Department of Mathematical Sciences King Fahd University of Petroleum and Minerals Dhahran 31261 Saudi Arabia

                      aumar@kfupm.edu.sa

Abstract Let PC_{n} be the semigroup of all decreasing and order-preserving partial transformations of a finite chain. It is shown that |PC_{n}| = r_{n}, where r_{n} is the large (or double) Schröder number. Moreover, the total number of idempotents of PC_{n} is shown to be (3^{n} + 1)/2.

1 Introduction and Preliminaries

Consider a finite chain, say X_{n} = {1, 2, …, 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 α : X_{n} → X_{n}, order-decreasing (order-increasing) or simply decreasing (increasing) if xα ≤ x (xα ≥ x) for all x in Dom α, and α is order-preserving if x ≤ y implies xα ≤ yα for x, y in Dom α. The semigroup of all decreasing full transformations is denoted by D_{n}, while the semigroup of all order-preserving full transformations is denoted by O_{n}, and D_{n} ∩ O_{n} is denoted by C_{n}.

Various enumerative problems of an essentially combinatorial nature have been considered for certain classes of semigroups of transformations. For example, Howie [9] showed that the order and number of idempotents of O_{n} are, respectively,

|O_{n}| = ( \begin{matrix}2n − 1 \\ n − 1 \end{matrix} ) and |E(O_{n})| = F_{2n},

where F_{2n} is the alternate Fibonacci number given by F_{1} = F_{2} = 1. More recently, Higgins [6] showed in particular, that |C_{n}| is the n-th Catalan number given by

|C_{n}| = \frac{1}{n + 1} ( \begin{matrix}2n \\ n \end{matrix} )

and |E(C_{n})| = 2^{n−1}. Further combinatorial properties for C_{n} were investigated by Laradji and Umar [10], where they showed that the number of maps in C_{n} such that |Im α| = r is the triangle of Narayana [17, A001263] numbers given by

|\{α ∈ C_{n} : |Im α| = r\}| = \frac{1}{n − r + 1} ( \begin{matrix}n − 1 \\ r − 1 \end{matrix} ) ( \begin{matrix}n \\ r \end{matrix} ) .

This paper investigates combinatorial properties of PC_{n}, the semigroup of all decreasing and order-preserving partial transformations, along the lines of [10]. An alternative approach to finding the order and number of idempotents in PC_{n} is given in [11], 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 [17]. Ironically, it is this paper that motivated [11] and [12]. The following is a list (which is by no means exhaustive) of papers and books [1, 2, 3, 4, 5, 6, 8, 9, 20, 21, 22] each of which contains some interesting combinatorial results pertaining to semigroups of transformations. Initially, the only reference we could find about PC_{n} is Higgins [7, theorem 4.2], where it is shown that any finite R -trivial semigroup S divides some monoid PC_{n}. However, the referee drew our attention to [15] and [18] where presentations of PC_{n} on a chain and trees, respectively, were studied and also to [14] where 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 PC_{n} as the large or double Schröder number [13], via some natural equivalences on PC_{n}. In Section 4, we show that the set of all idempotents of PC_{n} is of cardinality (3^{n} + 1)/2, again, via some natural equivalences on E(PC_{n}).

For standard terms and concepts in transformation semigroup theory see [5] or [8]. We now recall some definitions and notations to be used in the paper. Consider X_{n} = {1, 2, …, n} and let α : X_{n} → X_{n} be a partial transformation. We shall denote by Dom α and Im α, the domain and image set of α, respectively. The semigroup P_{n}, of all partial transformations contains two important subsemigroups which have been studied recently. They are P D_{n} and PO_{n} the semigroups of all order-decreasing and order-preserving partial transformations, respectively (see [23] and [3, 4]). Now let

PC_{n} = P D_{n} ∩ PO_{n}  (1.1)

be the semigroup of all decreasing and order-preserving partial transformations of X_{n}.

2 The order of PC_{n}

Our main objective in this section is to obtain a formula for |PC_{n}|. We initiate our investigation by considering two natural equivalences on PC_{n}. The first equivalence is defined by equality of widths (width of α := |Dom α|), while the second equivalence is defined by equality of waists (waist of α := max(Im α)). Taking the intersection of these two equivalences leads to the following definition of f(n, r, k) as

f(n, r, k) = |{α ∈ PC_{n} : |Dom α| = r ∧ max(Im α) = k}|.  (2.1)

Then clearly we have

f(n, 0, 0) = 1, f(n, n, 1) = 1

and

f(n, r, 0) = 0 (if r > 0), f(n, 0, k) = 0 (if k > 0).

Slightly less clearly, we have

f(n, 1, k) = n − (k − 1) = n − k + 1  (2.2)

and

f(n, r, 1) = ( \begin{matrix}n \\ r \end{matrix} )  (2.3)

In fact, f(n, 1, k) corresponds to the number of maps α (in PC_{n}) with singleton domain and hence Im α = {k}. Since by the order-decreasing property, x ∈ Dom α implies x ∈ {k, k + 1, …, 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

Lemma 2.1 For all n ≥ r, k ≥ 0, we have

f(n, r, k) = f(n − 1, r, k) + ∑_{t=0}^{k} f(n − 1, r − 1, t).

Proof. Essentially there are two cases to consider: n ∉ Dom α and n ∈ Dom α. In the former case there are clearly f(n−1, r, k) maps of this type. In the latter case, since nα = k, it is not difficult to see that there are

∑_{t=0}^{k} f(n − 1, r − 1, t)

maps of this type. Hence the result follows.

A closed formula for f(n, r, k) is possible, but before we propose this formula we would like to state this lemma from [10, lemma 3.3] which is obtained by combining equations (3) and (3b) from [16, p. 8].

Lemma 2.2 For any c ∈ ℝ, and q, m ∈ ℕ ∪ {0}, we have

∑_{j=0}^{m}(c − j) ( \begin{matrix}q + j \\ j \end{matrix} ) = (c − m − 1) ( \begin{matrix}m + q + 1 \\ m \end{matrix} ) + ( \begin{matrix}m + q + 2 \\ m \end{matrix} ) .

Proposition 2.3 Let f(n, r, k) be as defined in (2.1). Then for n ≥ r, k > 0, we have

f(n, r, k) = \frac{n − k + 1}{r} ( \begin{matrix}n − 1 \\ r − 1 \end{matrix} ) ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} ) = \frac{n − k + 1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} ) .

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 ≤ r, k ≤ n. We now prove that it is true for all 1 ≤ r, k ≤ n + 1. By Lemma 2.1 and the induction hypothesis successively, we have

f(n + 1, r, k) = f(n, r, k) + ∑_{t=0}^{k} f(n, r − 1, t)

= \frac{n − k + 1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} ) + ∑_{t=0}^{k} \frac{n − t + 1}{n} ( \begin{matrix}n \\ r − 1 \end{matrix} ) ( \begin{matrix}r + t − 3 \\ r − 2 \end{matrix} )

= \frac{1}{n} \{\frac{n!(n − k + 1)}{(n − r)!r(r − 1)!} ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} ) + (n + 1) ( \begin{matrix}n \\ r − 1 \end{matrix} ) ∑_{t=1}^{k} ( \begin{matrix}r + t − 3 \\ r − 2 \end{matrix} )

− ( \begin{matrix}n \\ r − 1 \end{matrix} ) ∑_{t=1}^{k} t ( \begin{matrix}r + t − 3 \\ r − 2 \end{matrix} )\}

= \frac{1}{n} ( \begin{matrix}n \\ r − 1 \end{matrix} ) \{\frac{n − r + 1}{r}(n − k + 1) ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} ) + (n + 1) ∑_{t=0}^{k−1} ( \begin{matrix}r − 2 + t \\ r − 2 \end{matrix} )

− ∑_{t=0}^{k−1}(t + 1) ( \begin{matrix}r − 2 + t \\ r − 2 \end{matrix} )\} .

= \frac{1}{n} ( \begin{matrix}n \\ r − 1 \end{matrix} ) \{\frac{(n − r + 1)(n − k + 1)}{r} ( \begin{matrix}k + r − 2 \\ r − 2 \end{matrix} )

+ ∑_{t=0}^{k−1}(n − t) ( \begin{matrix}r − 2 + t \\ r − 2 \end{matrix} )\} .

However, by Lemma 2.2

∑_{t=0}^{k−1}(n − t) ( \begin{matrix}r − 2 + t \\ r − 2 \end{matrix} ) = (n − k) ( \begin{matrix}k + r − 2 \\ k − 1 \end{matrix} ) + ( \begin{matrix}k + r − 1 \\ k − 1 \end{matrix} )

and so

f(n + 1, r, k) = \frac{1}{n} ( \begin{matrix}n \\ r − 1 \end{matrix} ) \{\frac{(n − r + 1)(n − k + 1)}{r} ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} )

+(n − k) ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} ) + ( \begin{matrix}k + r − 1 \\ r \end{matrix} )\}

= \frac{1}{n} ( \begin{matrix}n \\ r − 1 \end{matrix} ) ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} ) \{\frac{(n − r + 1)(n − k + 1)}{r}

+(n − k) + \frac{k + r − 1}{r}\}

= \frac{1}{r} ( \begin{matrix}n \\ r − 1 \end{matrix} ) ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} ) (n + 2 − k)

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.

Immediately, we have

Corollary 2.4 [10, proposition 3.10]. Let C_{n} be the semigroup of all decreasing and orderpreserving full transformations of X_{n}. Then

|\{α ∈ C_{n} : max(Im α) = k\}| = f(n, n, k) = \frac{n − k + 1}{n} ( \begin{matrix}n + k − 2 \\ n − 1 \end{matrix} ) .

Corollary 2.5 For n ≥ r ≥ 1, we have

f(n, r, r) = \frac{n − r + 1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}2r − 2 \\ r − 1 \end{matrix} ) .

Lemma 2.6 Let G(n, k) = ∑_{r=0}^{n} f(n, r, k). Then

G(n, k) = \frac{n − k + 1}{n} ∑_{r=0}^{n} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} ) .

Proposition 2.7 Let G(n, k) = ∑_{r=0}^{n} f(n, r, k). Then G(n, 0) = 1, G(n, 1) =

2^{n} − 1, G(n, n) = \frac{1}{n} ∑_{r=0}^{n} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}n + r − 2 \\ r − 1 \end{matrix} ), and for 2 ≤ k ≤ n, we have

G(n, k) = 2G(n − 1, k) − G(n − 1, k − 1) + G(n, k − 1).

Proof. Since the initial and boundary conditions are clear it remains to show the recurrence:

G(n, k) = ∑_{r=0}^{n} f(n, r, k) = ∑_{r=0}^{n} {f(n − 1, r, k) + ∑_{t=1}^{k} f(n − 1, r − 1, t)}

= ∑_{r=0}^{n−1} f(n − 1, r, k) + ∑_{t=0}^{k} ∑_{r=0}^{n} f(n − 1, r − 1, t)

= G(n − 1, k) + ∑_{t=0}^{k} G(n − 1, t)  (2.4)

= 2G(n − 1, k) + ∑_{t=0}^{k−1} G(n − 1, t).

Thus from (2.4) we have

G(n, k − 1) = G(n − 1, k − 1) + ∑_{t=0}^{k−1} 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.

Proposition 2.8 Let F (n, r) = ∑_{k=0}^{n} f(n, r, k). Then

F (n, r) = \frac{1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}n + r \\ n − 1 \end{matrix} ) .

Proof. The proof is direct by using Lemma 2.2 and Proposition 2.3. Thus we have

F (n, r) = ∑_{k=0}^{n} f(n, r, k) = ∑_{k=0}^{n} \frac{n − k + 1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}k + r − 2 \\ r − 1 \end{matrix} )

= \frac{1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ∑_{k=0}^{n}[n − (k − 1)] ( \begin{matrix}k + r − 2 \\ k − 1 \end{matrix} )

= \frac{1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ∑_{k=0}^{n}[n − (k − 1)] ( \begin{matrix}(r − 1) + (k − 1) \\ k − 1 \end{matrix} )

= \frac{1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ∑_{t=0}^{n−1}(n − t) ( \begin{matrix}(r − 1) + t \\ t \end{matrix} ) = \frac{1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}n + r \\ r − 1 \end{matrix} )

as required.

Corollary 2.9 [6, theorem 3.1]. Let C_{n} be the semigroup of all decreasing and orderpreserving full transformations of X_{n}. Then

|C_{n}| = F (n, n) = \frac{1}{n} ( \begin{matrix}2n \\ n − 1 \end{matrix} ) .

Remark 2.1 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 [17]. For some selected values of these numbers, see Tables 1-3.

From [13] and [19] we deduce that the large (or double) Schröder number denoted by r_{n} could be defined as

r_{n} = \frac{1}{n + 1} ∑_{r=0}^{n} ( \begin{matrix}n + 1 \\ n − r \end{matrix} ) ( \begin{matrix}n + r \\ r \end{matrix} ) .

Moreover, r_{n} satisfies the recurrence:

(n + 2)r_{n+1} = 3(2n + 1)r_{n} − (n − 1)r_{n−1}  (2.5)

for n ≥ 1, with initial conditions r_{0} = 1 and r_{1} = 2. The (small) Schröder number is usually denoted by s_{n} and defined as s_{0} = 1, s_{n} = r_{n}/2 (n ≥ 1) and so it satisfies the same recurrence as r_{n}.

7 Remark 2.2 The double Schrö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., →, ↑ and ↗. The authors [11] established a bijection between the set of all such paths and PC_{n}, and hence the order of PC_{n} was deduced.

We now have the main result of this section:

Theorem 2.10 Let PC_{n} be as defined in (1.1). Then |PC_{n}| = r_{n}, the double Schröder number.

Proof. It is clear from Proposition 2.8 that

|PC_{n}| = ∑_{r=0}^{n} F (n, r) = ∑_{r=0}^{n} \frac{1}{n} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}n + r \\ n − 1 \end{matrix} ) = \frac{1}{n + 1} ∑_{r=0}^{n} ( \begin{matrix}n + 1 \\ n − r \end{matrix} ) ( \begin{matrix}n + r \\ r \end{matrix} ) = r_{n}.

We conclude the section with the following congruence result.

Proposition 2.11 If n is prime then r_{n} ≡ 4 (mod n).

Proof. Since r_{n} = ∑_{r=0}^{n} \frac{1}{r + 1} ( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}n + r \\ n \end{matrix} ) and if n is prime then n| ( \begin{matrix}n \\ r \end{matrix} ), 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

r_{n} ≡ 1 + \frac{1}{n} · n ( \begin{matrix}2n − 1 \\ n \end{matrix} ) + \frac{1}{n + 1} ( \begin{matrix}2n \\ n \end{matrix} ) (mod n)
= 1 + ( \begin{matrix}2n − 1 \\ n \end{matrix} ) + \frac{1}{n + 1} ( \begin{matrix}2n \\ n \end{matrix} ) (mod n).

Now let A = ( \begin{matrix}2n − 1 \\ n \end{matrix} ), then n!(n − 1)!A = (2n − 1)!, that is

(n − 1)!A = (n + 1)(n + 2) · · · · · [n + (n − 1)] ≡ (n − 1)! (mod n).

Thus since (n, (n − 1)!) = 1, it follows that

A ≡ 1 (mod n).

Clearly, 2A = ( \begin{matrix}2n \\ n \end{matrix} ) so that

\frac{1}{n + 1} ( \begin{matrix}2n \\ n \end{matrix} ) ≡ 2A (mod n)

and hence

r_{n} ≡ 4 (mod n).

3 The number of idempotents

As stated in the introduction the number of idempotents of various classes of semigroups of transformations has been computed. For further results see [1, 12, 20, 21, 22]. Our main task in this section is to compute the number of all idempotents in PC_{n}. As in the previous section, we consider

e(n, r, k) = |{α ∈ PC_{n} : α^{2} = α, |Dom α| = r ∧ max(Im α) = k}|.  (3.1)

Then clearly we have

e(n, r, 0) = \{ \begin{matrix}1 & (r = 0); \\ 0 & (r > 0); \end{matrix} , e(n, 0, k) = \{ \begin{matrix}1 & (k = 0); \\ 0 & (k > 0); \end{matrix}

and

e(n, r, 1) = ( \begin{matrix}n − 1 \\ r − 1 \end{matrix} ) .

The latter corresponds to the number of all idempotents α in PC_{n} of width r and Im α = {1}, that is the number of all subsets of X_{n} each containing the element 1 and of size r. More generally, we have

Lemma 3.1 For all n ≥ r, k ≥ 1 and n > k, we have

e(n, r, k) = e(n − 1, r, k) + e(n − 1, r − 1, k).

Proof. If n ∉ Dom α then n ∉ Im α, by idempotency and so there are e(n − 1, r, k) idempotents of this type. If on the other hand n ∈ Dom α then nα = k < n and of course kα = 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.

Lemma 3.2 For n ≥ r ≥ 1, e(n, r, n) = ∑_{t=0}^{n−1} e(n − 1, r − 1, t) .

Proof. Since n = max(Im α), it follows by the order-decreasing property that nα^{−1} = {n}

and so there is no interference with the elements of X_{n} \ {n} of which there are ∑_{t=0}^{n−1} e(n −

1, r − 1, t) possible idempotents.

Proposition 3.3 Let e(n, r) = ∑_{k=0}^{n} e(n, r, k). For n ≥ r > 0, we have

e(n, r) = 2^{r−1} ( \begin{matrix}n \\ r \end{matrix} ) .

Proof. First note that e(n, 1) is the number of all idempotents of width 1, that is of the form Dom α = {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

e(n, r) = ∑_{k=0}^{n} e(n, r, k) = e(n, r, n) + ∑_{k=0}^{n−1} e(n, r, k)
= ∑_{t=0}^{n−1} e(n − 1, r − 1, t) + ∑_{k=0}^{n−1}{e(n − 1, r, k) + e(n − 1, r − 1, k)}
= 2e(n − 1, r − 1) + e(n − 1, r) (r ≥ 2)
= 2 · 2^{r−2} ( \begin{matrix}n − 1 \\ r − 1 \end{matrix} ) + 2^{r−1} ( \begin{matrix}n − 1 \\ r \end{matrix} ) = 2^{r−1} ( \begin{matrix}n \\ r \end{matrix} )

as required. Corollary 3.4 [6, theorem 3.19]. Let C_{n} be the semigroup of all decreasing and orderpreserving full transformations of X_{n}. Then

|E(C_{n})| = e(n, n) = 2^{n−1}.

We now have the main result of this section: Proposition 3.5 Let PC_{n} be as defined in (1.1). Then |E(PC_{n})| = \frac{1}{2}(3^{n} + 1). Proof.

|E(PC_{n})| = ∑_{r=0}^{n} e(n, r) = 1 + ∑_{r=1}^{n} e(n, r) = 1 + ∑_{r=1}^{n} 2^{r−1} ( \begin{matrix}n \\ r \end{matrix} )
= 1 + \frac{1}{2} ∑_{r=1}^{n} 2^{r} ( \begin{matrix}n \\ r \end{matrix} ) = 1 + \frac{1}{2}(3^{n} − 1) = \frac{1}{2}(3^{n} + 1).

Let g(n, k) be the number of maps in PC_{n} of waist k. Then g(n, k) = ∑_{r=0}^{n} e(n, r, k), and a closed formula for g(n, k) is now possible. First we show the following lemma: Lemma 3.6 For all n ≥ k > 0, g(n, k) = 2^{n−k}g(k, k). Proof.

g(n, k) = ∑_{r=0}^{n} e(n, r, k) = ∑_{r=0}^{n}{e(n − 1, r, k) + e(n − 1, r − 1, k)} = 2g(n − 1, k).

By iteration we have

g(n, k) = 2^{n−k}g(k, k)

as required.

Now let e_{n} = ∑_{k=0}^{n} g(n, k). Then we have Lemma 3.7 g(n, n) = e_{n−1}.

Proof.

g(n, n) = ∑_{r=0}^{n} e(n, r, n) = ∑_{r=0}^{n} ∑_{t=0}^{n} e(n − 1, r − 1, t)

= ∑_{t=0}^{n} ∑_{r=0}^{n} e(n − 1, r − 1, t) = ∑_{t=0}^{n} g(n − 1, t) = e_{n−1}.

Proposition 3.8 Let g(n, k) = ∑_{r=0}^{n} e(n, r, k). For n ≥ k > 0, we have

g(n, k) = 2^{n−k−1}(3^{k−1} + 1).

Proof. By Lemmas 3.6 and 3.7 and Proposition 3.5 successively we have

g(n, k) = 2^{n−k}g(k, k) = 2^{n−k} · 2^{−1}(3^{k−1} + 1) = 2^{n−k−1}(3^{k−1} + 1) (k < n),

as required. Moreover, by Lemma 3.7 and Proposition 3.5

g(n, n) = e_{n−1} = \frac{1}{2}(3^{n−1} + 1) = 2^{−1}(3^{n−1} + 1)

as required. Hence the proof is complete.

Remark 3.1 The triangular array of numbers e(n, r) is referred to in [17, A082137] 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 [17]. For some selected values of these numbers, see Tables 4 and 5.

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 [14, 15, 18] to our attention.

References

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

[2] G.U. Garba, Idempotents in partial transformation semigroups. Proc. Roy. Soc. Edinburgh 116 (1990), 359–366.

[3] G. U. Garba, On the idempotent ranks of certain semigroups of order-preserving transformations, Portugal. Math. 51 (1994), 185–204.

[4] G. M. S. Gomes and J. M. Howie, On the ranks of certain semigroups of order-preserving transformations, Semigroup Forum, 45 (1992), 272–282.

[5] P. M. Higgins, Techniques of Semigroup Theory, (Oxford University Press, 1992).

[6] P. M. Higgins, Combinatorial results for semigroups of order-preserving mappings, Math. Proc. Camb. Phil. Soc. 113 (1993), 281–296.

[7] P. M. Higgins, Divisors of semigroups of order-preserving mappings on a finite chain, Intern. Journal of Algebra and Computations 5 (1995), 725–742.

[8] J. M. Howie, Fundamentals of Semigroup Theory (Oxford: Clarendon Press, 1995).

[9] J. M. Howie, Products of idempotents in certain semigroups of order-preserving transformations, Proc. Edinburgh Math. Soc. (2) 17(1971), 223–236.

[10] A. Laradji and A. Umar, On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2) (2004) 184–200.

[11] A. Laradji and A. Umar, Lattice paths and order-preserving partial transformations, submitted.

[12] Laradji and A. Umar, Combinatorial results for semigroups of order-preserving partial transformations, J. Algebra 278 (1)(2004), 342–359.

[13] E. Pergola and R. A. Sulanke, Schröder Triangles, Paths and Parallelogram Polyominoes, J. Integer Sequences 1 (1998), 98.1.7.

[14] J. E. Pin, Varieties of formal languages, translated from the French by A. Howie, (Plenum Pub. Corp., New York, 1986).

[15] L. M. Popova, Defining relations of a semigroup of partial endomorphisms of a finite linearly ordered set, Leningrad. Gos. Ped. Inst. Učen. Zap 238 (1962), 78–88.

[16] J. Riordan, Combinatorial Identities, (John Wiley and Sons, New York, 1968).

[17] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, available at http://www.research.att.com/ njas/sequences/

[18] A. Solomon, Catalan monoids, monoids of local endomorphisms, and their presentations, Semigroup Forum 53 (1996), 351–368.

[19] R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Amer. Math. Monthly 104 (1997), 344-350.

[20] M. Tainiter, A characterization of idempotents in semigroups, J. Combin. Theory 5 (1968), 370–373.

[21] A. Umar, On the semigroups of order-decreasing finite full transformations, Proc. Roy. Soc. Edinburgh Sect. A 120 (1992), 129–142.

[22] A. Umar, Enumeration of certain finite semigroups of transformations, Discrete Math. 189 (1998), 291–297.

[23] A. Umar, On certain infinite semigroups of order-decreasing transformations I, Commun. Algebra 25 (9) (1997), 2987–2999.

2000 Mathematics Subject Classification: Primary 20M18; Secondary 20M20, 05A10, 05A15.

Keywords: Semigroup, order-preserving, order-decreasing, partial transformation, full transformation, Catalan number, Fibonacci number, Narayana numbers, Schröder numbers.

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

Received October 25 2003; revised version received July 31 2004; Published in Journal of Integer Sequences, October 17 2004.

Return to Journal of Integer Sequences home page.