Some combinatorial problems in the theory of symmetric inverse semigroups
Let Xn={1,2,⋯,n} and let α:Domα⊆Xn→Imα⊆Xn be a (partial) transformation on Xn. On a partial one-one mapping of Xn the following parameters are defined: the height of α is h(α)=|Imα|, the right [left] waist of α is w+(α)=max(Imα)[w−(α)=min(Imα)], and fix of α is denoted by f(α), and defined by f(α)...
Gespeichert in:
| Veröffentlicht in: | Algebra and Discrete Mathematics |
|---|---|
| Datum: | 2010 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2010
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/154602 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Some combinatorial problems in the theory of symmetric inverse semigroups / A. Umar // Algebra and Discrete Mathematics. — 2010. — Vol. 9, № 2. — С. 113–124. — Бібліогр.: 32 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-154602 |
|---|---|
| record_format |
dspace |
| spelling |
Umar, A. 2019-06-15T16:43:30Z 2019-06-15T16:43:30Z 2010 Some combinatorial problems in the theory of symmetric inverse semigroups / A. Umar // Algebra and Discrete Mathematics. — 2010. — Vol. 9, № 2. — С. 113–124. — Бібліогр.: 32 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:20M18, 20M20, 05A10, 05A15 https://nasplib.isofts.kiev.ua/handle/123456789/154602 Let Xn={1,2,⋯,n} and let α:Domα⊆Xn→Imα⊆Xn be a (partial) transformation on Xn. On a partial one-one mapping of Xn the following parameters are defined: the height of α is h(α)=|Imα|, the right [left] waist of α is w+(α)=max(Imα)[w−(α)=min(Imα)], and fix of α is denoted by f(α), and defined by f(α)=|{x∈Xn:xα=x}|. The cardinalities of some equivalences defined by equalities of these parameters on In, the semigroup of partial one-one mappings of Xn, and some of its notable subsemigroups that have been computed are gathered together and the open problems highlighted. The ideas for this work were formed during a one month stay at Wilfrid LaurierUniversity in the Summer of 2007.2This paper is based on the talk I gave at the 22nd BCC Conference, University ofSt Andrews, July 2009. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Some combinatorial problems in the theory of symmetric inverse semigroups Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Some combinatorial problems in the theory of symmetric inverse semigroups |
| spellingShingle |
Some combinatorial problems in the theory of symmetric inverse semigroups Umar, A. |
| title_short |
Some combinatorial problems in the theory of symmetric inverse semigroups |
| title_full |
Some combinatorial problems in the theory of symmetric inverse semigroups |
| title_fullStr |
Some combinatorial problems in the theory of symmetric inverse semigroups |
| title_full_unstemmed |
Some combinatorial problems in the theory of symmetric inverse semigroups |
| title_sort |
some combinatorial problems in the theory of symmetric inverse semigroups |
| author |
Umar, A. |
| author_facet |
Umar, A. |
| publishDate |
2010 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
Let Xn={1,2,⋯,n} and let α:Domα⊆Xn→Imα⊆Xn be a (partial) transformation on Xn. On a partial one-one mapping of Xn the following parameters are defined: the height of α is h(α)=|Imα|, the right [left] waist of α is w+(α)=max(Imα)[w−(α)=min(Imα)], and fix of α is denoted by f(α), and defined by f(α)=|{x∈Xn:xα=x}|. The cardinalities of some equivalences defined by equalities of these parameters on In, the semigroup of partial one-one mappings of Xn, and some of its notable subsemigroups that have been computed are gathered together and the open problems highlighted.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/154602 |
| citation_txt |
Some combinatorial problems in the theory of symmetric inverse semigroups / A. Umar // Algebra and Discrete Mathematics. — 2010. — Vol. 9, № 2. — С. 113–124. — Бібліогр.: 32 назв. — англ. |
| work_keys_str_mv |
AT umara somecombinatorialproblemsinthetheoryofsymmetricinversesemigroups |
| first_indexed |
2025-11-25T01:53:17Z |
| last_indexed |
2025-11-25T01:53:17Z |
| _version_ |
1850501224574484480 |
| fulltext |
A
D
M
D
R
A
F
T
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 9 (2010). Number 2. pp. 113 – 124
c© Journal “Algebra and Discrete Mathematics”
Some combinatorial problems in the theory
of symmetric inverse semigroups
A. Umar
Communicated by Mazorchuk V.
Abstract. Let Xn = {1, 2, · · · , n} and let α : Domα ⊆
Xn → Imα ⊆ Xn be a (partial) transformation on Xn. On a partial
one-one mapping of Xn the following parameters are defined: the
height of α is h(α) = | Imα|, the right [left] waist of α is w+(α) =
max(Imα)[w−(α) = min(Imα)], and fix of α is denoted by f(α),
and defined by f(α) = |{x ∈ Xn : xα = x}|. The cardinalities
of some equivalences defined by equalities of these parameters on
In, the semigroup of partial one-one mappings of Xn, and some of
its notable subsemigroups that have been computed are gathered
together and the open problems highlighted.1 2
1. Introduction and preliminaries
Let Xn = {1, 2, · · · , n}. Then a (partial) transformation α : Domα ⊆
Xn → Imα ⊆ Xn is said to be full or total if Domα = Xn; otherwise it is
called strictly partial. Then the height of α is | Imα|, the right [left] waist
of α is w+(α) = max(Imα)[w−(α) = min(Imα)], and fix of α is denoted
by f(α), and defined by
f(α) = |F (α)| = |{x ∈ Xn : xα = x}|.
1The ideas for this work were formed during a one month stay at Wilfrid Laurier
University in the Summer of 2007.
2This paper is based on the talk I gave at the 22nd BCC Conference, University of
St Andrews, July 2009.
2000 Mathematics Subject Classification: 20M18, 20M20, 05A10, 05A15.
Key words and phrases: partial one-one transformation, height, right (left)
waist and fix of a transformation. Idempotents and nilpotents.
A
D
M
D
R
A
F
T
114 Some combinatorial problems
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 also well-known that a partial transformation ǫ is idempotent (ǫ2 = ǫ)
if and only if Im ǫ = F (ǫ), and a partial transformation α is nilpotent if
αk = ∅ (the empty or zero map) for some positive integer k. It is worth
noting that to define the left (right) waist of a transformation the base
set Xn must be totally ordered. The main object of study in this paper is
In, the semigroup of partial one-one mappings of Xn (more commonly
known as the symmetric inverse semigroup) and some of its notable
subsemigroups. Enumerative problems of an essentially combinatorial
nature arise naturally in the study of semigroups of transformations. Many
numbers and triangle of numbers regarded as combinatorial gems like the
Stirling numbers [15, pp. 42 & 96], the factorial [26, 31], the Fibonacci
number [13], binomial numbers [14, 10], Catalan numbers [7], Eulerian
numbers [18], Schröder numbers [20], Narayana numbers [18], Lah numbers
[16, 17], etc., have all featured in these enumeration problems. These
enumeration problems lead to many numbers in Sloane’s encyclopaedia of
integer sequences [28] but there are also others that are not yet or have
just been recorded in [28]. This paper has two main objectives: first, to
gather together the various scattered enumeration results; and second, to
highlight open problems. Let S be a set of partial one-one transformations
on Xn. Next, let
F (n; p,m, k) = |{α ∈ S : h(α) = p ∧ f(α) = m ∧ w+(α) = k}|
and, let
F (n; p,m) = |{α ∈ S : h(α) = p ∧ f(α) = m}|,
F (n; p, k) = |{α ∈ S : h(α) = p ∧ w+(α) = k}|,
F (n;m, k) = |{α ∈ S : f(α) = m ∧ w+(α) = k}|.
Further, let
F (n; k) = |{α ∈ S : w+(α) = k}|,
F (n;m) = |{α ∈ S : f(α) = m}|,
F (n; p) = |{α ∈ S : h(α) = p}|.
It is not difficult to see that
|S| =
∑
k
F (n; k) =
∑
m
F (n;m) =
∑
p
F (n; p),
and any two-variable function can be expressed as a sum of appropriate
three-variable functions and so on. Ideally, we would like to compute
A
D
M
D
R
A
F
T
A. Umar 115
F (n; p,m, k) for any finite semigroup of partial one-one transformations
but at the moment this seems to be a difficult proposition and so we have
to start from the smaller-variable functions to higher-variable functions.
It appears that many important integer sequences can be realized as se-
quences counting these functions in various partial one-one transformation
semigroups - akin to Cameron’s remark about oligomorphic permutation
groups [2]. In In and its subsemigroups of order-preserving/order-reversing,
order-decreasing and orientation-preserving/orientation-reversing transfor-
mations we have expressions for |S| and most of the two-variable functions
and only a few three-variable functions.
Types of bijective transformations Semigroup
Permutations Sn
Partial one-one transformations In
Order-preserving IOn
Order-preserving or order-reversing PODIn
Order-decreasing IDn
Order-preserving or order-decreasing ICn
Orientation-preserving POPIn
Orientation-preserving or orientation-reversing PORIn
Table 1
We shall present the known results by means of tables and exhibit/
explain some of the techniques that have been used to obtain these results,
as well as explore some of the open problems. In the next section, (Section
2) we consider the symmetric group Sn, and the symmetric inverse semi-
group, In. In Section 3 we consider the order-preserving/order-reversing
subsemigroups of In and in Section 4, we consider its order-decreasing
version, while in Section 5 we consider its order-preserving and order-
decreasing version. In Section 6 we consider the orientation-preserving/
orientation-reversing subsemigroups of In. Concluding remarks form the
contents of Section 7.
2. The symmetric inverse semigroup
For more detailed studies of the symmetric inverse semigroup, In we refer
the reader to the books [24, 15, 9] and the papers [12, 16]. First, note that
k = w+(α) is undefined when p = 0. Due to the presence of the empty map,
it seems reasonable to define k = 0 if p = 0; and F (n; k) = F (n; p, k) = 1
if k = p = 0. This, and other observations we record in the following
lemma, which will be used implicitly whenever needed.
A
D
M
D
R
A
F
T
116 Some combinatorial problems
Lemma 2.1. Let Xn = {1, 2, · · · , n} and P = {p,m, k}, where for a
given α ∈ In, we set p = h(α),m = f(α) and k = w+(α). We also define
F (n; k) = F (n; p, k) = 1 if k = p = 0. Then we have the following:
1. n ≥ k ≥ p ≥ m ≥ 0;
2. k = 1 =⇒ p = 1;
3. p = 0 ⇔ k = 0
The following proposition is easy to prove, nevertheless, we include its
proof to demonstrate the technique rather than because it is new.
Proposition 2.2. Let S = In. Then
F (n; p, k) =
(
n
p
)(
k − 1
p− 1
)
p!, (n ≥ k ≥ p ≥ 0).
Proof. First observe that the p elements of Domα can be chosen from
Xn in
(
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
(
k−1
p−1
)
ways. Finally, observe that the p elements of Domα can be tied to
the p images in a one-one fashion, in p! ways. The result now follows.
The following corollaries can easily be deduced:
Corollary 2.3. Let S = In. Then
F (n; p) =
(
n
p
)2
p!, (n ≥ p ≥ 0).
Corollary 2.4. Let S = In. Then
F (n; k) =
k
∑
p=0
(
n
p
)(
k − 1
p− 1
)
p!, (n ≥ k ≥ 0).
Now let i = ai = a, for all a ∈ {p,m, k}, and 0 ≤ i ≤ n.
Corollary 2.5. Let S = In. Then F (n; kn) = n|In−1|, (n ≥ 2).
Corollary 2.6. Let S = In. Then F (n; kn−1) = n|N(In−1)|, where N(T )
is the set of nilpotents in T .
S |S| |E(S)| |N(S)|
Sn n! 1 0
In
∑n
p=0
(
n
p
)2
p! = an 2n
∑n
p=0
(
n
p
)(
n−1
p
)
p!
=
∑n−1
p=0 |Ln,n−p| = un
[26] [17], [8]
or [9, Theorem 2.5.1, p.22] or [9, Theorem 2.8.5, p.30]
In \ Sn an − n! 2n − 1 same as in above cell
Table 2
A
D
M
D
R
A
F
T
A. Umar 117
an = 2nan−1 − (n− 1)2an−2, a0 = 1, a1 = 2 [1] :
1, 2, 7, 34, 209, 1546, 13327, 130922, · · · , (A002720);
un = (2n− 1)un−1 − (n− 1)(n− 2)un−2, u0 = 1 = u1 :
1, 1, 3, 13, 73, 501, 4051, 37633, · · · , (A000262);
|Ln,n−p| is the triangle of signless transpose Lah numbers (A089231).
The main statement proved above is by direct combinatorial arguments;
however, this approach does not always work. Finding recurrences and
guessing a closed formula which can then be proved by induction is
another approach effectively used in [18, 19, 20, 21, 22]. The success of
this approach depends heavily on enumerating methods and techniques
that can be found in [3, 25, 29] and identities that can be found in [27].
We (in [23]) are currently using generating functions to investigate some
of the unknown cases and it looks very promising.
Sn In
F (n; p) n! (if p = n) and
(
n
p
)2
p!
0 (if p 6= n)
F (n;m)
(
n
m
)
dn−m
n!
m!
∑n−m
i=0
(−1)i
i!
∑n−i
j=0
(
n−i
j
)
1
j!
=
(
n
m
)
f(n−m; 0) [22]
F (n; k) n! (if k = n) and
∑k
p=0
(
n
p
)(
k−1
p−1
)
p!
0 (if k 6= n) (Corollary 2.4)
F (n; p,m) F (n;m) (if p = n) and n!
m!(n−p)!
∑p−m
j=0
(
n−m−j
p−m−j
) (−1)j
j!
0 (if p 6= n) [22]
F (n; p, k) F (n; p) (if k = n) and
(
n
p
)(
k−1
p−1
)
p!
0 (if k 6= n) (Proposition 2.2)
F (n;m, k) F (n;m) (if k = n) and ?
0 (if k 6= n)
F (n; p,m, k) F (n;m) (if k = p = n) and ?
0 (otherwise)
Table 3
dn = 1, 0, 1, 2, 9, 44, 265, 1854, 14833, · · · , derangements (A000166)
(n−m)F (n;m) = n(2n− 2m− 1)F (n− 1;m)−
n(n− 1)(n−m− 3)F (n− 2;m)− n(n− 1)(n− 2)F (n− 3;m) (A144088)
f(n; 0) : 1, 1, 4, 18, 108, 780, 6600, · · · , partial derangements (A144085).
3. Order-preserving or order-reversing
partial one-one transformations
A transformation α ∈ In is said to be order-preserving (order-reversing)
if (∀x, y ∈ Domα) x ≤ y =⇒ xα ≤ yα (xα ≥ yα). The semigroups of
order-preserving and order-preserving or order-reversing partial one-one
transformations of Xn will be denoted by IOn and PODIn, respectively.
A
D
M
D
R
A
F
T
118 Some combinatorial problems
The general study of IOn was initiated in [11] while PODIn first appeared
in [5].
Remark 3.1. For p = 0, 1 the concepts of order-preserving and order-
reversing coincide but distinct otherwise. However, there is a bijection
between the two sets for p ≥ 2.
Now we announce some new results of the author (and his coauthor),
whose detail proofs are going to appear in [23].
Proposition 3.2. Let S = PODIn. Then F (n; p, k) = 2
(
n
p
)(
k−1
p−1
)
, (if
n ≥ k ≥ p ≥ 2) and equals n (if k = 1 or p = 1).
Corollary 3.3. Let S = PODIn. Then F (n; p) = 2
(
n
p
)2
, (n ≥ p > 1)
and equals n2 (if p = 1).
Corollary 3.4. Let S = PODIn. Then F (n; k) = 2
(
n+k−1
k
)
− n, (n ≥
k ≥ 1).
S |S| |E(S)| |N(S)|
IOn
(
2n
n
)
[11] 2n bn[23]
PODIn 2
(
2n
n
)
− n2 − 1 [5] 2n ?
Table 4
(n+ 1)bn+1 = 2(4n+ 1)bn − 3(5n− 3)bn−1 − 2(2n− 1)bn−2, b0 = 1 = b1 :
1, 1, 3, 9, 29, 97, 333, 1165, 4135, · · · (A081696).
IOn PODIn
F (n; p)
(
n
p
)2
[11] 2
(
n
p
)2
(if p > 1) and
n2 (if p = 1)
(Corollary 3.3)
F (n;m)
∑n
j=m F (j − 1;m− 1)bn−j ?
[23]
F (n; k)
(
n+k−1
k
)
[23] 2
(
n+k−1
k
)
− n (Corollary 3.4)
F (n; p,m) ? ?
F (n; p, k)
(
n
p
)(
k−1
p−1
)
[23] 2
(
n
p
)(
k−1
p−1
)
(if p > 1) and
n (if k = 1 or p = 1)
(Proposition 3.2)
F (n;m, k) ? ?
F (n; p,m, k) ? ?
Table 5
A
D
M
D
R
A
F
T
A. Umar 119
4. Order-decreasing partial one-one transformations
A transformation α in In is said to be order-decreasing (increasing) if
(∀x ∈ Domα)xα ≤ x (xα ≥ x). The two semigroups of order-decreasing
and order-increasing partial one-one transformations of Xn are isomorphic
[31]. The semigroup of order-decreasing partial one-one transformations of
Xn will be denoted by IDn. The general study of this class of semigroups
was initiated in [30].
The following result easily follows from [31, Theorem 4.2].
Proposition 4.1. Let S = IDn. Then F (n;m) =
(
n
m
)
Bn−m, where Bn
is the n-th Bell’s number.
Proof. Let α ∈ IDn and let x1, x2, · · · , xm be the fixed points of α.
Since α is one-one and order-decreasing, it follows that for x ∈ (Xn \
{x1, · · · , xm}) ∩ Domα we have xα ∈ Xn \ {x1, · · · , xm} and xα < x.
Therefore the restriction of α to Xn \ {x1, · · · , xm} is well defined and
is a nilpotent element of I(Xn \ {x1, · · · , xm}. The number of nilpotents
that can be formed by these n−m elements (after relabelling) is Bn−m
(by [31, Theorem 4.2]), and the result now follows.
Conjecture 4.2. Let S = IDn. Then F (n; k) =
(
n
k
)
Bk.
S |S| |E(S)| |N(S)|
IDn Bn+1 [1] 2n Bn [31]
Table 6
IDn
F (n; p) S(n, n− p) [1]
F (n;m)
(
n
m
)
Bn−m (Proposition 4.1)
F (n; k)
(
n
k
)
Bk (Conjecture 4.2)
F (n; p,m) ?
F (n; p, k) ?
F (n;m, k) ?
F (n; p,m, k) ?
Table 7
S(n, r) is the Stirling number of the second kind:
S(n, r) = S(n− 1, r − 1) + rS(n− 1, r), S(n, 1) = 1 = S(n, n) (A008277).
Bn+1 =
∑n
k=0
(
n
k
)
Bk : 1, 2, 5, 15, 52, 203, 877, 4140, · · · (A000110).
A
D
M
D
R
A
F
T
120 Some combinatorial problems
5. Order-preserving and order-decreasing partial one-one
transformations
We define ICn = IOn ∩ IDn as the semigroup of order-preserving and order-
decreasing partial one-one transformations of Xn. Surprisingly, the semigroup
ICn first appeared in [9] and not much is known about it.
Proposition 5.1. Let S = ICn. Then |N(ICn)| =
1
n
(
2n
n−1
)
= Cn, where Cn is
the n-th Catalan number.
Proof. It is similar to the proof of [21, Proposition 2.3].
Conjecture 5.2. Let S = ICn. Then F (n; p) = 1
n−p+1
(
n
p
)(
n+1
p+1
)
. (This is known
as the Narayana triangle – A001263.)
Conjecture 5.3. Let S = ICn. Then F (n;m) = m+1
2n−m+1
(
2n−m+1
n+1
)
. (This is
triangle – A033184.)
Conjecture 5.4. Let S = ICn. Then F (n; k) = n−k+1
n
(
n+k−1
n−1
)
. (This is known
as the Catalan triangle – A009766.)
S |S| |E(S)| |N(S)|
ICn Cn+1 2n Cn
[9, Theorem2.4.8(ii)] (Proposition 5.1)
Table 8
ICn
F (n; p) 1
n−p+1
(
n
p
)(
n+1
p+1
)
(Conjecture 5.2)
F (n;m) m+1
2n−m+1
(
2n−m+1
n+1
)
(Conjecture 5.3)
F (n; k) n−k+1
n
(
n+k−1
n−1
)
(Conjecture 5.4)
F (n; p,m) ?
F (n; p, k) ?
F (n;m, k) ?
F (n; p,m, k) ?
Table 9
6. Orientation-preserving or orientation-
reversing partial one-one transformations
Let a = (a1, a2, · · · , at) be a sequence of t (t > 0) distinct elements from the chain
Xn. We say that a is cyclic (anti-cyclic) if there exists no more than one index i ∈
{1, 2, · · · , t} such that ai > ai+1(ai < ai+1), where at+1 denotes a1. For α ∈ In,
suppose that Dom α = {a1, a2, · · · , at}, with t ≥ 0 and a1 < a2 < · · · < at. We
say that α is orientation-preserving (orientation-reversing) if (a1α, a2α, · · · , atα)
is cyclic (anti-cyclic). The semigroups of orientation-preserving and orientation-
preserving/ orientation-reversing partial one-one transformations of Xn will be
denoted by POPIn and PORIn, respectively.
A
D
M
D
R
A
F
T
A. Umar 121
Remark 6.1. For p = 0, 1, 2 the concepts of orientation-preserving and orientation-
reversing coincide but distinct otherwise. However, there is a bijection between
the two sets for p > 2.
Now we announce new results by the author, whose proofs are given in the
preprint [32].
Proposition 6.2. Let S = POPIn. Then
F (n; p, k) =
(
n
p
)(
k − 1
p− 1
)
p (n ≥ k ≥ p > 0).
Corollary 6.3. Let S = POPIn. Then
F (n; p) =
{
(
n
p
)2
p (n ≥ p > 1),
n2 (p = 1).
Corollary 6.4. Let S = POPIn. Then F (n; k) = n
(
n+k−2
k−1
)
, (n ≥ k ≥ 1).
Corollary 6.5. Let S = POPIn. Then F (n; kn) = n
(
2n−2
n−1
)
, (n ≥ 1).
Proposition 6.6. Let S = PORIn. Then
F (n; p, k) =
2
(
n
p
)(
k−1
p−1
)
p (n ≥ k ≥ p > 2),
n2 (k = 2),
2(k − 1)
(
n
2
)
(p = 2),
n ((k = 1) ∨ (p = 1)).
Corollary 6.7. Let S = PORIn. Then
F (n; p) =
{
2
(
n
p
)2
p (n ≥ p > 2),
(
n
p
)2
p (p = 1, 2).
Corollary 6.8. Let S = PORIn. Then
F (n; k) = 2n
(
n+ k − 2
n− 1
)
− n− n(n− 1)(k − 1), (n ≥ k > 0).
S |S| |E(S)| |N(S)|
POPIn 1 + n
2
(
2n
n
)
[4] 2n ?
PORIn 1 + n
(
2n
n
)
− n2(n2 − 2n+ 3)/2 2n ?
[5]
Table 10
A
D
M
D
R
A
F
T
122 Some combinatorial problems
POPIn PORIn
F (n; p)
(
n
p
)2
p (if p > 1) 2
(
n
p
)2
p (if p > 2) and
n2 (if p = 1)
(
n
p
)2
p (if p = 1, 2)
(Corollary 6.3) (Corollary 6.7)
F (n;m) ? ?
F (n; k) n
(
n+k−2
k−1
)
(if k > 0) 2n
(
n+k−2
k−1
)
− n− n(n− 1)(k − 1)
(if k > 0)
(Corollary 6.4) (Corollary 6.8)
F (n; p,m) ? ?
F (n; p, k)
(
n
p
)(
k−1
p−1
)
p (if k ≥ p > 0) 2
(
n
p
)(
k−1
p−1
)
p (if k ≥ p > 2)
n2 (if k = 2)
(Proposition 6.2) 2(k − 1)
(
n
2
)
(if p = 2)
n (if k = 1 or p = 1)
(Proposition 6.6)
F (n;m, k) ? ?
F (n; p,m, k) ? ?
Table 11
7. Concluding remarks
Remark 7.1 All these combinatorial functions can be computed when restricted
to special subsets within a particular semigroup, for example, the set of nilpotents,
N(S) [17].
Remark 7.2 We have only considered 7 classes of transformation semigroups:
In, IOn, PODIn, IDn, ICn, POPIn and PORIn, however, there are many
other classes of transformation semigroups that can be studied from this point
of view.
Remark 7.3 When the totally ordered set Xn is replaced by a partially ordered
set (poset), for each n > 1 there are ’several’ non-isomorphic posets, each of
which gives rise to potentially different combinatorial results.
Acknowledgements. I would like to thank Professor A. Laradji for his useful
suggestions and encouragement. My sincere thanks also to Professor S. Bulman-
Fleming and the Department of Mathematics and Statistics, Wilfrid Laurier
University. Finally, I thank the anonymous referee whose corrections helped
remove many errors and suggestions that greatly improve the clarity of some of
the proofs and statements.
References
[1] Borwein, D., Rankin, S. and Renner, L. Enumeration of injective
partial transformations. Discrete Math. 73 (1989), 291–296.
[2] Cameron, P. J. Sequences realized by oligomorphic permutation groups. J.
Integer Seq. 3 (2000), 00.1.5, HTML document (electronic).
[3] Comtet, L. Advanced Combinatorics: the art of finite and infinite expansions,
D. Reidel Publishing Company, Dordrecht, Holland, 1974.
A
D
M
D
R
A
F
T
A. Umar 123
[4] Fernandes, V. H. The monoid of all injective orientation-preserving partial
transformations on a finite chain. Comm. Algebra 32 (2000), 3401–3426.
[5] Fernandes, V. H., Gomes, G. M. S. and Jesus, M. M. Presen-
tations for some monoids of injective partial transformations on a finite chain.
Southeast Asian Bull. Math. 28 (2004), 903–918.
[6] Fernandes, V. H., Gomes, G. M. S. and Jesus, M. M. The
cardinal and idempotent number of various monoids of transformations on a finite
chain. (submitted).
[7] Ganyushkin, E. and Mazorchuk, V. On the structure of IOn. Semi-
group Forum 66 (2003), 455–483.
[8] Ganyushkin, O. and Mazorchuk, V. Combinatorics of nilpotents in
symmetric inverse semigroups. Ann. Comb. 8 (2) (2004), 161–175.
[9] Ganyushkin, O. and Mazorchuk, V. Classical Finite Transformation
Semigroups: An Introduction, Springer, London, 2009.
[10] Garba, G. U. On the nilpotent ranks of certain semigroups of transformations.
Glasgow Math. J. 36 (1994), 1–9.
[11] Garba, G. U. Nilpotents in semigroups of partial one-to-one order-preserving
mappings. Semigroup Forum, 48 (1994), 37–49.
[12] Gomes, G. M. S. and Howie, J. M. Nilpotents in finite symmetric
inverse semigroups. Proc. Edinburgh Math. Soc., 30 (1987), 383–395.
[13] Howie, J. M. Products of idempotents in certain semigroups of transformations.
Proc. Edinburgh Math. Soc. 17 (1971), 223–236.
[14] Howie, J. M., Lusk, E. L. and McFadden, R. B. Combinatorial
results relating to product of idempotents in finite full transformation semigroups.
Proc. Roy. Soc. Edinburgh Sect. A 115 (1990), 289–299.
[15] Howie, J. M. Fundamentals of semigroup theory. Oxford: Clarendon Press,
1995.
[16] Janson, S. and Mazorchuk, V. Some remarks on the combinatorics of
ISn. Semigroup Forum, 109 (2005), 391–405.
[17] Laradji , A. and Umar, A. On the number of nilpotents in the partial
symmetric semigroup. Comm. Algebra, 32 (2004), 3017–3023.
[18] Laradji , A. and Umar, A. On certain finite semigroups of order-decreasing
transformations I. Semigroup Forum, 69 (2004), 184–200.
[19] Laradji , A. and Umar, A. Combinatorial results for semigroups of order-
preserving partial transformations. Journal of Algebra, 278 (2004), 342–359.
[20] Laradji , A. and Umar, A. Combinatorial results for semigroups of order-
decreasing partial transformations. J. Integer Seq., 7 (2004), 04.3.8.
[21] Laradji , A. and Umar, A. Combinatorial results for semigroups of order-
preserving full transformations. Semigroup Forum, 72 (2006), 51–62.
[22] Laradji , A. and Umar, A. Combinatorial results for the symmetric inverse
semigroup. Semigroup Forum, 75 (2007), 221–236.
[23] Laradji , A. and Umar, A. Combinatorial results for semigroups of order-
preserving or order-reversing subpermutations (in preparation).
[24] Limpscomb, S. Symmetric Inverse Semigroups, Mathematical Surveys of The
American mathematical Society, no. 46, Providence, R. I., 1996.
A
D
M
D
R
A
F
T
124 Some combinatorial problems
[25] Liu, C. L. Introduction to combinatorial mathematics, McGraw Hill Company,
New York, 1968.
[26] Munn, W. D. The characters of the symmetric inverse semigroup. Proc.
Cambridge Philos. Soc., 53 (1957), 13–18
[27] Riordan, J. Combinatorial Identities, John Wiley and Sons, New York, 1968.
[28] Sloane, N. J. A. The On-Line Encyclopedia of Integer Sequences,
@http://www.research.att.com/ ∼ njas/sequences/.
[29] Stanley, R. P. Enumerative Combinatorics Vol. I, Cambridge University
Press, 1997.
[30] Umar, A. Semigroups of order-decreasing transformations, Ph. D Thesis, Uni-
versity of St Andrews, 1992.
[31] Umar, A. On the semigroups of partial one-to-one order-decreasing finite
transformations, Proc. Roy. Soc. Edinburgh, 123A (1993), 355–363.
[32] Umar, A. Some combinatorial results for the semigroups of orientation-
preserving partial transformations (submitted).
Contact information
A. Umar Department of Mathematics and Statistics
Sultan Qaboos University
Al-Khod, PC 123 – OMAN
E-Mail: aumarh@squ.edu.om
Received by the editors: ????
and in final form ????.
A. Umar
|