Combinatorial Results for Semigroups of Orientation-Preserving Partial Transformations

A. Umar Department of Mathematics and Statistics Sultan Qaboos University Al-Khod, PC 123 Sultanate of Oman

                   aumarh@squ.edu.om

Abstract

Let X_{n} = {1, 2, …, n}. On a partial transformation α : Dom α ⊆ X_{n} → Im α ⊆ X_{n} of X_{n} the following parameters are defined: the breadth or width of α is | Dom α |, the height of α is | Im α |, and the right (resp., left) waist of α is max(Im α) (resp., min(Im α)). We compute the cardinalities of some equivalences defined by equalities of these parameters on OP_{n}, the semigroup of orientation-preserving full transformations of X_{n}, POP_{n} the semigroup of orientation-preserving partial transformations of X_{n}, OR_{n} the semigroup of orientation-preserving/reversing full transformations of X_{n}, and POR_{n} the semigroup of orientation-preserving/reversing partial transformations of X_{n}, and their partial one-to-one analogue semigroups, POPI_{n} and PORI_{n}.

1 Introduction and Preliminaries

Let X_{n} = {1, 2, …, n}. A (partial) transformation α : Dom α ⊆ X_{n} → Im α ⊆ X_{n} is said to be full or total if Im α = X_{n}; otherwise it is called strictly partial. The breadth or width of α is denoted and defined by b(α) =| Dom α |. The height or rank of α is denoted and defined by h(α) =| Im α |. The right (resp., left) waist of α is denoted and defined by w^{+}(α) = max(Im α) (resp., w^{−}(α) = min(Dom α)). Of course, other parameters have been defined and many more could still be defined but we shall restrict ourselves to only these in this paper. It is worth noting that to define the left (right) waist of a transformation the base set X_{n} must be totally ordered. The main objects of study in this paper are OP_{n}, the semigroup of orientation-preserving full transformations of X_{n}, POP_{n} the semigroup of orientation-preserving partial transformations of X_{n}, OR_{n} the semigroup of orientation-preserving/reversing full transformations of X_{n}, and POR_{n} the semigroup of orientation-preserving/reversing partial transformations of X_{n}, and their partial one-to-one analogue semigroups, POPI_{n} and PORI_{n}. For basic and standard concepts in transformation semigroup theory the reader may consult one of Howie [10], Higgins [7] or Ganyushkin and Mazorchuk [6].

Enumerative results of an essentially combinatorial nature in the study of semigroups of transformations are now numerous and interesting to warrant sections and plenty of exercises in [6] and survey articles [9, 5, 19, 20]. These enumeration problems lead to many numbers in Sloane’s encyclopaedia of integer sequences [18] but there is also the likelihood of finding others that may not yet be recorded in [18]. Motivated by Higgins [8], Laradji and Umar wrote a series of papers [11, 12, 13, 14, 15] dealing exclusively with combinatorial questions.

Let S be a set of partial transformations on X_{n}. Next, let

F (n; r, p, k) =| {α ∈ S : b(α) = r ∧ h(α) = p ∧ w^{+}(α) = k} |,

and let P = {r, p, k} be the set of counters for the breadth, height, and right waist of a transformation. Then any 3-parameter combinatorial function can be expressed as F (n; a_{1}, a_{2}), where {a_{1}, a_{2}} ⊂ P. For example,

F (n; r, p) =| {α ∈ S : b(α) = r ∧ h(α) = p} | .

Similarly, any 2-parameter combinatorial function can be expressed as F (n; a_{1}). It is not difficult to see that

|S| = ∑_{a_{1}} F (n; a_{1}), F (n; a_{1}) = ∑_{a_{2}} F (n; a_{1}, a_{2}).

We note also that certain special cases of these combinatorial functions, when two or more parameters are equal or when these parameters take extreme values are worth pointing out, see for example, [13, 14].

In Section 2 we consider the semigroups of orientation-preserving full and partial transformations OP_{n} and POP_{n}, while in Section 3 we consider OR_{n} and POR_{n}, the semigroups of orientation-preserving/reversing full and partial transformations of X_{n}, respectively. And finally, in Section 4 we consider the partial one-to-one analogues of the earlier considered classes of semigroups, POPI_{n} and PORI_{n}. We conclude this section with a list of results that will be needed in our proofs.

Lemma 1. Let α be a partial transformation of X_{n} = {1, 2, …, n}. Let r = b(α), p = h(α) and k = w^{+}(α). Then we have the following:

1. n ≥ r ≥ p ≥ 0;

2. n ≥ k ≥ p ≥ 0;

3. r = 1 ⟹ p = 1; 4. k = 1 ⟹ p = 1;

5. r = 0 ⇔ p = 0 ⇔ k = 0.

Lemma 2. For all natural number n we have

∑_{i=1}^{n}(i − 1)\binom{n}{i} = (n − 2)2^{n−1} + 1.

Proof.

∑_{i=1}^{n}(i − 1)\binom{n}{i} = n ∑_{i=1}^{n} \binom{n − 1}{i − 1} − ∑_{i=1}^{n} \binom{n}{i} = n2^{n−1} − (2^{n} − 1) = (n − 2)2^{n−1} + 1.

Lemma 3. (Vandemonde’s Convolution Identity, [17, (3a), p. 8]). For all natural numbers m, n and p we have

∑_{k=0}^{n} \binom{n}{m − k}\binom{p}{k} = \binom{n + p}{m}.

Lemma 4. [13, Lemma 1.3] For all natural numbers n and p we have

∑_{k=p}^{n} \binom{k − 1}{p − 1} = \binom{n}{p}.

2 Orientation-Preserving Partial Transformations

Let a = (a_{1}, a_{2}, …, a_{t}) be a sequence of t (t > 0) elements from the chain X_{n}. We say that a is cyclic if there exists no more than one index i ∈ {1, 2, …, t} such that a_{i} > a_{i+1}, where a_{t+1} denotes a_{1}. For a partial transformation α of X_{n}, suppose that Dom α = {a_{1}, a_{2}, …, a_{t}}, with t ≥ 0 and a_{1} < a_{2} < … < a_{t}. We say that α is orientation-preserving if (a_{1}α, a_{2}α, …, a_{t}α) is cyclic. The semigroups of orientation-preserving full and partial transformations of X_{n} will be denoted by OP_{n} and POP_{n}, respectively. Moreover, note that for all α ∈ POP_{n} and y ∈ Im α, yα^{−1} is convex with respect to Dom α and the circular order. Further note that to partition Dom α into p nonempty convex subsets, we insert p symbols between the r = | Dom α| spaces. Then we have the principal result of this section.

Proposition 5. Let S = POP_{n}. Then

F (n; r, p, k) = \begin{cases}\binom{n}{r}\binom{k−1}{p−1}\binom{r}{p}p, & n ≥ r, k ≥ p > 1; \\ \binom{n}{r}, & r = 1 or k = 1 or p = 1. \end{cases}

Proof. First, note that we can choose the r elements of Dom α from X_{n} in \binom{n}{r} ways, and the p elements of Im α from \{1, 2, …, k\} in \binom{k−1}{p−1} ways, since k must be one of the choices. Next, we partition the r chosen elements of the domain into p-convex subsets in \binom{r}{p} ways. It is clear that that there are exactly p ways of tying these p-subsets to the p-images. Hence the result follows.

Let a ∈ P = {r, p, k}. Then for all i ∈ {0, 1, …, n} if a = i we shall denote this by a_{i}.

Corollary 6. Let S = POP_{n}. Then

F (n; r, p) = \begin{cases}\binom{n}{r}\binom{n}{p}\binom{r}{p}p, & n ≥ r ≥ p > 1; \\ n\binom{n}{r}, & r = 1 or p = 1. \end{cases}

Proof.

F (n; r, p) = ∑_{k=p}^{n} F (n; r, p, k) = ∑_{k=p}^{n} \binom{n}{r}\binom{k − 1}{p − 1}\binom{r}{p}p (r ≥ p ≥ 2)

= p\binom{n}{r}\binom{r}{p} ∑_{k=p≥2}^{n} \binom{k − 1}{p − 1} = \binom{n}{r}\binom{r}{p}\binom{n}{p}p (by Lemma 4).

Moreover, it is not difficult to see that F (n; r_{1}, p_{1}) = n^{2} and F (n; r, p_{1}) = n\binom{n}{r}. Hence the result follows.

Corollary 7. Let S = POP_{n}. Then

F (n; r, k) = r\binom{n}{r}\binom{r + k − 2}{r − 1} − (r − 1)\binom{n}{r},

for n ≥ r, k ≥ 1.

Proof.

F (n; r, k) = ∑_{p=1}^{k} F (n; r, p, k) = \binom{n}{r} + ∑_{p=2}^{n} \binom{n}{r}\binom{k − 1}{p − 1}\binom{r}{p}p (r, k ≥ 2)

= \binom{n}{r} + ∑_{p=1}^{n} \binom{n}{r}\binom{k − 1}{p − 1}\binom{r}{p}p − r\binom{n}{r}

= r\binom{n}{r} ∑_{p=1}^{n} \binom{k − 1}{p − 1}\binom{r − 1}{p − 1} − (r − 1)\binom{n}{r}

= r\binom{n}{r}\binom{r + k − 2}{r − 1} − (r − 1)\binom{n}{r} (by Lemma 3).

Moreover, it is not difficult to see that F (n; r_{1}, k) = n and F (n; r, k_{1}) = \binom{n}{r}. Hence the result follows.

Corollary 8. Let S = POP_{n}. Then

F (n; p, k) = \begin{cases}p2^{n−p}\binom{n}{p}\binom{k−1}{p−1}, & n ≥ k ≥ p > 1; \\ 2^{n} − 1, & k = 1 or p = 1. \end{cases}

Proof.

F (n; p, k) = ∑_{r=p}^{k} F (n; r, p, k) = ∑_{r=2}^{n} \binom{n}{r}\binom{k − 1}{p − 1}\binom{r}{p}p (k ≥ p ≥ 2)

= p\binom{k − 1}{p − 1} ∑_{r=2}^{n} \binom{n}{r}\binom{r}{p} = p\binom{k − 1}{p − 1}\binom{n}{p} ∑_{r=2}^{n} \binom{n − p}{r − p}

= p2^{n−p}\binom{k − 1}{p − 1}\binom{n}{p}.

Moreover, it is not difficult to see that F (n; p_{1}, k) = F (n; p, k_{1}) = 2^{n} − 1. Hence the result follows.

Corollary 9. Let S = POP_{n}. Then

F (n; r) = \begin{cases}r\binom{n}{r}\binom{n+r−1}{n−1} − n(r − 1)\binom{n}{r}, & n ≥ r ≥ 1; \\ 1, & r = 0. \end{cases}

Proof.

F (n; r) = ∑_{p=1}^{r} F (n; r, p) = n\binom{n}{r} + ∑_{p=2}^{r} \binom{n}{r}\binom{r}{p}\binom{n}{p}p (r ≥ 2)

= n\binom{n}{r} + \binom{n}{r} ∑_{p=1}^{r} \binom{r}{p}\binom{n}{p}p − rn\binom{n}{r}

= r\binom{n}{r} ∑_{p=1}^{r} \binom{r − 1}{p − 1}\binom{n}{p} − n(r − 1)\binom{n}{r}

= r\binom{n}{r}\binom{n + r − 1}{r} − n(r − 1)\binom{n}{r} (by Lemma 3).

Moreover, it is not difficult to see that F (n; r_{1}) = n^{2} and F (n; r_{0}) = 1. Hence the result follows. Alternatively, we can get the same result from F (n; r) = ∑_{k=1}^{n} F (n; r, k).

Corollary 10. Let S = POP_{n}. Then

F (n; p) = \begin{cases}p2^{n−p}\binom{n}{p}^{2}, & n ≥ p > 1; \\ n(2^{n} − 1), & p = 1; \\ 1, & p = 0. \end{cases}

Proof.

F (n; p) = ∑_{r=p}^{n} F (n; r, p) = ∑_{r=p}^{n} \binom{n}{r}\binom{r}{p}\binom{n}{p}p (p ≥ 2)

= p\binom{n}{p} ∑_{r=p}^{n} \binom{n}{r}\binom{r}{p} = p\binom{n}{p}^{2} ∑_{r=p}^{n} \binom{n − p}{r − p}

= p2^{n−p}\binom{n}{p}^{2}.

It is not difficult to see that F (n; p_{1}) = n(2^{n} − 1) and F (n; p_{0}) = 1. Hence the result follows. Alternatively, we can get the same result from F (n; p) = ∑_{k=p}^{n} F (n; p, k).

Corollary 11. Let S = POP_{n}. Then

F (n; k) = \begin{cases}n ∑_{r=1}^{n} \binom{n−1}{r−1}\binom{r+k−2}{r−1} − (n − 2)2^{n−1} − 1, & n ≥ k ≥ 1; \\ 1, & k = 0. \end{cases}

Proof.

F (n; k) = ∑_{r=1}^{n} F (n; r, k) = n + ∑_{r=2}^{n}[r\binom{n}{r}\binom{r + k − 2}{r − 1} − (r − 1)\binom{n}{r}] (k ≥ 2)

= n + n ∑_{r=2}^{n} \binom{n − 1}{r − 1}\binom{r + k − 2}{r − 1} − ((n − 2)2^{n−1} + 1) (by Lemma 2)

= n ∑_{r=1}^{n} \binom{n − 1}{r − 1}\binom{r + k − 2}{r − 1} − (n − 2)2^{n−1} − 1.

It is not difficult to see that F (n; k_{1}) = n(2^{n} − 1) and for convenience we set F (n; k_{0}) = 1. Hence the result follows. Alternatively, we get

F (n; k) = ∑_{p=1}^{k} F (n; p, k) = (2^{n} − 1) + ∑_{p=2}^{k} p\binom{k − 1}{p − 1}\binom{n}{p}2^{n−p} (k ≥ 2)

= (2^{n} − 1) + n ∑_{p=2}^{k} \binom{k − 1}{p − 1}\binom{n − 1}{p − 1}2^{n−p}

= (2^{n} − 1) + n ∑_{p=1}^{k} \binom{k − 1}{p − 1}\binom{n − 1}{p − 1}2^{n−p} − n2^{n−1}

= n ∑_{p=1}^{k} \binom{k − 1}{p − 1}\binom{n − 1}{p − 1}2^{n−p} − (n − 2)2^{n−1} − 1.

From the proof of Corollary 11 we deduce the following non-trivial identity. Proposition 12. For all natural numbers n and k we have

∑_{r=1}^{n} \binom{n − 1}{r − 1}\binom{r + k − 2}{r − 1} = ∑_{r=1}^{k} \binom{k − 1}{r − 1}\binom{n − 1}{r − 1}2^{n−r}.

We can now deduce the order of POP_{n}. The first expression is [4, Proposition 1.9]. Corollary 13. For all natural number n we have

| POP_{n} | = 1 + n(2^{n} − 1) + ∑_{p=2}^{n} p2^{n−p}\binom{n}{p}^{2}
= 1 + n ∑_{r=1}^{n} \binom{n − 1}{r − 1}\binom{n + r − 1}{n − 1} − n(n − 2)2^{n−1} − n.

Corollary 14. Let S = OP_{n}. Then

\begin{cases}\binom{k−1}{p−1}\binom{n}{p}p, & n ≥ k ≥ p > 1; \\ 1, & k = 1 or p = 1. \end{cases}

Proof. The result follows by the substitution r = n in Proposition 5. Corollary 15. [1, p. 198] Let S = OP_{n}. Then

F (n; p) = \begin{cases}p\binom{n}{p}^{2}, & n ≥ p > 1; \\ n, & p = 1. \end{cases}

Corollary 16. Let S = OP_{n}. Then

F (n; k) = \begin{cases}n\binom{n+k−2}{k−1} − (n − 1), & n ≥ k > 1; \\ 1, & k = 1. \end{cases}

Corollary 17. [16, Theorem 4.3] & [1, p. 194] For any natural number n we have

| OP_{n} |= \frac{n}{2}\binom{2n}{n} − n(n − 1).

Remark 18. The triangles of numbers F_{P OP} (n; r), F_{P OP} (n; p), F_{P OP} (n; k), F_{OP} (n; p) and F_{OP} (n; k) are as at the time of submitting this paper not in Sloane [18]. However, note that F_{P OP} (n, p_{1}) is [18, \underline{A066524}] and F_{OP} (n, k_{1}) is [18, \underline{A002061}].

n\r 0 1 2  3  4  5  6 ∑ F (n; r) =| POP_{n} |
0 1  1
1 1 1  2
2 1 4 4  9
3 1 9 27 24  61
4 1 16 96 208 128  449
5 1 25 250 950 1325 610  3161
6 1 36 540 3120 7290 7416 2742  21145

Table 2.1

n\p 0 1  2  3  4  5 6 ∑ F (n; p) =| POP_{n} |
0 1  1
1 1 1  2
2 1 6  2  9
3 1 21 36  3  61
4 1 60 288 96  4  449
5 1 155 1600 1200 200 5  3161
6 1 378 7200 9600 3600 360 6  21145

Table 2.2

n\k 0 1 2 3 4 5 6 ∑ F (n; k) =| POP_{n} |
0 1  1
1 1 1  2
2 1 3 5  9
3 1 7 19 34  61
4 1 15 63 135 235  449
5 1 31 191 471 911 1556  3161
6 1 63 543 1503 3183 5883 9969  21145

Table 2.3

n\p 1 2 3 4 5 6 7 ∑ F (n; p) =| OP_{n} |
1 1  1
2 2 2  4
3 3 18 3  24
4 4 72 48 4 128
5 5 200 300 100 5  610
6 6 450 1200 900 180 6  2742
7 7 882 3675 4900 2205 294 7  11970

Table 2.4

n\k 1 2 3 4 5 6 7 ∑ F (n; k) =| OP_{n} |
1 1  1
2 1 3  4
3 1 7 16  24
4 1 13 37 77  128
5 1 21 71 171 346  610
6 1 31 121 331 751 1507  2742
7 1 43 190 582 1464 3228 6462  11970

Table 2.5

3 Orientation-Preserving or Reversing Partial Transformations

Let a = (a_{1}, a_{2}, …, a_{t}) be a sequence of t (t > 0) elements from the chain X_{n}. We say that a is anti-cyclic if there exists no more than one index i ∈ {1, 2, …, t} such that a_{i} < a_{i+1}, where a_{t+1} denotes a_{1}. For a partial transformation α of X_{n}, suppose that Dom α = {a_{1}, a_{2}, …, a_{t}}, with t ≥ 0 and a_{1} < a_{2} < … < a_{t}. We say that α is orientation-reversing if (a_{1}α, a_{2}α, …, a_{t}α) is anti-cyclic. The semigroups of orientation-preserving or reversing full and partial transformations of X_{n} will be denoted by OR_{n} and POR_{n}, respectively.

Remark 19. For p = 1, 2 every orientation-preserving transformation is also orientationreversing but distinct otherwise [1, Lemma 1.1]. However, there is a bijection between the set of orientation-preserving transformations and that of orientation-reversing transformations [1, Lemma 5.1].

The proofs of all the results in this section are similar to the proofs of the corresponding results in Section 2, taking into account Remark 19.

Proposition 20. Let S = POR_{n}. Then

F (n; r, p, k) = \{ \begin{matrix}2\binom{n}{r}\binom{k−1}{p−1}\binom{r}{p}p, & n ≥ r, k ≥ p > 2; \\ 2(k − 1)\binom{n}{r}\binom{r}{2}, & n ≥ r, k ≥ p = 2; \\ \binom{n}{r}, & r = 1 or k = 1 or p = 1. \end{matrix}

Corollary 21. Let S = POR_{n}. Then

F (n; r, p) = \{ \begin{matrix}2\binom{n}{r}\binom{n}{p}\binom{r}{p}p, & r ≥ p > 2; \\ 2\binom{n}{r}\binom{r}{2}\binom{n}{2}, & n ≥ r ≥ p = 2; \\ n\binom{n}{r}, & r = 1 or p = 1. \end{matrix}

Corollary 22. Let S = POR_{n}. Then

F (n; r, k) = \{ \begin{matrix}\binom{n}{r}[2r\binom{r+k−2}{k−1} − (2r − 1) − 2(k − 1)\binom{r}{2}], & r, k > 2; \\ (2k − 1)\binom{n}{2}, & k ≥ r = 2; \\ \binom{n}{r} + 2\binom{n}{r}\binom{r}{2}, & r ≥ k = 2; \\ \binom{n}{r}, & r = 1 or k = 1. \end{matrix}

Corollary 23. Let S = POR_{n}. Then

F (n; p, k) = \{ \begin{matrix}p2^{n−p+1}\binom{k−1}{p−1}\binom{n}{p}p, & k ≥ p > 2; \\ 2^{n−1}\binom{n}{2} + 2^{n} − 1, & k = 2; \\ (k − 1)2^{n−1}\binom{n}{2}, & p = 2; \\ 2^{n} − 1, & k = 1 or p = 1. \end{matrix}

Corollary 24. Let S = POR_{n}. Then

F (n; r) = 2r\binom{n}{r}\binom{n + r − 1}{n − 1} − n(2r − 1)\binom{n}{r} − 2\binom{n}{r}\binom{r}{2}\binom{n}{2}, for r ≥ 1.

Corollary 25. Let S = POR_{n}. Then

F (n; p) = \{ \begin{matrix}p2^{n−p+1}\binom{n}{p}^{2}, & p > 2; \\ 2^{n−1}\binom{n}{2}^{2}, & p = 2; \\ n(2^{n} − 1), & p = 1. \end{matrix}

Corollary 26. Let S = POR_{n}. Then

F (n; k) = 2n ∑_{r=1}^{n} \binom{n − 1}{r − 1}\binom{r + k − 2}{r − 1} − (n − 1)2^{n} − 1 − (k − 1)2^{n−1}\binom{n}{2}
= 2n ∑_{p=1}^{k} \binom{k − 1}{p − 1}\binom{n − 1}{p − 1}2^{n−p} − (n − 1)2^{n} − 1 − (k − 1)2^{n−1}\binom{n}{2},

for k ≥ 1.

We can now deduce the order of POR_{n}. The first expression is [4, Proposition 1.10]. Corollary 27. For all natural number n we have

| POR_{n} | = 1 + n(2^{n} − 1) = 2^{n−1}\binom{n}{2}^{2} + ∑_{p=3}^{n} p2^{n−p+1}\binom{n}{p}^{2}
= 1 + 2n ∑_{r=1}^{n} \binom{n − 1}{r − 1}\binom{n + r − 1}{n − 1} − 2^{n−3}n(n − 1)(n^{2} − n + 8) − n.

Corollary 28. Let S = OR_{n}. Then

F (n; p, k) = \{ \begin{matrix}2\binom{k−1}{p−1}\binom{n}{p}p, & k ≥ p > 2; \\ \binom{k−1}{p−1}\binom{n}{p}p, & k ≥ p = 2; \\ 1, & k = 1 or p = 1. \end{matrix}

Corollary 29. Let S = OR_{n}. Then

F (n; p) = \{ \begin{matrix}2p\binom{n}{p}^{2}, & p > 2; \\ 2\binom{n}{2}^{2}, & p = 2; \\ n, & p = 1. \end{matrix}

Corollary 30. Let S = OR_{n}. Then

F (n; k) = 2n\binom{n + k − 2}{k − 1} − 2(k − 1)\binom{n}{2} − 2n + 1,

for k ≥ 1. Corollary 31. [16, Theorem 5.2] & [1, Theorem 5.5] For any natural number n we have

| OR_{n} |= n\binom{2n}{n} − n^{2}(n^{2} − 2n + 5)/2 + n.

Remark 32. The triangles of numbers F_{P OR}(n; r), F_{P OR}(n; p), F_{P OR}(n; k), F_{OR}(n; p) and F_{OR}(n; k) are as at the time of submitting this paper not in Sloane [18]. However, note that F_{P OR}(n; r_{1}) is [18, \underline{A000290}], F_{P OR}(n; p_{1}) is [18, \underline{A066524}], F_{P OR}(n; k_{1}) is [18, \underline{A000225}], F_{OR}(n; p_{1}) is [18, \underline{A163102}] and F_{OR}(n; k_{1}) is [18, \underline{A002061}].

n\r 0 1 2  3  4  5  6 ∑ F (n; r) =| POR_{n} |
0 1  1
1 1 1  2
2 1 4 4  9
3 1 9 27 27  64
4 1 16 96 256 180  549
5 1 25 250 1250 2025 1015  4566
6 1 36 540 4320 11790 12996 5028  34711

Table 3.1

n\p 0 1  2  3  4  5 6 ∑ F (n; p) =| POR_{n} |
0 1  1
1 1 1  2
2 1 6  2  9
3 1 21 36  6  64
4 1 60 288 192  8  549
5 1 155 1600 2400 400 10  4566
6 1 378 7200 19200 7200 720 12  34711

Table 3.2

n\k 0 1 2  3  4  5  6 ∑ F (n; k) =| POR_{n} |
0 1  1
1 1 1  2
2 1 3 5  9
3 1 7 19 37  64
4 1 15 63 159 311  549
5 1 31 191 591 1311 2441  4566
6 1 63 543 1983 4863 9783 17475  34711

Table 3.3

n\p 1 2  3  4  5  6 7 ∑ F (n; p) =| OR_{n} |
1 1  1
2 2 2  4
3 3 18 6  27
4 4 72 96 8 180
5 5 200 600 200 10  1015
6 6 450 2400 1800 360 12  5028
7 7 882 7350 9800 4410 588 14  23051

Table 3.4

n\k 1 2 3  4  5  6  7 ∑ F (n; k) =| OR_{n} |
1 1  1
2 1 3  4
3 1 7 19  27
4 1 13 49 117  180
5 1 21 101 281 611  1015
6 1 31 181 571 1381 2863  5028
7 1 43 295 1037 2759 6245 12671  23051

Table 3.5

4 Orientation-Preserving or Orientation-Reversing Partial One-to-one Transformations

The semigroups of orientation-preserving and orientation-preserving or reversing partial oneto-one transformations of X_{n} will be denoted by POPI_{n} and PORI_{n}, respectively.

Proposition 33. Let S = POPI_{n}. Then F (n; p, k) = \binom{n}{p}\binom{k−1}{p−1}p, for n ≥ k ≥ p > 0.

Proof. First observe that the p elements of Dom α can be chosen from X_{n} in \binom{n}{p} ways, and since k is the maximum element in Im α then the remaining p − 1 elements of Im α can be chosen from \{1, 2, …, k − 1\} in \binom{k−1}{p−1} ways. Finally, observe that if p > 0, then the p elements of Dom α can be tied to the p images in a one-to-one fashion (whilst preserving the orientation), in p ways. The result now follows.

The following corollaries can be deduced in exactly the same manner as their corresponding results in Section 2:

Corollary 34. Let S = POPI_{n}. Then

F (n; p) = \{ \begin{matrix}\binom{n}{p}^{2}p, & n ≥ p > 1; \\ n^{2}, & p = 1. \end{matrix}

Corollary 35. Let S = POPI_{n}. Then F (n; k) = n\binom{n+k−2}{k−1}, for n ≥ k ≥ 1. Corollary 36. Let S = POPI_{n}. Then F (n; k_{n}) = n\binom{2n−2}{n−1}, for n ≥ 1. Corollary 37. [2, Corollary 2.8] For any natural number n we have

| POPI_{n} |= 1 + \frac{n}{2}\binom{2n}{n}.

Proposition 38. Let S = PORI_{n}. Then

F (n; p, k) = \{ \begin{matrix}2\binom{n}{p}\binom{k−1}{p−1}p, & n ≥ k ≥ p > 2; \\ n^{2}, & k = 2; \\ 2(k − 1)\binom{n}{2}, & p = 2; \\ n, & k = 1 or p = 1. \end{matrix}

Proof. The proof is similar to that of Proposition 33. Corollary 39. Let S = PORI_{n}. Then

F (n; p) = \{ \begin{matrix}2\binom{n}{p}^{2}p, & n ≥ p > 2; \\ 2\binom{n}{2}^{2}, & p = 2; \\ n^{2}, & p = 1. \end{matrix}

Corollary 40. Let S = PORI_{n}. Then

F (n; k) = 2n\binom{n + k − 2}{n − 1} − n − n(n − 1)(k − 1), for n ≥ k > 0.

Corollary 41. Let S = PORI_{n}. Then

F (n; k_{n}) = 2n\binom{2n − 2}{n − 1} − n − n(n − 1)^{2}, for n ≥ 1.

Corollary 42. [3, Proposition 5.2] For any natural number n we have

| PORI_{n} |= 1 + n\binom{2n}{n} − n^{2}(n^{2} − 2n + 3)/2.

Remark 43. The triangular arrays of numbers F_{P OP I}(n; p), F_{P OP I}(n; k), F_{P ORI}(n; p) and F_{P ORI}(n; k) are as at the time of submitting this paper not in Sloane [18]. However, note that F_{P ORI}(n; p_{2}) is [18, \underline{A163102}].

n\p 0 1 2  3  4 5 6 ∑ F (n; p) =| POPI_{n} |
0 1  1
1 1 1  2
2 1 4 2  7
3 1 9 18 3  31
4 1 16 72 48 4  141
5 1 25 200 300 100 5  631
6 1 36 450 1200 900 180 6  2773

Table 4.1

n\k 0 1 2 3 4 5  6 ∑ F (n; k) =| POPI_{n} |
0 1  1
1 1 1  2
2 1 2 4  7
3 1 3 9 18  31
4 1 4 16 40 80  141
5 1 5 25 75 175 350  631
6 1 6 36 126 336 756 1512  2773

Table 4.2

n\p 0 1 2 3 4 5 6 ∑ F (n; p) =| PORI_{n} |
0 1  1
1 1 1  2
2 1 4 2  7
3 1 9 18 6  34
4 1 16 72 96 8 193
5 1 25 200 600 200 10  1036
6 1 36 450 2400 1800 360 12  5059

Table 4.3

n\k 0 1 2 3 4 5 6 ∑ F (n; k) =| PORI_{n} |
0 1  1
1 1 1  2
2 1 2 4  7
3 1 3 9 21  34
4 1 4 16 52 120  193
5 1 5 25 105 285 615  1036
6 1 6 36 166 576 1386 2868  5059

Table 4.4

5 Acknowledgements

I would like to thank the anonymous referee whose corrections helped remove many errors and suggestions that greatly improve the clarity of some statements in the paper.

References

[1] P. M. Catarino and P. M. Higgins, The monoid of orientation-preserving mappings on a chain, Semigroup Forum 58 (1999), 190–206.

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

[3] V. H. Fernandes, G. M. S. Gomes, and M. M. Jesus, Presentations for some monoids of injective partial transformations on a finite chain, Southeast Asian Bull. Math. 28 (2004), 903–918.

[4] V. H. Fernandes, G. M. S. Gomes, and M. M. Jesus, Congruences on monoids of transformations preserving the orientation of a finite chain, J. Algebra 321 (2009), 743–757.

[5] 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, submitted.

[6] O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups: An Introduction, Springer, 2009.

[7] P. M. Higgins, Techniques of Semigroup Theory, Oxford University Press, 1992.

[8] P. M. Higgins, Combinatorial results for semigroups of order-preserving mappings, Math. Proc. Camb. Phil. Soc., 113 (1993), 281–296.

[9] J. M. Howie, Combinatorial and probabilistic results in transformation semigroups, in Masami Ito and H. Jürgensen, eds., Words, Languages and Combinatorics, World Sci. Publ., 1994, pp. 200–206.

[10] J. M. Howie, Fundamentals of Semigroup Theory, Clarendon Press, 1995.

[11] A. Laradji and A. Umar, On certain finite semigroups of order-decreasing transformations I, Semigroup Forum, 69 (2004), 184–200.

[12] A. Laradji and A. Umar, Combinatorial results for semigroups of order-preserving partial transformations, J. Algebra, 278 (2004), 342–359.

[13] A. Laradji and A. Umar, Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq., 7 (2004), Article 04.3.8.

[14] A. Laradji and A. Umar, Combinatorial results for semigroups of order-preserving full transformations, Semigroup Forum, 72 (2006), 51–62.

[15] A. Laradji and A. Umar, Some combinatorial properties of the symmetric monoid, Int. Journal of Alg. and Computations, (to appear).

[16] D. B. McAlister, Semigroups generated by a group and an idempotent, Comm. Algebra, 26 (1998), 515–547.

[17] J. Riordan, Combinatorial Identities, John Wiley and Sons, 1968.

[18] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

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

[20] A. Umar, Some combinatorial problems in the theory of partial transformation semigroups, submitted.

2010 Mathematics Subject Classification: Primary 20M18; Secondary 20M20, 05A10, 05A15. Keywords: full transformation, partial transformation, partial one-to-one transformation, orientation-preserving transformation, orientation-reversing transformation, breadth, height, right waist, left waist, cyclic sequence, anti-cyclic sequence.

(Concerned with sequences \underline{A000225}, \underline{A000290}, \underline{0002061}, \underline{066524}, and \underline{A163102}.)

Received September 19 2010; revised version received July 9 2011. Published in Journal of Integer Sequences, September 5 2011.

Return to Journal of Integer Sequences home page.