Back
 OJDM  Vol.11 No.3 , July 2021
On the Number of Idempotent Partial Contraction Mappings of a Finite Chain
Abstract: Let be the partial symmetric semigroup on and let and be its subsemigroups of order-preserving contractions and order-preserving, order-decreasing contractions mappings of , respectively. In this paper we investigate the cardinalities of and , the set idempotents of and , respectively. We also investigate the cardinalities of certain equivalences on and .

1. Introduction

Let X n = { 1 , 2 , , n } . A (partial) transformation α : Dom α X n Im α X n is said to be full or total if Dom α = X n ; otherwise it is called strictly partial. The set of partial transformations of X n , denoted by P n , 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 X n , denoted by T n , 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 ( x ) α (or simply x α ) instead of α ( x ) . This is called the right-hand notation and it has the advantage that composition of maps is read from left to right, that is, ( x ) α β = ( ( x ) α ) β . Further, a transformation α P n is said to be order-preserving (order-reversing) if ( x , y Dom α ) x y x α y α ( x α y α ) and, a contraction mapping (or simply a contraction) if ( x , y Dom α ) | x y | | x α y α | . We shall denote by O C P n and O D C P n , the semigroups of order-preserving partial contractions and of order-preserving, order-decreasing partial contractions of X n , respectively.

Recently, Zhao and Yang [1] initiated the algebraic study of semigroups of order-preserving partial contractions of X n , 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, O C T n and its subsemigroup of order-decreasing full contraction mappings, O D C T n . This paper investigates the combinatorial properties of the set of idempotents of O C P n and O D C P n and of certain natural equivalences on them.

An element e in a semigroup S, is said to be an idempotent if e 2 = e . 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 X n denoted by | E ( T n ) | and | E ( P n ) | are, respectively,

| E ( T n ) | = p = 0 n ( n p ) p n p [14] and | E ( P n ) | = p = 0 n ( n p ) ( p + 1 ) n p [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 | E ( O n ) | is

| E ( O n ) | = f 2 n ,

where f m denotes the mth Fibonacci number, defined recursively for m > 2 by

f 1 = f 2 = 1 , f m = f m 1 + f m 2 .

More recently, Adeshola and Umar [3] showed that the number of full order-preserving contraction idempotents denoted by | E ( O C T n ) | is

| E ( O C T n ) | = n ( n + 1 ) / 2 = ( n + 1 2 ) .

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 E ( O C P n ) . In Section 3 we obtain the analogues of the results from Section 2 for E ( O D C P n ) . These cardinalities lead to formulae for the orders of E ( O C P n ) and E ( O D C P n ) 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 E ( S ) .

2. The Semigroup O C P n

Our approach is essentially that of [20]. For α P n define F ( α ) = { x [ n ] : x α = x } as the set of fixed points of α , and let

e n = | E ( O C P n ) | ,

β n = | { α E ( O C P n ) : F ( α ) = } | ,

u n = | { α E ( O C P n ) : { 1 } F ( α ) } | ,

v n = | { α E ( O C P n ) : F ( α ) = { 1 } } | = | { α E ( O C P n ) : F ( α ) = { n } } | ,

a n = | { α E ( O C P n ) : { 1 , n } F ( α ) } | ,

γ n = | { α E ( O C P n ) : F ( α ) = { 1 , n } | .

Then we have the following results:

Lemma 2.1. For n 1 , γ n = 1 , and γ 0 = 0 .

Lemma 2.2. For n 2 , a n = 2 n 2 , a 1 = 1 and a 0 = 0 .

Proof. Let α E ( O C P n ) be such that { 1, n } F ( α ) . It is clear that for all x X n \ { 1, n } either x Dom α or x Dom α . In the former, we must have x α = x and there are n 2 choices for x. Thus each x has two degrees of freedom. The result is clear when n = 1 .

Lemma 2.3. For n 1 , v n = 2 n 1 , and v 0 = 0 .

Proof. Let α E ( O C P n ) be such that { 1 } = F ( α ) = Im α . Then for all x Dom α , we must have x α = 1 , 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 n 2 , u n = v n + γ 2 u n 1 + + γ n u 1 .

Proof. u n v n is the number of maps α O C P n with 1 α = 1 and i α = i for some i > 1 : if r is the smallest integer greater than 1 such that r α = r ; then clearly the number of such maps α is r = 2 n γ r u n r + 1 , as required.

This leads to the following lemma:

Lemma 2.5. For n 1 , u n = 2 n 2 ( n + 1 ) , and u 0 = 0 .

Proof. Substituting γ n and v n with 1 and 2 n 1 , respectively into Lemma 2.4 we get

u n = 2 n 1 + u n 1 + u n 2 + + u 1 (1)

Replacing n by n 1 we get

u n 1 = 2 n 2 + u n 2 + u n 3 + + u 1 (2)

Subtracting (2) from (1) we get

u n = 2 n 2 + 2 u n 1 ,

which implies (by iteration)

u n = 2 n 2 ( n + 1 ) ,

as required.

We also have

Lemma 2.6. For n 0 , β n = 1 .

Next, we state and prove an analogue of ( [20], Lemma 5) which will be useful in what follows.

Lemma 2.7. For n 2 , e n = β n + v 1 u n 1 + v 2 u n 2 + + v n u 1 .

Proof. The nilpotents of O C P n are precisely those that do not have fixed points (see [21] ), hence e n β n is the number of maps α O C P n with at least one fixed point. If u n , r is the number of such maps α with r as the smallest fixed point, then u n , r = v r u n r + 1 . Hence e n β n = r = 1 n v r u n r + 1 . 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 n 0 , e n = 1 + 2 n 3 n ( n + 3 ) .

Proof. Using Lemmas 2.5, 2.6 & 2.7 we see that

e n = 1 + 2 0 × 2 n 2 ( n + 1 ) + 2 1 × 2 n 3 n + 2 2 × 2 n 4 ( n 1 ) + + 2 n 2 × 2 0 × 3 + 2 n 1 × 2 1 × 2 = 1 + 2 n 2 [ ( n + 1 ) + n + ( n 1 ) + + 3 + 2 + 1 1 ] = 1 + 2 n 2 [ ( n + 1 ) ( n + 2 ) / 2 1 ] = 1 + 2 n 3 n ( n + 3 ) ,

as required.

Now we let e ( x ) be the (ordinary) generating functions of the sequence e n above. The proof of the next result is routine using Theorem 2.8 above.

Theorem 2.9. e ( x ) = n 0 e n x n = 1 5 x + 10 x 2 6 x 3 ( 1 x ) ( 1 2 x ) 3 = ( 1 x ) ( 1 4 x + 6 x 2 ) ( 1 x ) ( 1 2 x ) 3 .

As in Umar [17], for natural numbers n k p 0 we define

F p k ( n ; p , k ) = F ( n ; p , k ) = | { α S : h ( α ) = | Im α | = p , w + ( α ) = k } | , (3)

F p ( n ; p ) = F ( n ; p ) = | { α S : h ( α ) = | Im α | = p } | , F k ( n ; k ) = F ( n ; k ) = | { α S : w + ( α ) = k } | . (4)

Then we have

Proposition 2.10. Let S = E ( O C P n ) . Then F p k ( n ; 1, k ) = 2 n 1 and

F ( n ; p , k ) = t = 1 k p + 1 ( k t + 1 p 2 ) 2 n ( k t + 1 ) , ( n k p 2 ) .

Proof. Let α E ( O C P n ) be such that h ( α ) = | Im α | = p and w + ( α ) = k . First, notice that if p = 1 then { k } = F ( α ) = Im α , and so k α = k . Now for all x [ n ] \ { k } there are two degrees of freedom: x Dom α and x α = k ; or x Dom α . Hence F p k ( n ; 1, k ) = 2 n 1 .

Next, let t = min ( Im α ) then t { 1,2, , k p + 1 } . Next, note that we can

choose the remaining p 2 elements of F ( α ) in ( k t + 1 p 2 ) ways, since

t , k Im α = F ( α ) Dom α . Similarly, the remaining elements of Dom α can be chosen from { 1,2, , t 1 } { k + 1, k + 2, , n } in 2 t 1 2 n k = 2 n ( k t + 1 ) 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 S = E ( O C P n ) . Then F k ( n ; 0 ) = 1 and

F ( n ; k ) = ( k + 1 ) 2 n 2 , ( n k 1 ) .

Corollary 2.12. Let S = E ( O C P n ) . Then F p ( n ; 0 ) = 1 , F p ( n ; 1 ) = n 2 n 1 and

F ( n ; p ) = k = p n t = 1 k p + 1 ( k t + 1 p 2 ) 2 n ( k t + 1 ) , ( n p 2 ) .

Finally, notice that we may recover Theorem 2.8 from either of the two corollories above. For some selected values of F ( n ; k ) and F ( n ; p ) in E ( O C P n ) see Table 1 and Table 2 below:

Table 1. Some selected values of F ( n ; k ) in E ( O C P n ) .

Table 2. Some selected values of F ( n ; p ) in E ( O C P n ) .

3. The Semigroup O D C P n

Let

d n = | E ( O D C P n ) | ,

z n = | { α E ( O D C P n ) : F ( α ) = { n } } | .

Then observe that Lemmas 2.1, 2.2, 2.4, 2.5 & 2.6 are all valid if we replace O C P n with O D C P n . Moreover, in contrast to Lemma 2.3 we have

Lemma 3.1. For n 1 , z n = 1 .

To prove the main result of this section, the following lemma (which can be proved by induction) will be needed:

Lemma 3.2. For n 1 , we have i = 1 n i 2 n i = 2 n + 1 ( n + 2 ) .

An analogue of Lemma 2.7 will also be needed.

Lemma 3.3. For n 2 , d n = β n + z 1 u n 1 + z 2 u n 2 + + z n u 1 .

Thus we can now state and prove one of the main results of this section.

Theorem 3.4. For n 0 , d n = 1 + n 2 n 1 .

Proof. Using Lemmas 2.5, 2.6, 3.1 & 3.3 we see that

d n = 1 + 2 n 2 ( n + 1 ) + 2 n 3 n + 2 n 4 ( n 1 ) + + 2 0 [ n ( n 3 ) ] + 1

= 2 + n [ 2 n 2 + 2 n 3 + + 2 0 ] + 2 n 2 [ 2 n 4 2 × 2 n 5 3 × 2 n 6 ( n 3 ) × 2 0 ]

= 2 + n ( 2 n 1 1 ) + 2 n 2 [ 2 n 2 ( n 1 ) ] (by Lemma 3.2)

= 1 + n 2 n 1 ,

as required.

Now we let d ( x ) 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. d ( x ) = n 0 d n x n = 1 3 x + 3 x 2 ( 1 x ) ( 1 2 x ) 2 = ( 1 x ) 3 + x 3 ( 1 x ) ( 1 2 x ) 2 .

As in the previous section we obtain expressions for the following combinatorial functions.

Proposition 3.6. Let S = E ( O D C P n ) . Then

F ( n ; p , k ) = ( k 1 p 1 ) 2 n k , ( n k p 0 ) .

Proof. Let α E ( O D C P n ) be such that h ( α ) = | Im α | = p and w + ( α ) = k .

First, note that we can choose the remaining p 1 elements of F ( α ) in ( k 1 p 1 )

ways, since k Im α = F ( α ) Dom α . Similarly, the remaining elements of Dom α can be chosen from [ n ] \ { 1,2, , k } in 2 n k ways, as each has two degrees of freedom: x α = k or x Dom α .

Immediately, we deduce the following

Corollary 3.7. Let S = E ( O D C P n ) . Then F k ( n ; 0 ) = 1 and F ( n ; k ) = 2 n 1 , ( n k 1 ) .

Corollary 3.8. Let S = E ( O D C P n ) . Then F p ( n ; 0 ) = 1 and

F ( n ; p ) = k = p n ( k 1 p 1 ) 2 n k , ( n p 1 ) .

Finally, notice that we may recover Theorem 3.4 from either of the two corollories above. For some selected values of F ( n ; k ) and F ( n ; p ) in E ( O D C P n ) see Table 3 and Table 4 below:

Table 3. Some selected values of F ( n ; k ) in E ( O D C P n ) .

Table 4. Some selected values of F ( n ; p ) in E ( O D C P n ) .

Remark 3.9. The sequence d n , is recorded (in [19] ) as A005183.

Support

Financial support from TRC Grant No: RC/SCI/DOMS/13/01 is gratefully acknowledged.

Cite this paper: Ojo, O. , Al-Kharousi, F. and Umar, A. (2021) On the Number of Idempotent Partial Contraction Mappings of a Finite Chain. Open Journal of Discrete Mathematics, 11, 94-101. doi: 10.4236/ojdm.2021.113007.
References

[1]   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.
https://doi.org/10.4134/BKMS.2012.49.5.1015

[2]   Ali, B., Umar, A. and Zubairu, M.M. (2018) Regularity and Green’s Relations on the Semigroup of Partial Contractions of a Finite Chain.

[3]   Adeshola, A.D. and Umar, A. (2018) Combinatorial Results for Certain Semigroups of Order-Preserving Full Contraction Mappings of a Finite Chain. JCMCC, 106, 37-49.

[4]   Ali, B., Umar, A. and Zubairu, M.M. (2018) Regularity and Green’s Relations on the Semigroup of Partial and Full Contractions of a Finite Chain.

[5]   Umar, A. and Zubairu, M.M. (2018) On Certain Semigroups of Partial Contractions of a Finite Chain.

[6]   Borwein, D., Rankin, S. and Renner, L. (1989) Enumeration of Injective Partial Transformations. Discrete Mathematics, 73, 291-296.
https://doi.org/10.1016/0012-365X(89)90272-0

[7]   Clifford, A.H. and Preston, G.B. (1961) The Algebraic Theory of Semigroups, Vol. 1. American Mathematical Society, Providence.

[8]   Ganyushkin, O. and Mazorchuk, V. (2009) Classical Finite Transformation Semigroups: An Introduction. Springer, London.
https://doi.org/10.1007/978-1-84800-281-4

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

[10]   Howie, J.M. (1971) Products of Idempotents in Certain Semigroups of Transformations. Proceedings of the Edinburgh Mathematical Society, 17, 223-236.
https://doi.org/10.1017/S0013091500026936

[11]   Laradji, A. and Umar, A. (2004) Combinatorial Results for Semigroups of Order-Preserving Partial Transformations. Journal of Algebra, 278, 342-359.

[12]   Laradji, A. and Umar, A. (2004) Combinatorial Results for Semigroups of Order-Decreasing Partial Transformations. Journal of Integer Sequences, 7, Article 04.3.8.

[13]   Laradji, A. and Umar, A. (2006) Combinatorial Results for Semigroups of Order-Preserving Full Transformations. Semigroup Forum, 72, 51-62.
https://doi.org/10.1007/s00233-005-0553-6

[14]   Tainiter, T. (1968) A Characterization of Idempotents in Semigroups. The Journal of Combinatorial Theory, 5, 370-373.
https://doi.org/10.1016/S0021-9800(68)80012-2

[15]   Umar, A. (1992) On the Semigroups of Order-Decreasing Finite Full Transformations. Proceedings of the Royal Society of Edinburgh Section A, 120, 129-142.
https://doi.org/10.1017/S0308210500015031

[16]   Umar, A. (1998) Enumeration of Certain Finite Semigroups of Transformations. Discrete Mathematics, 89, 291-297.

[17]   Umar, A. (2014) Some Combinatorial Problems in the Theory of Partial Transformation Semigroups. Algebra Discrete Mathematics, 17, 110-134.

[18]   Garba, G.U. (1990) Idempotents in Partial Transformation Semigroups. Proceedings of the Royal Society of Edinburgh Section A, 116, 359-366.

[19]   Sloane, N.J.A. (2011) The On-Line Encyclopedia of Integer Sequences.
https://oeis.org

[20]   Laradji, A. (2019) On Order-Preserving Partial Transformations with Prescribed Number of Fixed Points. Technical Report No. 298, (June) Department of Mathematical Sciences, KFUPM, Dhahran.

[21]   Garba, G.U. (1994) Nilpotents in Semigroups of Partial Order-Preserving Transformations. Proceedings of the Edinburgh Mathematical Society, 37, 361-377.
https://doi.org/10.1017/S001309150001885X

 
 
Top