Let . A (partial) transformation is said to be full or total if ; otherwise it is called strictly partial. The set of partial transformations of , denoted by , more commonly known as the partial transformation semigroup is also known as the partial symmetric semigroup or monoid with composition of mappings as the semigroup operation. Similarly, the set of full (or total) transformations of , denoted by , more commonly known as the full transformation semigroup is also known as the (full) symmetric semigroup or monoid.
We shall write the image of x under as (or simply ) instead of . This is called the right-hand notation and it has the advantage that composition of maps is read from left to right, that is, . Further, a transformation is said to be order-preserving (order-reversing) if and, a contraction mapping (or simply a contraction) if . We shall denote by and , the semigroups of order-preserving partial contractions and of order-preserving, order-decreasing partial contractions of , respectively.
Recently, Zhao and Yang  initiated the algebraic study of semigroups of order-preserving partial contractions of , where they referred to our contractions as compressions. A general systematic studied of various semigroups of contraction mappings of a finite chain was initiated in the papers    . While the papers    investigated algebraic properties of various semigroups of contraction mappings of a finite chain, Adeshola and Umar  investigated combinatorial properties of the semigroups of order-preserving full contraction mappings, and its subsemigroup of order-decreasing full contraction mappings, . This paper investigates the combinatorial properties of the set of idempotents of and and of certain natural equivalences on them.
An element e in a semigroup S, is said to be an idempotent if . Every finite semigroup contains an idempotent and in a group there is only one idempotent, namely the identity. Semigroups which contain a “sufficient” supply of idempotents (for example, regular, abundant, etc.) have been the object of study by many semigroup theorists largely due to the role idempotents play in determining the structure of such semigroups. Counting the number of idempotents in a semigroup has attracted the attention of several authors, see for example   - , which is by no means a complete list. For a detailed account on combinatorial enumeration problems in transformation semigroup theory we refer the reader to Umar . It is fairly obvious that the number of full and partial transformation idempotents of denoted by and are, respectively,
 and .
However, at least two non-trivial cases are worth mentioning. In an elegant paper in 1971, Howie  showed that the number of full order-preserving idempotents denoted by is
where denotes the mth Fibonacci number, defined recursively for by
More recently, Adeshola and Umar  showed that the number of full order-preserving contraction idempotents denoted by is
We conclude this section with a breakdown of our investigation section by section. In Section 2 we obtain the cardinalities of various equivalence classes defined on . In Section 3 we obtain the analogues of the results from Section 2 for . These cardinalities lead to formulae for the orders of and as well as new triangles of numbers which are as at the time of submitting this paper not yet recorded in .
For standard concepts in semigroup and transformation semigroup theory, see for example  . In particular, the set of idempotents of a semigroup S is denoted by .
2. The Semigroup
Our approach is essentially that of . For define as the set of fixed points of , and let
Then we have the following results:
Lemma 2.1. For , , and .
Lemma 2.2. For , , and .
Proof. Let be such that . It is clear that for all either or . In the former, we must have and there are choices for x. Thus each x has two degrees of freedom. The result is clear when .
Lemma 2.3. For , , and .
Proof. Let be such that . Then for all , we must have , and again, each with 2 degrees of freedom.
Next, we state and prove an analogue of ( , Lemma 4) which will be useful in what follows.
Lemma 2.4. For , .
Proof. is the number of maps with and for some : if r is the smallest integer greater than 1 such that ; then clearly the number of such maps is , as required.
This leads to the following lemma:
Lemma 2.5. For , , and .
Proof. Substituting and with 1 and , respectively into Lemma 2.4 we get
Replacing n by we get
Subtracting (2) from (1) we get
which implies (by iteration)
We also have
Lemma 2.6. For , .
Next, we state and prove an analogue of ( , Lemma 5) which will be useful in what follows.
Lemma 2.7. For , .
Proof. The nilpotents of are precisely those that do not have fixed points (see  ), hence is the number of maps with at least one fixed point. If is the number of such maps with r as the smallest fixed point, then . Hence . The result now follows.
Now we are ready to state and prove one of the two main results of this section.
Theorem 2.8. For , .
Proof. Using Lemmas 2.5, 2.6 & 2.7 we see that
Now we let be the (ordinary) generating functions of the sequence above. The proof of the next result is routine using Theorem 2.8 above.
Theorem 2.9. .
As in Umar , for natural numbers we define
Then we have
Proposition 2.10. Let . Then and
Proof. Let be such that and . First, notice that if then , and so . Now for all there are two degrees of freedom: and ; or . Hence .
Next, let then . Next, note that we can
choose the remaining elements of in ways, since
. Similarly, the remaining elements of can be chosen from in ways, as each has two degrees of freedom. Now taking the sum over the range of t yields the required result.
Immediately, we deduce the following
Corollary 2.11. Let . Then and
Corollary 2.12. Let . Then , and
Table 1. Some selected values of in .
Table 2. Some selected values of in .
3. The Semigroup
Then observe that Lemmas 2.1, 2.2, 2.4, 2.5 & 2.6 are all valid if we replace with . Moreover, in contrast to Lemma 2.3 we have
Lemma 3.1. For , .
To prove the main result of this section, the following lemma (which can be proved by induction) will be needed:
Lemma 3.2. For , we have .
An analogue of Lemma 2.7 will also be needed.
Lemma 3.3. For , .
Thus we can now state and prove one of the main results of this section.
Theorem 3.4. For , .
Proof. Using Lemmas 2.5, 2.6, 3.1 & 3.3 we see that
(by Lemma 3.2)
Now we let be the (ordinary) generating functions of the corresponding sequence above. Then we have the following result whose proof is routine using Theorem 3.4.
Theorem 3.5. .
As in the previous section we obtain expressions for the following combinatorial functions.
Proposition 3.6. Let . Then
Proof. Let be such that and .
First, note that we can choose the remaining elements of in
ways, since . Similarly, the remaining elements of can be chosen from in ways, as each has two degrees of freedom: or .
Immediately, we deduce the following
Corollary 3.7. Let . Then and .
Corollary 3.8. Let . Then and
Table 3. Some selected values of in .
Table 4. Some selected values of in .
Remark 3.9. The sequence , is recorded (in  ) as A005183.
Financial support from TRC Grant No: RC/SCI/DOMS/13/01 is gratefully acknowledged.
 Zhao, P. and Yang, M. (2012) Regularity and Green’s Relations on Semigroups of Transformations Preserving Order and Compression. Bulletin of the Korean Mathematical Society, 49, 1015-1025.
 Umar, A. (1992) On the Semigroups of Order-Decreasing Finite Full Transformations. Proceedings of the Royal Society of Edinburgh Section A, 120, 129-142.