ABSTRACT
Let X { n} n = 1,2,…, be a finite n -element set and let n n n S , A and D be the
Symmetric, Alternating and Dihedral groups of n X , respectively. In this thesis we
obtained and discussed formulae for the number of even and odd permutations (of an
n − element set) having exactly k fixed points in the alternating group and the
generating functions for the fixed points. Further, we give two different proofs of the
number of even and odd permutations (of an n − element set) having exactly k fixed
points in the dihedral group, one geometric and the other algebraic. In the algebraic
proof, we further obtain the formulae for determining the fixed points. We finally
proved the three families; F(2r,4r + 2), F(4r +3,8r + 8) and F(4r +5,8r +12) of the
Fibonacci groups F(m , n) to be infinite by defining Morphism between Dihedral
groups and the Fibonacci groups.
1
TABLE OF CONTENTS
TITLE PAGE i
DECLARATION ii
CERTIFICATION iii
ACKNOWLEDGEMENT iv
DEDICATION v
TABLE OF CONTENTS vi
LIST OF TABLES xv
NOTATIONS xvi
ABSTRACT xx
CHAPTER ONE
INTRODUCTION
1.1 FUNDAMENTAL CONCEPTS 1
1.2 BASIC SEMIGROUP THEORY 1
1.3 MONOGENIC (CYCLIC) SEMIGROUP 3
1.4 ORDERED SETS, SEMILATTICES AND LATTICES 4
1.5 GREEN’S EQUIVALENCE 4
1.6 BASIC GROUP THEORY 5
1.7 PERMUTATION GROUP 7
1.8 TRANSFORMATIONS 9
1.9 GROUP HOMOMORPHISM 9
1.9.1 First isomorphism theorem 10
vii
1.9.2 Second isomorphism theorem 10
1.9.3 Third isomorphism theorem 10
1.10 DIRECT PRODUCTS 10
1.11 COSETS 11
1.12 NORMAL SUBGROUP 12
1.13 p-GROUPS 14
1.13.1 First sylow theorem 14
1.13.2 Second sylow theorem 16
1.13.3 Third sylow theorem 16
1.14 GROUP ACTIONS ON GROUPS 16
1.15 BASIC COMBINATORICS 16
1.16 BINOMIAL THEOREM 16
1.17 PERMUTATIONS AND COMBINATIONS 16
1.18 RECURRENCE RELATIONS AND FUNCTION
GENERATING 17
1.18.1 Recurrence relation 17
1.18.2 Generating functions 17
1.19 SOME SPECIAL NUMBERS 18
1.19.1 Bell numbers 18
1.19.2 Fibonacci numbers 18
1.19.3 Catalan numbers 19
1.19.4 Starling numbers 20
1.20 DERANGEMENTS 20
viii
1.21 BACKGROUND OF THE STUDY 21
1.22 STATEMENT OF THE PROBLEM 23
1.23 JUSTIFICATION OF THE STUDY 24
1.24 OBJECTIVE OF THE STUDY 24
CHAPTER TWO
LITERATURE REVIEW
2.1 TRANSITIVE PERMUTATION GROUP 26
2.1.1 Orbits of α in G 26
2.1.2 Properties of orbits of α in G 27
2.1.3 Stabilizer of α in G 27
2.1.4 Properties of stabilizer of α in G 27
2.1.5 Transitive constituent 28
2.2 REGULAR AND SEMI-REGULAR GROUPS 28
2.3 THE SUBGROUPS (Δ) G and {Δ} G . 29
2.3.1 Properties of (Δ) G and {Δ} G 29
2.3.2 Burnside lemma 29
2.4 PRIMITIVE GROUPS 30
2.4.1 Properties of primitive groups 30
2.5 MULTIPLY TRANSITIVE GROUPS 31
2.6 CLASSIFICATION OF TRANSITIVE GROUPS 31
2.7 CLASSIFICATION OF PRIMITIVE GROUPS 32
2.8 CONSTRUCTING TRANSITIVE PERMUTATION
GROUPS 33
ix
2.9 TRANSITIVE p -GROUPS OF DEGREE pm 33
2.9.1 Lemma 33
2.9.2 Theorem 34
2.10 CLOCKWISE (ANTI-CLOCKWISE) ORIENTATION 34
2.10.1 Remark 34
2.11 ORIENTATION PRESERVING (REVERSING) MAPPINGS 35
2.11.1 Orientation preserving mappings 35
2.11.2 Lemma 36
2.11.3 Lemma 36
2.11.4 Lemma 36
2.11.5 Lemma 36
2.11.6 Remark 37
2.11.7 Orientation preserving mappings 37
2.11.8 Remark 37
2.11.9 Lemma 38
2.11.10 Theorem 38
2.12 COMBINATORIAL PROPERTIES OF TRANSFORMATION
SEMIGROUPS AND SYMMETRIC GROUPS 38
CHAPTER THREE
RESULTS
3.1 RESULT ONE: SOME COMBINATORIAL PROPERTIES OF
THE ALTERNATING GROUP 41
3.1.1 Result 41
3.1.2 Result 42
3.1.4 Result 42
x
3.2 EVEN AND ODD PERMUTATIONS 42
3.2.1 Theorem 43
3.2.2 Proposition 44
3.2.4 Proposition 47
3.2.5 Proposition 47
3.2.6 Remark 48
3.3 GENERATING FUNCTIONS 53
3.3.1 Proposition 53
3.3.2 Proposition 53
3.3.3 Proposition 54
3.4 NUMBER OF PERMUTATIONS WITH A GIVEN CYCLE
STRUCTURE 55
3.4.1 Lemma 55
3.4.2 Lemma 55
3.4.3 Theorem 55
3.4.5 Theorem 56
3.5 RESULT TWO: SOME COMBINATORIAL PROPERTIES
OF THE DIHEDRAL GROUP 57
3.5.1 Result 58
3.5.2 Result 58
3.5.3 Result 58
3.5.4 Result 58
3.5.5 Result 59
3.5.6 Result 59
3.5.7 Result 59
3.5.8 Result 60
3.5.9 Result 60
xi
3.5.10 Result 60
3.6 NUMBER OF FIXED POINTS 60
3.6.1 Proposition 61
3.7 EVEN AND ODD PERMUTATIONS 62
3.7.1 Proposition 62
3.7.2 Proposition 63
3.8 THE SUBGROUP OF ORIENTATION PRESERVING
(REVERSING) MAPPINGS 64
3.8.1 Result 65
3.8.2 Result 66
3.8.3 Result 66
3.8.10 Result 67
3.9 THE SUBGROUP OF ORIENTATION PRESERVING
MAPPINGS 67
3.9.1 Lemma 67
3.9.2 Lemma 67
3.9.3 Lemma 68
3.9.4 Theorem 68
3.10 THE SUBGROUP OFORIENTATION REVERSING
MAPPINGS 71
3.10.1 Lemma 72
3.10.2 Lemma 77
3.10.3 Lemma 82
3.10.4 Result 83
3.10.6 Result 84
xii
3.10.7 Result 84
3.10.8 Result 85
3.10.9 Remark 85
3.11 EVEN AND ODD PERMUTATIONS 85
3.11.1 Proposition 85
3.11.2 Proposition 86
3.12 DIHEDRAL GROUPS AS HOMOMORPHIC IMAGES 89
3.12.1 Lemma 89
3.12.2 Lemma 89
3.13 THE FIBONACCI GROUP F(2r, 4r + 2) 90
3.13.1 Lemma 90
3.13.2 Proposition 90
3.13.3 Lemma 91
3.13.4 Lemma 91
3.14 THE FIBONACCI GROUP F(4r + 3, 8r + 8) 92
3.14.1 Lemma 92
3.14.2 Proposition 93
3.14.3 Lemma 94
3.14.4 Lemma 94
3.14.5 Lemma. 95
3.14.6 Lemma 96
3.14.7 Lemma 97
3.15 THE FIBONACCI GROUP F(4r + 5, 8r +12) 98
xiii
3.15.1 Lemma 99
3.15.2 Proposition 99
3.15.3 Lemma 100
3.15.4 Lemma 101
3.15.5 Lemma 101
3.15.6 Lemma 102
3.15.7 Lemma 103
CHAPTER FOUR
SUMMARY OF RESULTS, CONTRIBUTIONS
AND AREAS FOR FURTHER RESEARCH
4.1 SUMMARY OF RESULTS 105
4.2 CONTRIBUTIONS TO KNOWLEDGE 106
4.2 AREAS FOR FURTHER RESEARCH 106
REFERENCES 108
CHAPTER ONE
INTRODUCTION
1.1 INTRODUCTION
The main aim of this chapter is to highlight a few concepts which are
fundamental for the understanding of semigroup, group and combinatorial
theoretical concepts. The results therein form the background of the study,
which spell out the statement of the problem, objective and justification of the
study.
Let n { n} X x , x , , x = 1 2 … be a finite set, a permutation on n X is a one-toone
mapping of n X onto itself. The set of all permutations on n elements is
denoted by n S called symmetric group of degree n,and of order n!. The group
n S consists of both even and odd permutations depending on the length the
permutation, even or odd. The set of all even permutations on n X forms a
group called the alternating group ( n A ). Another subgroup of n S comprising of
both even and odd permutations is called the Dihedral group such that for all
, ,n x y∈S , n 2 1, 1
n x y∈D iff x = y = xy = y− x .
The arrangement of elements of the Alternating or Dihedral groups
according to specified rule (the number of fixed points) is of particular interest.
First, how many of such arrangements are possible and what is their recurrence
and generating functions.
Another group which has similar structure to the dihedral group is the
Fibonacci 1 2 1 1 2 3 2 3 4 1 1 ( , ) : , , n n n n F r n aa a a aa a a a a a a a − − =< = = = > where r is the
2
number of relations and n is the number of generators, for what value of
r &n is the group finite or infinite.
1.2 BACKGROUND OF THE STUDY
Let X { n} n = 1, 2,…, be a finite n -element set and let , n P , n O , n n n S D and A
be the partial transformation semigroups, the submonoid of n T consisting of all
order preserving mappings of n X , the symmetric, dihedral and alternating
groups respectively. The combinatorial properties of n S have been studied
over long period and many interesting results have emerged. In particular, the
number of permutations of n X having exactly k fixed points and their
generating functions are known.
The Dihedral group n D , geometrically consists of all symmetries of a
regular n− gon (n ≥ 3), that is, n rotations through the angles
x
n
360 (x = 0,1,2,…,n −1) and n reflections through each of the n lines of
symmetry of the regular n -gon. Algebraically, each element of n D is either
cyclic (preserve orientation) or ant-cyclic (reverse orientation). Catarino and
Higgins (1999) introduced a new subsemigroup of n X containing n O which is
denoted by n OP and its elements are called orientation preserving mappings.
Also, they introduced a Semigroup n n n P = OP ∪OR where n OR denotes the
collection of all orientation reversing mappings. They showed that the
Dihedral Group is the maximal sub-Semigroup of . n n n P = OP ∪OR Fernandes
(2000) studied the monoid of orientation preserving partial transformations of
3
a finite chain, concentrating in particular on partial transformations which are
injective. However, the algebraic proof (along the lines of Catarino and
Higgins (1999)) and the geometric proof, for the number (and properties) of
even and odd permutations having exactly k fixed points in the Dihedral group
n D seem not to have been studied.
The Fibonacci group F(2, n) is the group defined by the Presentation
< = = = = > 1 2 1 2 3 2 3 4 −1 1 1 2 a a , , a : a a a ,a a a a a a ,a a a n n n n
The study of these groups began in earnest after a question of Conway (1965)
as to whether or not F(2, 5) is cyclic of order 11, and it was quickly determined
in (Conway, et al, 1965) that this was indeed the case, and also that F(2, 1)
and F(2, 2) are trivial, F(2, 3) is the quaternion group of order 8 , F(2, 4) is
cyclic of order 5 , and F(2, 6) is infinite.
In a survey article Thomas (1989) gave a list of those parameters r and
n for which the finiteness or infiniteness of the Fibonacci group F(r, n) was
still unknown. Since then, some of the unknown examples were proved infinite
by Prishchepov (1998) using geometric methods, and some isolated difficult
examples, such as F(4,7), were proved infinite and automatic by computer
programs written by Holt (1998), Christopher (1998), proved all of the
outstanding cases except for two families of examples which were proved to
be infinite by using geometric methods. The two families that remain unsettled
are F(7 + 5i,5) and F(8 + 5i,5) for integers i ≥ 0. The methods also apply to
those examples that had previously been handled by computers. All these
4
methods were not able to give a generalized result of testing the order of a
Fibonacci group.
1.3 STATEMENT OF THE PROBLEM
Let
( , ) { : ( ) } n e n k = α ∈ A f α = k
( , ) { : ( ) } n e′ n k = α ∈ A′ f α = k
( )
0 !
i
i
i
f x e x
≥ i
= Σ
be the number of even (odd) permutations in the alternating group and the
generating functions for the fixed points. How many even (odd) permutations
( e (n, k) or e′(n, k ) ) of an n − element set having exactly k fixed points are in
the alternating group and what is the generating functions for the fixed points.
Geometrically and Algebraically, How many even and odd permutations
(of an n − element set) having exactly k fixed points are in the dihedral group
and what are the fixed points.
To study Alternating and Dihedral groups, let α be a permutation of n X ,
and f (m , n) be the number of permutations of n X that can be expressed as a
product of ( 1, 1, 2, , 1) ir m− i + i = m− cycles. How many such permutations are
there in n X .
The Fibonacci groups F(m , n) defined as
( ) =< = = > + + − + F m n a a a a a a a i m n i i i m i m , , , , 1,2, , 1 2 … 1 1 …
for what value of m and n is the Fibonacci group infinite or finite.
5
1.4 JUSTIFICATION OF THE STUDY
Since the combinatorial properties of n n A and D have not been studied, it
is our desire to consider the number of even and odd permutations (of an
n − element set) having exactly k fixed points in the alternating & dihedral
groups, the generating functions for the fixed points in the alternating group
and the formulae for determining the fixed points in the dihedral group.
Considering the combinatorial properties of the Dihedral group, we create
morphism between the dihedral group and the Fibonacci group. The morphism
will give us a new method of determining the finiteness or infiniteness of
Fibonacci group.
It is our hope that the combinatorial properties of these groups will help
in studying the nature (structure) of other permutation groups, and it is our
hope that the new method of studying the finiteness or infiniteness of
Fibonacci group will help in the study of unsettled problems.
1.5 OBJECTIVE OF THE STUDY
The objective of this research is to
1. Obtain the number of even (odd) permutations having exactly k fixed
points in the alternating group, discuss the fixed points and the generating
functions for the fixed points.
2. Give two different proofs one geometric and the other algebraic (in line
with Catarino and Higgins 1999) of the number of even and odd permutations
(of an n − element set) having exactly k fixed points in the dihedral group. In
6
the algebraic proof, we further obtain the formulae for determining the fixed
points.
3. Prove the three families; F(2r,4r + 2), F(4r +3,8r + 8) and F(4r +5,8r +12)
of the Fibonacci groups F(m , n) to be infinite by defining Morphism between
Dihedral groups and the Fibonacci groups.
4. Obtain the number of permutations of n X that can be expressed as a
product of ( 1, 1, 2, , 1) ir m− i + i = m− cycles.
1.6 BASIC SEMIGROUP THEORY
Throughout unless otherwise explicitly indicated, the letter S denotes an
arbitrary semigroup.
We call an algebraic structure (S,) that satisfies the closure property a
groupoid, that is to say, if, ∀ x, y∈S, x y∈S . A semigroup S is a groupoid
with an associative binary operation, that is to say, if
∀ x, y, z ∈S, x (y z) = (x y) z.
If a semigroup S has the property that, for all x , y∈ S, xy = yx , we say
that S is a commutative semigroup. If a semigroup S contains an element 1
with the property that ∀ x∈S, 1 x = x = x 1. We say that 1 is an identity
element of S, and that S is a semigroup with identity or a monoid. A
semigroup S has at most one identity element. If S has no identity element,
then an extra element 1 can be adjoined to S to form a monoid. We define
S 1 = S =1 S and 11 = 1 ∀ s∈S , thus S ∪{1} is now a monoid. We refer to
7
S1 =S ∪{1} as a monoid obtained from S by adjoining an identity element if
necessary.
If a semigroup S with at least two elements contains a unique element 0
(zero) such that, ∀ x∈S, 0 x = x 0 = 0, we say that 0 is a zero element (or just
a zero) of S and S is a semigroup with zero. If S has no zero element, then an
extra element 0 can be adjoined to S, we define S 0 = 0 = 0 S and 0 0 = 0
∀ s ∈ S. We refer to S0 =S ∪{0} as a semigroup obtained from S by adjoining
zero if necessary. A semigroup with zero, sometimes written as S0 such that
xy = 0 ∀ x, y ∈ S is called a null semigroup. A semigroup with zero is called a
0 group if and only if ∀a ∈S \{0} aS=S and Sa= S.
A non-trivial example of semigroup are the so called left (right) zero
semigroups. A non-empty set L such that ∀ a,b∈ L, ab = a, is called a left
zero semigroup. Similarly, we define a right zero semigroup R such that
∀a,b∈R, ab = b. Observe that for all a in L(R) we have a2 = aa = a such
elements are called idempotent. A semigroup consisting entirely of idempotent
elements is called a band (or Idempotent semigroup).
A non-empty subset A of S is called a subsemigroup if it is closed with
respect to multiplication, that is, if a, b ∈ A, ab ∈ A a condition that can be
expressed more compactly as A2 ⊆ A. The associative condition that holds
throughout S certainly holds throughout A and so A is itself a semigroup. The
sets S, {0}, {1} and {e} are special subsemigroups of S.
8
A non empty subset A of S is called a left Ideal if SA ⊆ A, a right ideal,
if AS ⊆ A, and two sided if it is both a left and a right ideal. Every ideal is a
subsemigroup, but the converse is not true.
1.7 MONOGENIC (CYCLIC) SEMIGROUP
The concept of a cyclic semigroup is similar to that of group theory. Let
S be a semigroup, and let {U i I} i : ∈ with I ≠0 i I i
T U
∈ ∩
φ ≠ = is a subsemigroup
of S. Let A be a non empty subset of S, there is at least one subsemigroup of
S containing A, namely S itself. The intersection of all subsemigroups of S
containing A, is a subsemigroup of S we denote it by A , and is a
subsemigroup defined by two properties. (1) A A (j J ). j ⊆ ∈ (2) If U is a
subsemigroup of S containing A, then j < A >=U for each j .
The subsemigroup A consists of all elements of S that can be
expressed as a finite product of elements of A. If A = S, we say that A is a
set of generators or a generating set of S .
If A is finite, i.e. { , , , , }. 1 2 3 n A = a a a … a Then we shall write A
as n a , a , ,a 1 2 … . In the case where A = {a}, a singleton set, when
< a > = { a , a 2 , a 3 , }. If S is a monoid then we can equally talk of the
subsemigroup of S generated a, this will always contain 1,
{1, , , }. 3,
< a >= a a2 a we refer to a as a monogenic subsemigroup of S
generated by the element a. The order of a is the order of the subsemigroup
a .
9
If S is a semigroup in which there exist an element a such that
S =< a >, then S is said to be a monogenic semigroup. A semigroup with only
one generator is referred to as cyclic.
1.8 ORDERED SETS, SEMILATTICES AND LATTICES
A binary relation ≤ on a set X is called a partial order relation if the
relation ≤ is an equivalence relation on X .
A partial order having the extra-property that for all x, y∈ X,
x ≤ y or y ≤ x will be called a total (or linear) order. A set with total order will
be called a totally ordered set (or chain). A set with a partial order is called a
poset.
1.9 GREEN’S EQUIVALENCE: REGULAR SEMIGROUP
In 1951, J.A. Green defined five equivalences H,K,R,D, and J .
These equivalences play a fundamental role in the semigroup theory.
Green’s Equivalences: Let a be an element of a semigroup S. The smallest left
ideal of S containing an element a is Sa ∪{a}, denoted by S1a and is called
the principal left ideal generated by a. An equivalence L on S is defined by
the rule that a L b if and only if S1a = S1b Similarly, we define the
equivalence R by the rule that a R b if and only if aS1 = bS1.
An alternative (internal) characterization is;
Let a, b, c, d ∈ S. Then
(i) a L b iff ∃ x, y ∈ S1 : x a = b, yb = a
a R b iff ∃ u,v∈S1 : au = b, bv = a
10
(ii) L and R are right and left congruence’s respectively.
(iii) L∩R = H and L∪R = D The smallest equivalence containing both
L and R.
The equivalence J is defined by the rule that
, , , 1 , , .
1 1 1 1
x y u v S xay b ubv a
a J b S a S S b S
⇔ ∃ ∈ = =
⇒ =
An element a∈S is called regular; if there exists x in S such that
a x a = a. Obviously, idempotents are regular. If every element of a semigroup
S is regular, we say that S is a regular semigroup.
Groups are of course regular semigroups and also every rectangular
band B is trivially regular, since a x a=a for all a, x in B
Every idempotent e in a semigroup S is right identity for Re(right
regular D-class) and a left identity for Le.(left regular D-class) An element
a’ in S is called an inverse of a if aa’a= a, a’a a’ =a’ .
An element with an inverse is necessarily regular, if a’ is an inverse of
a then a is an inverse of a’ . Every regular element has an inverse, if there
exist x in S such that axa = a then, let x’ = xax, ax’a = a, x’ax’ = x’ .
An element a in S may have more than one inverse. Indeed, in a
rectangular band every element is an inverse of every other element.
1.10 BASIC GROUP THEORY
Throughout, unless otherwise explicitly indicated, the letter G denotes
an arbitrary group.
11
Let G be a non empty set, the algebraic structure (G,∗) is called a group
if;
(i) G is a semigroup with respect to ∗
(ii) For all g ∈ G ∃ e ∈ G such that g ∗ e = e ∗ g = g , the element e is the
identity element of G.
(iii) To every element g in G, there exist a unique element g−1 ∈ G called the
inverse of g in G with the property that g ∗ g−1 = g−1 ∗ g = e.
Henceforth, unless otherwise explicitly indicated, our groups are
multiplicative. If H is a subset of a group G such that the group operation of
G is closed on H , then H is a subgroup of G and we write H ≤ G, we state
that H is a subgroup of G if for all x, y∈H, x y−1∈H.
If the element e is the identity element of G, the set {e} is the smallest
subgroup of G of order one. This and G itself are called the trivial (improper)
subgroups of G. Any other subgroup H of G is said to be a proper subgroup
of G.
We say that G is commutative or abelian if every pair of its elements
commutes, i.e. 1 2 ∀ g , g in G. , 1 2 2 1 g g = g g otherwise it is non-abelian. By the
cardinality of G we mean the number of elements of the set G which we
called the order of G and is denoted by G or o(G).
The order of an element g ∈G is the least positive integer n , if one
exists, such that an = e, then g is said to be of order n , if no such n exist,
then g is said to be of infinite or zero order.
12
Let g ∈G , if the group G can be generated by an element g ∈G such
that { } + G = gn : n∈ Ζ then G is said to be a cyclic group generated by g, and
written as g = G. If g generates G then so is g−1 ∈G, and the order of g is
equal to the order of G. Thus, if the 0(G) = n and 0(g) = m Then m and n are
relatively prime.
If 0(G) = p, p a prime number, then G is cyclic and has no proper
subgroup.
1.11 PERMUTATION GROUP
Let { } n n X x , x , , x = 1 2 … be a finite set of arbitrary elements, a permutation
on n X is a one-to-one mapping of n X onto itself. The set of all permutations
on n X forms a group with respect to permutation multiplication (composition
of mappings). The set of all permutations on n elements is denoted by
( ) n n S or Sym X and called the symmetric group of degree n, the degree of n S is
the number of elements in the finite set permuted. The number of elements in a
permutation on n elements is n! and is the order of n S (i.e. S n!). n = A
Permutation group G is a subgroup of a symmetric group. Elements of
permutation groups are denoted by lower case letters as well as elements of
abstract groups.
The inverse permutation n β ∈ S is given by 1 ,
n β − ∈ S if β takes y
into x and then β −1 permutation inverse of β takes the point x to y ,
xβ −1 = y . The identity permutation on n X is the identity mapping which leaves
all points of n X fixed, i : x → x (x)i = x ∀x ∈G .
13
Any element ( ) n g ∈Sym X can be written in , . . ( ), 1 2 r r − cycle i e g = x x …x
such that mapped , 1 2 x is to x 2 3 x is mapped to x r−1 … x 1 and x is mapped to x r and
any other element of n X to itself. The length of a cycle is the number of
distinct elements (points) which occur in the cycle.
Each cycle can be decomposed uniquely into disjoint cycles. A cycle
which interchanges only two points and fixes the rest is called a transposition.
Every permutation can be written as a product of transpositions,
( )( ) ( ) n n g x1 y1 x2 y2 x y = .
An element ( ) n g ∈ Sym X is said to be even if it can be expressed as a
product of even number of transpositions and odd if it can be expressed as a
product of odd number of transpositions. A t − cycle can be expressed as a
product of t −1 transpositions; a t − cycle is an even permutation if it has odd
length and is odd if it has even length. A transposition is odd while the identity
element is even by convention.
The set of all even permutations on n X forms a group called the
alternating group and denoted by , x ( ) : : { ( ) : }.
n n n A A or A x A = g ∈Sym X g is even
We state that ( )
2
Sym X : A 2 or A n! n n = = and n A is a normal subgroup of
Sym( X ) . Two permutations n α and β in S are conjugate in n S if and only if
they have the same cycle. The cyclic form of the permutations g −1xg is
obtained by replacing each point α in the cyclic form of x by α g . Thus if
x = (578)(321) g = (152)(743) then g−1xg = (5g, 7g, 8g, 3g, 2g, 1g) = (248)(715)
14
1.12 TRANSFORMATIONS
The analogue to the symmetric group n S of all permutations of a set n X is the
full transformations semigroup n T consisting of all mappings from n X into n X .
The operation in both cases is composition of mappings. Simple combinatorics
yields n
n n S = n! T = n
1.13 GROUP HOMOMORPHISM (SEMIGROUP MORPHISM)
Let Ψ be a mapping from a set M into a set N denoted as
Ψ:M → N or Ψ:M →MΨ where mΨ or Ψ(m) is the image of an element
in Ψ . A homomorphism from a group M to a group N is a mapping
Ψ : M → N such that ( )Ψ = Ψ Ψ 1 2 1 2 m m m m for all , . 1 2 m m ∈M In that case Ψ is
said to preserve the respective operations in M and N. In the sense that if
operation in M and N are • and ∗ respectively, then ( ) . 1 2 1 2m • m Ψ = mΨ∗m Ψ A
homomorphism of a group into itself is called an endomorphism.
Let Ψ :M → N be a homomorphism of groups. We define the kernel of
Ψ (written kerΨ) as ker Ψ:= { m∈M :mΨ =1} and it is a normal subgroup of M .
The image of Ψ is imΨ:={mΨ∈ Ν : m ∈ M } is a subgroup of N. The kerΨ = 1
if and only if the homomorphism Ψ is a one to one mapping. Every
homomorphism Ψ :M → N gives rise to a natural factor group namely G kerϕ .
It can easily be verified that if N is normal in M, then each factor group N
M
gives rise to the natural homomorphism N
Ψ: M → M defined by m imΨ = N for
all m∈M with kerΨ = N.
15
Let the mapping Ψ :M → N be a bijective (one to one and onto)
homomorphism, then Ψ−1 : N → M is also a homomorphism and Ψ is said to
be an isomorphism denoted as M ≅ N read as M is isomorphic to N. If
M ≅ N, then the order of M and N is the same, and the identity e′∈ N is the
image of identity e∈M.
We state without proof the three main isomorphism theorems.
1.13.1 The First Isomorphism Theorem
If Ψ: M → N is a homomorphism of groups then M kerϕ ≅ imϕ .
1.13.2 The Second Isomorphism Theorem
Let M be a subgroup of G and N a normal subgroup of G. Then
, (NM ) .
NM ≤ G N ∩M M and M ≅ M M ∩ N
1.13.3 The Third Isomorphism Theorem
Let G be a group. If N is normal in G and N ≤ M G , then
( ) ( ) M
G
N
M
N
G
N
G
N
M and / ≅
An isomorphism of a group G into itself is said to be an automorphism
of the group G . The mapping Ψ: M →M given by mΨ = m for all m∈M , is an
automorphism iff M is an Abelian group.
1.14 DIRECT PRODUCTS
Let M and N be any two groups, the (external) direct product of M and
N denoted by M × N , is the set of ordered pairs (m, n), m∈ M and n∈ N, with
coordinate wise multiplication
( , ) ( , ) ( , ), , , , . 1 1 2 2 1 2 1 2 1 2 1 2 m n m n = m m n n m m ∈ M n n ∈ N
16
The unit element is (1, 1), the inverse of (m, n) is (m−1 ,n−1 ). The new
group is known as the direct product M × N and it is routine to verify the
axioms of a group.
A group G is said to be decomposable if its subgroups M and N are
such that every element of G is expressible as a product mn with
m ∈ M and n ∈ N; every element of M commutes with every element of N
and M ∩N =1. If not, it is said to be indecomposable.
The correspondence (m,n)→ (n,m) shows that M ∗ N and N ∗M are
isomorphic. Let M and N be normal subgroups of G such that G = M ∗ N, the
mappings Ψ :G → M and Φ:G→ N defined by Ψ :(m,n)→ m and
Φ: (m,n)→n for all (m,n)∈G then Φ and Ψ are surjective homomorphism
called projection of G onto M and onto N respectively.
We say that kerΨ = 1∗ N and kerΦ = M ∗1 if it is a subgroup of G such
that H Ψ = M and HΦ = N. In that caseG , is said to be the sub-direct product of
M and N .
1.15 COSET
Let H be a subgroup of a group G and a ∈ G. The subset
Ha:= {ha : h∈ H} is called a right coset of H in G (or residue classes modulo
the subgroup) generated by a. Left cosets of H in G are defined in an
analogous way.
17
Any two left (right) cosets of H in G are either disjoint or identical. If
a,b ∈ G, Ha = Hb iff ab−1 ∈ H, we say that a is congruent to b mod ulo H,
symbolically, we write a ≡ b(mod H) iff ab−1 ∈ H.
The relation, congruency, is an equivalence relation. Therefore, it
partitions G into disjoint equivalence classes. The equivalence classes
corresponding to a ∈G is defined as, [a] = {x ∈ G x ≡ a mod H }. The number of
distinct right (left) cosets of H in G is called the index of H in G , and will be
denoted by G : H or [G : H], if G is a finite group we have G : H = G / H .
By Lagrange’s theorem, the order of a subgroup of a finite group G
divides the order of the group, for which we can show that
H
G
G : H =
Equally, the order of an element of a finite group divides the order of the
group.
1.16 Normal Subgroup
Let N be a subgroup of a group G. The subgroup N is normal in G,
denoted as N G, if and only if gN = Ng for all g ∈G or
equivalently g−1Ng = N for all g ∈G . The normalizer of H in G is denoted
by N(H) := {g ∈G H g = H}= {g ∈G Hg = gH}≤ G . We call G simple if its
only normal subgroups are the trivial subgroups {e} and G .
If H is normal in G then the set H {gH g G}
G = ∈ is called the factor or
quotient group of G by H . The product on the set is defined by the rule
g H g H = g g H for all g g ∈G 1 2 1 2 1 2 , .
18
The identity element of H
G is H and g−1H is the inverse of gH.
Let g, a ∈G the element a−1ga = ga is known as the conjugate
of g by a if a−1ga = b . Then b is said to be conjugate to g and b is also called
the transform of g by a,written as a ~ b. The relation ~ partition G into
equivalence classes, and conjugate elements have the same order. We write
C(a) or [a] for the set of all elements conjugate to a ∈G called the conjugacy
classes of a.
We defined the conjugate subgroups of G as if M and N are two
subgroups of a group G. In that case, N is said to be conjugate to M if there
exist an element x ∈G such that N = x−1Mx.
If N = x−1Mx, then N is called the transform of M by x. We write
N ~ M if N is conjugate to M. The relation ~ on the sets of subgroups of G is
also an equivalence relation as in elements in G.
The centralizer of g in G is defined by C (g) {g G y gy g} G := ∈ : −1 =
If the conjugacy class of g consist of just g, then g is known as a self
conjugate element. C (g) {g G x G x gx g} G = ∈ ∀ ∈ , −1 =
There is a one-one correspondence between the conjugacy class of g in G and
the set of right cosets of the centralizer of G and C l (g) G C (g) G G = :
C (H) {x G xh hx for all h H } G := ∈ = ∈
{x G h h for all x H} {C ( x) x H } G
:= ∈ x = ∈ = ∩ ∈
is a subgroup of G . Indeed, C (H) {C (x) x H} G. G G = ∩ ∈ ≤
19
If H = G then C (H) G is called the centre of G and it is denoted as Z(G).
Z(G) := {g ∈ G gx = xg ∀x ∈ G}
1.17 p – GROUPS
Throughout this section, p -denotes a prime number.
Let G be a group, such that every element of G has prime power order
for some fixed prime p, then G is called a p -group.
Lagrange’s theorem assures that in a given group G, certain types of
subgroups do not exist; it however, provides a necessary condition for the
existence of a subgroup. In 1875 Sylow provides a sufficient condition for the
existence in a group of subgroups of certain orders. Suppose H is a proper
subgroup of G and 0(H) = n, 1 < n < p , then n cannot divide p . Thus a group
of prime order can have no proper subgroup, e.g. the alternating group of
degree 4, 4 A has no subgroup of order 6 although 6 divides 12.
Let G be a finite group, such that G = pr s and r a natural number
where p is a prime and (p,s) = 1. Each subgroup of order pr in G is called a
Sylow p -subgroup of G and if N is any p -subgroup of G then H ⊆ x−1N x
for some x ∈G.
We state without proof the three Sylow theorems.
1.17.1 Sylow’s first theorem
Let G be a finite non-abelian group and G = prm and (p,m) =1. Then
for each n∈ Ζ such that 0 ≤ n ≤ r , G has a subgroup of order pn .
20
Thus, G = pr for some r if and only if the order of every element of G
is a power of p.
1.17.2 Sylow’s second theorem
In a finite group the Sylow p -subgroups (for a fixed prime p ) are all
conjugate and are isomorphic.
1.17.3 Sylow’s third theorem
In a finite group the number of Sylow p -subgroups (for a fixed prime
p ) is congruent to 1 modulo p.
1.18 GROUP ACTIONS ON GROUPS
Let M and N be groups. We say that M acts on N as a group if to each
m∈M and each n∈ N, there corresponds a unique element m ∈ M such that
i (mn )n mn n ii m m iii (n n )m nmnm1 2 1 2
( ) 1 2 = 1 2 ( ) 1 = ( ) = ∀ m m m ∈ M and n n n ∈ N 1 2 1 2 , , , ,
Let M act on N as groups, then for each m∈M, there corresponds an
automorphism Ψ: N → Nm of N and the mapping m Ψ : M → Ψ is a
homomorphism of M int o Auto(N). We call Ψ the automorphism
representation of M or simply action.
1.19 BASIC COMBINATORICS
Combinatorics could be described as the art of arranging objects
according to specified rule. We want to know, first, whether a particular
arrangement is possible at all. If so, in how many ways can it be done?
Combinatorics depends on two elementary rules. (i) Disjunctive (or
Sum) rule; if E (i k ) i =1, 2, …, are k events such that no two of them can occur at
21
the same time, and if i E can occur in i n ways, then one of the k events can
occur in n1 + n2 +…+ nk ways. (ii) Sequential or Product Rule; if an event can
occur in m ways and a second event in n ways, and if the number of ways the
second event occurs does not depend upon how the first event occurs, then the
two events can occur simultaneously in mn ways. More generally, if
E (i k ) i = 1,2,…, are k events and if i E can occur in 1 n ways, 2 E can occur in 2 n
and k E can occur in k n ways (no matter how the previous k −1events occur),
then the k events can occur simultaneously in k n1 n2 n3…n ways.
1.20 THE BINOMIAL THEOREM
Let n and k be non-negative integers, with 0 ≤ k ≤ n. The binomial
coefficient ⎟
⎟⎠
⎞
⎜ ⎜⎝
⎛
k
n is defined to be the number of k − element subsets of a set of n
elements. This numbers is often written as k
nC or ⎟
⎟⎠
⎞
⎜ ⎜⎝
⎛
k
n and read as n choose k.
It is called a binomial coefficient.
( ) ( )
( ) !( )!
!
1 1
1 1
k n k
n
k k
n n n k
k
n
−
=
−
− − +
= ⎟⎠
⎞
⎜⎝
⎛
where, 1
0
= ⎟⎠
⎞
⎜⎝
⎛n is the empty set and . 1 = ⎟⎠
⎞
⎜⎝
⎛
n
n
1.21 PERMUTATIONS AND COMBINATIONS
The number of selections of k objects from a set of n objects where
repetition is allowed and order is significant is given by nk . If the order is not
significant, it is given by .
1⎟⎠
⎞
⎜⎝
⎛ + −
k
n k
22
If the repetitions is not allowed and order is significant it is given by
( ) ( ) 1 1 + − − k n n n … . But if the order is not significant, it is given by . ⎟⎠
⎞
⎜⎝
⎛
k
n
1.22 RECURRENCE RELATIONS AND GENERATING FUNCTIONS
1.22.1 Recurrence Relation
If , ,, , 0 1 k a a a is a sequence of real numbers such that there is an
equation relating to the term ( ) 0 a for any n n n ≥ to one or more of its
predecessors in the sequence, then this equation is a recurrence relation obeyed
by the sequence. For example, the sequence 0!, 1!, 2! , satisfies the
recurrence relation ( 1) 1 = ≥ − a na n n n .
Conversely, given this relation and the initial condition 1, 0 a = one can
recover the entire sequence by iteration.
[( 1) ] [ ( 1)( 2) ] ( 1) (1) ! 1 3 a n n a n n n a n n n n n n = − = − − = = − = − −
The recurrence relation;
( ) n 1 n 1 1 n 1 1 n r a ca ca ca f n − − − = + + + +
In which, C (i r ) i =1,2,…, are constants, with ≠0, i C is called a linear
recurrence relation with constant coefficients of order r.
1.22.2 Generating Function
The sequence of real numbers , , ,… 1 2 a a a o and a dummy variable x ,
have ordinary generating functions as ( ) = + + 2 +…
0 1 2g x a a x a x and exponential
generating function as ( ) .
1! 2!
2
= 0 + 1 + 2 +…
x
a
x
G x a a
23
1.23 SOME SPECIAL NUMBERS
1.23.1 Bell Numbers
The Bell numbers n B is the number of partitions of an n -set or the
number of equivalence relations on an n -set (if R is an equivalence relation on
X , then the equivalence classes of R form a partition of X and the converse is
also true).
The recurrence and generating functions for Bell numbers is given by
Σ=
− ≥ ⎟⎠
⎞
⎜⎝
⎛
−
−
=
1
, 1
1
1
k
n n k B for n
k
n
B , 1
0
, 1
!
x n n
n
e B x for n
n
∞
−
=
=Σ ≥
1.23.2 Fibonacci numbers
In his book “Liberabaci” which appeared in 1202, the Italian
mathematician Fibonacci gives this problem (the Rabbit Problem):
How many pairs of rabbit can be produced from a single pair in a year if
every month each pair begets a new pair which from the second month on
becomes productive?
Let us denote by F(n) the number of pairs after n months starting from
the beginning of a year. We see that in n + 1 months there will be F(n) pairs
and as many more newly born pairs as there were at the end of the month n−1,
which is to say, F(n−1) pairs of rabbits. In other words, we have the recurrence
relation
( ) ( ) ( ) 1 1 1 1 + − + = + − = + n n n F n F n F n or F F F
Since, by hypothesis, F(0) =1 and F(1) =2.
24
We find, in succession, F(2) =3, F(3) =5, F(4) =8, etc. In particular,
F(12) =377.
The numbers F(n) are called Fibonacci numbers.
Fibonacci sequence 1, 2, 3, 5, 8,… , is defined by the recurrence relation
( ) ( ) 1 2 1 2 − − = − + − = + n n n n f f n f n or f f f
Such that f (0) = f (1) = 1
Thus, the ordinary generating function of Fibonacci sequence is
Σ ( ) Σ ( ) Σ ( ) ∞
=
∞
=
∞
=
= − − + − −
2 2 2
1 1 2 2 2
n n n
f n x n x f n x n x f n xn
The Catalan and Bell numbers are two important sequences of numbers.
They have several, apparently accidental, common properties.
1.23.3 The Catalan Numbers
The Catalan Numbers are 1, 2, 5, 14, 42, … and appear in many guises.
For example, in how many ways can sums of n terms be bracketed so that it
can be calculated by adding two terms at a time? (Five possibilities)
The recurrence relations for the Catalan numbers is given by
Σ−
=
− = >
1
1
, 1.
n
i
n i n i C C C n
Here C ( i n) n 1 ≤ ≤ is the number of ways of bracketing a sum of n terms.
The Catalan numbers n C is ⎟
⎟⎠
⎞
⎜ ⎜⎝
⎛
−
−
=
1
1 2 1
n
n
n
Cn ,
The generating functions for Catalan numbers is given as
0 11 2 2 C(x)=C +C x +C x +
25
1.23.4 Sterling Numbers
Let n and k be positive integers with k ≤ n, the sterling number of the
first kind, s(n, k ) is defined by the rule that ( 1)n k s(n,k ) − − is the number of
permutations of {1, 2, …, n} with k -cycle.
The sterling numbers of the second kind S(n, k ) is the number of
partitions of {1, …, n} with k (non-empty) parts.
The recurrence relation is given by S(n +1,k ) = S(n,k −1)− nS(n,k) such
that S(n , 0) = S(n ,1) = 0 for all n.
1.23.5 Proposition
Σ( ) ( ) Σ ( )
= =
− − = =
n
k
n
k
a n S n k S n k n
1 1
1 ; ! , , 1 ) ( ( ) Σ=
=
n
k
n b S n k B
1
( ) , , nth Bell numbers.
S(n,n) = S(n,k) = 1,S(n +1,k) = −nS(n,k) + S(n,k −1),and S(n +1,k) = kS(n,k) + S(n,k −1)
1.24 DERANGEMENTS
A derangement of {1, 2,…, n} is a permutation of this set which leaves no
point fixed. Let d(n) be the number of derangements of {1 ,…, n}. Any
derangement moves the point n to some point i < n (fixed no point of n ).
Thus, d(n) is given as three terms recurrence relation.
d(n) = (n −1)d(n −1)+ d(n − 2). d(0) = 1, d(1) = 0 .
( ) ( )
⎟ ⎟
⎠
⎞
⎜ ⎜
⎝
⎛ −
= Σ=
n
i
i
i
d n n
0 !
! 1
This is the nearest integer to ! for n ≥ 1,
e
n where e is the base of natural
logarithms.
26
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
