Combinatorial results for order-preserving partial injective contraction mappings

Abstract

Let ${\mathcal{I}}_n$ be the symmetric inverse semigroup on $X_n=\{1,2,\dots ,n\}$. Let ${\mathcal{O}\mathcal{C}\mathcal{I}}_n$ be the subsemigroup of ${\mathcal{I}}_n$ consisting of all order-preserving injective partial contraction mappings, and let ${\mathcal{O}\mathcal{D}\mathcal{C}\mathcal{I}}_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{O}\mathcal{C}\mathcal{I}}_n$ and ${\mathcal{O}\mathcal{D}\mathcal{C}\mathcal{I}}_n$ which lead naturally to obtaining the order of these semigroups. Then, we relate the formulae obtained to Fibonacci numbers. Similar results about ${\mathcal{O}\mathcal{R}\mathcal{C}\mathcal{I}}_n$, the semigroup of order-preserving or order-reversing injective partial contraction mappings, are deduced.

18 pages