## 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»**