Combinatorial results for order-preserving partial injective contraction mappings


  • Ahmed Bayo Musa Univesity of Ilorin
  • Nadia AlDhamri Sultan Quaboos University
  • Fatma Al-Kharousi Sultan Quaboos University
  • Georg Klein Universidade Federal da Bahia
  • Abdullahi Umar Khalifa University of Science and Technology


semigroups of transformations, partial injective contraction mappings


Let $ \mathcal{I}_n$ be the symmetric inverse semigroup on $X_n = \{1, 2, \ldots , n\}$. Let $\mathcal{OCI}_n$ be the subsemigroup of $\mathcal{I}_n$ consisting of all order-preserving injective partial contraction mappings, and let $\mathcal{ODCI}_n$ be the subsemigroup of $\mathcal{I}_n$ consisting of all order-preserving and order-decreasing injective partial contraction mappings of $X_n$. In this paper, we investigate the cardinalities of some equivalences on $\mathcal{OCI}_n$ and $\mathcal{ODCI}_n$ which lead naturally to obtaining the order of these semigroups. Then, we relate the formulae obtained to Fibonacci numbers. Similar results about $\mathcal{ORCI}_n$, the semigroup of order-preserving or order-reversing injective partial contraction mappings, are deduced.


[1] F. Al-Kharousi, G. U. Garba, M. J. Ibrahim, A. T. Imam, and A. Umar, On the semigroup of finite order-preserving partial injective contraction mappings. (Submitted ).

[2] F. Al-Kharousi, R. Kehinde, and A. Umar, Combinatorial results for certain semigroups of partial isometries of a finite chain. Australas. J. Combin. 58 (2014), 365–375.

[3] F. Al-Kharousi, R. Kehinde, and A. Umar, Combinatorial results for certain semigroups of order-decreasing partial isometries of a finite chain. arXiv:1702.04485.

[4] A. D. Adeshola, and A. Umar, Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain. J. Combin. Math. Combin. Comput., (2017) (To appear).

[5] E. Barcucci, R. Pinzani, and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations. Lecture Notes in Comput. Sci. 668 (1993), 282–298.

[6] D. Borwein, S. Rankin, and L. Renner, Enumeration of injective partial transformations. Discrete Math. 73 (1989), 291–296.

[7] S. Epp, Discrete mathematics with applications, 4th Edition. Brooks/Cole, Boston, MA, 2011.

[8] V. H. Fernandes, The monoid of all injective orientation-preserving partial transformations on a finite chain. Comm. Algebra 28 (2000), 3401–3426.

[9] V. H. Fernandes, G. M. S. Gomes, and M. M. Jesus, The cardinal and idempotent number of various monoids of transformations on a finite chain. Bull. Malays. Math. Sci. Soc. 34 (2011), 79–85.

[10] G. U. Garba, Nilpotents in semigroups of partial one-to-one order-preserving mappings. Semigroup Forum 48 (1994), 37–49.

[11] H. W. Gould, Combinatorial identities. A standardized set of tables listing 500 binomial coefficient summations., Morgantown, W.Va., 1972.

[12] R. P. Grimaldi, Fibonacci and Catalan numbers. An introduction., John Wiley & Sons, 2012.

[13] J. M. Howie, Fundamentals of semigroup theory. London Mathematical Society Monographs. New series, 12. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1995.

[14] A. Laradji and A. Umar, Combinatorial results for the symmetric inverse semigroup. Semigroup Forum 75 (2007), 221–236.

[15] S. Lipscomb, Symmetric Inverse Semigroups, Mathematical Surveys and Monographs, 46. American mathematical Society, Providence, R. I., 1996.

[16] S. Rinaldi and D. G. Rogers, How the odd terms in the Fibonacci sequence stack up. Math. Gaz., 90
(2006), 431–442.

[17] J. Riordan, Combinatorial identities. Reprint of the 1968 original. Robert E. Krieger Publishing Co., Huntington, N.Y., 1979.

[18] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at

[19] A. Umar, On the semigroups of partial one-to-one order-decreasing finite transformations, Proc. Roy. Soc. Edinburgh, Sect. A, 123 (1993), 355–363.

[20] A. Umar, Some combinatorial problems in the theory of symmetric inverse semigroups. Algebra Discrete Math. 9 (2010), 115–126.