Project Materials

Combinatorial Properties of the Alternating & Dihedral Groups and Homomorphic Images of Fibonacci Groups

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.

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

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.