6.3 Permutation groups and cyclic groups Exampl ole: Consider the equilateral triangle with vertices 1, 2, and3. Letl1, l2, and l3 be the angle bisectors of the corresponding angles, and leto be their point of intersection a Counterclockwise rotation of the triangle about through120°,240°,360°(0°)
6.3 Permutation groups and cyclic groups Example: Consider the equilateral triangle with vertices 1，2，and 3. Let l1 , l2 , and l3 be the angle bisectors of the corresponding angles, and let O be their point of intersection。 Counterclockwise rotation of the triangle about O through 120°,240°,360° (0°)
f2:1→>2,2→)3,3-)1 nf:1-)3,2-1,3->2 f1:1-1,2->2,3-)3 reflect the linesli,l2, and l3. g1:1-1,2->3,3->2 g2:13,2->2,3-)1 ng3:l->2,2-1,3->3
f2 :1→2，2→3，3→1 f3 :1→3，2→1，3→2 f1 :1→1，2→2，3→3 reflect the lines l1 , l2 , and l3 . g1 :1→1，2→3，3→2 g2 :1→3，2→2，3→1 g3 :1→2，2→1，3→3
6.3.1 Permutation groups Definition 9: a bijection from a set s to itself is called a permutation of s Lemma 6.1: let s be a set (1) Let fand g be two permutations of s. Then the composition of f and g is a permutation of S (2) Letf be a permutation of s. Then the inverse of f is a permutation of s
6.3.1 Permutation groups Definition 9: A bijection from a set S to itself is called a permutation of S Lemma 6.1：Let S be a set. (1) Let f and g be two permutations of S. Then the composition of f and g is a permutation of S. (2) Let f be a permutation of S. Then the inverse of f is a permutation of S
Theorem 6.9: Lets be a set. The set of all permutations of S, under the operation of composition of permutations, forms a group A(S) Proof: Lemma 6.1 implies that the rule of multiplication is well-defined associative the identity function from s to s is identity element The inverse permutation g of f is a permutation of s
Theorem 6.9：Let S be a set. The set of all permutations of S, under the operation of composition of permutations, forms a group A(S). Proof: Lemma 6.1 implies that the rule of multiplication is well-defined. associative. the identity function from S to S is identity element The inverse permutation g of f is a permutation of S
Theorem 6.10: let s be a finite set with n elements. Then A(S) has n! elements. Definition 10: The group S, is the set of permutations of the first n natural numbers. The group is called the symmetric group on n letters, is called also the permutation group
Theorem 6.10: Let S be a finite set with n elements. Then A(S) has n! elements. Definition 10: The group Sn is the set of permutations of the first n natural numbers. The group is called the symmetric group on n letters, is called also the permutation group
o(1)a(2)…(m) 12 (1)a(2)…o(n)(a(1)o(i2)…a(n)
= (1) (2) ( ) 1 2 n n = = (1) (2) ( ) ( ) ( ) ( ) 1 2 1 2 1 2 n n i i i i i i n n
identity permutation e a(1)a(2)…a(n) inverse permutation of o o 2 a1(1)a(2)…a(n)
= = = − − − − − σ (1) σ (2) σ (n) 1 2 n σ 1 2 n σ(1) σ(2) σ(n) σ 1 2 n 1 2 n e 1 1 1 1 1 inverse permutation of identity permutation
12 n σ(1)a(2)…a( n τ(1)τ(2)…τ(n) n 12 n 0●t= 0(1)0(2)…o(n)丿(τ(1)τ(2)…τ(n) τ(1)t(2) t(n))(12 n o((1)0((2)…o((m))((1)τ(2)…τ(m 0(τ(1)0(τ(2)…o(τ(m)
, τ(1)τ(2) τ(n) 1 2 n τ , σ(1)σ(2) σ(n) 1 2 n σ = = = • = • • = ( (1)) ( (2)) ( (n)) 1 2 n (1) (2) (n) 1 2 n ( (1)) ( (2)) ( (n)) (1) (2) (n) (1) (2) (n) 1 2 n (1) (2) (n) 1 2 n σ τ σ τ σ τ σ τ σ τ σ τ τ τ τ τ τ σ σ σ τ τ τ σ τ τ
Definition 11: Let Sn, and let oESn. We say that o is a d-cycle if there are integers i1; 2;…; id such that o(i1)=i2,σ(2)=i3, andσ(d=i1andσ fixes every other integer, …la-1lala+1 O
= + − + d d n d d d n i i i i i i i i i i i i 2 3 1 1 1 2 1 1 Definition 11: Let |S|=n, and let Sn .We say that is a d-cycle if there are integers i1 ; i2 ; … ; id such that (i1 ) =i2 , (i2 ) = i3 , … , and (id ) =i1 and fixes every other integer, i.e
1···9d A 2-cycle o is called transposition Theorem 6.11. Let o be any element of s Then o may be expressed as a product of disjoint cycles. Corollary 6.1. Every permutation of'sn is a product of transpositions
=(i1 ,…, id ): A 2-cycle is called transposition. Theorem 6.11. Let be any element of Sn . Then may be expressed as a product of disjoint cycles. Corollary 6.1. Every permutation of Sn is a product of transpositions
