On the Number of Idempotent Partial Contraction Mappings of a Finite Chain ()
1. Introduction
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 [1] 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 [2] [3] [4] [5]. While the papers [2] [4] [5] investigated algebraic properties of various semigroups of contraction mappings of a finite chain, Adeshola and Umar [3] 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 [3] [6] - [17], 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 [17]. It is fairly obvious that the number of full and partial transformation idempotents of
denoted by
and
are, respectively,
[14] and
[18].
However, at least two non-trivial cases are worth mentioning. In an elegant paper in 1971, Howie [10] 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 [3] 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 [19].
For standard concepts in semigroup and transformation semigroup theory, see for example [8] [9]. In particular, the set of idempotents of a semigroup S is denoted by
.
2. The Semigroup
Our approach is essentially that of [20]. 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 ( [20], 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
(1)
Replacing n by
we get
(2)
Subtracting (2) from (1) we get
which implies (by iteration)
as required.
We also have
Lemma 2.6. For
,
.
Next, we state and prove an analogue of ( [20], 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 [21] ), 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
as required.
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 [17], for natural numbers
we define
(3)
(4)
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
Finally, notice that we may recover Theorem 2.8 from either of the two corollories above. For some selected values of
and
in
see Table 1 and Table 2 below:
Table 1. Some selected values of
in
.
Table 2. Some selected values of
in
.
3. The Semigroup
Let
●
,
●
.
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)
as required.
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
Finally, notice that we may recover Theorem 3.4 from either of the two corollories above. For some selected values of
and
in
see Table 3 and Table 4 below:
Table 3. Some selected values of
in
.
Table 4. Some selected values of
in
.
Remark 3.9. The sequence
, is recorded (in [19] ) as A005183.
Support
Financial support from TRC Grant No: RC/SCI/DOMS/13/01 is gratefully acknowledged.