Permutations
Definition: A permutation of a set X is a rearrangement of its elements. Example: Let X = {1, 2, 3}. Then there are 6 permutations: 123, 132, 213, 231, 312, 321.

Definition : A permutation of a set X is a one-one correspondence (a bijection) from X to itself. Notation: Let X = {1, 2, . . . , n} and α : X → X be a permutation. It is convenient to describe this function in the following way: α= 1 2 ... n α(1) α(2) . . . α(n) .

Example: 1 2 2 1 1 2 3 1 2 3 1 2 3 2 3 1 1 2 3 4 1 4 3 2 1 2 3 4 5 3 5 4 1 2

Definition: Let X = {1, 2, . . . , n} and α : X → X be a permutation. Let i1 , i2 , . . . , ir be distinct numbers from {1, 2, . . . , n}. If α(i1 ) = i2 , α(i2 ) = i3 , . . . , α(ir−1 ) = ir , α(ir ) = i1 ,

and α(iν ) = iν for other numbers from {1, 2, . . . , n}, then α is called an r-cycle. Notation: An r-cycle is denoted by (i1 i2 . . . ir ). Example: 1 2 3 4 5 2 5 3 4 1 1 2 3 4 5 2 5 4 3 1 = (125) 3 − cycle is not a cycle

1

Remark: We can use different notations for the same cycles. For example, 1 2 3 1 2 3 = (1) = (2) = (3), 1 2 3 2 3 1 = (123) = (231) = (312).

Warning: Do not confuse notations of a permutation and a cycle. For example, (123) = 123. Instead, (123) = 231 and 123 = (1).

Composition (Product) Of Permutations
Let α= Then α◦β = β◦α= 1 2 ... n α(β(1)) α(β(2)) . . . α(β(n)) 1 2 ... n β(α(1)) β(α(2)) . . . β(α(n)) , . 1 2 ... n α(1) α(2) . . . α(n) and β = 1 2 ... n β(1) β(2) . . . β(n) .

Example: Let α = 1 2 3 4 5 5 1 2 4 3 α◦β = , β= 1 2 3 4 5 4 2 5 1 3 . We have: 1 2 3 4 5 4 1 3 5 2 1 2 3 4 5 3 4 2 1 5

1 2 3 4 5 5 1 2 4 3 1 2 3 4 5 4 2 5 1 3

1 2 3 4 5 4 2 5 1 3 1 2 3 4 5 5 1 2 4 3

=

,

β◦α=

=

.

Remark: It is convenient to represent a permutation as the product of circles. Example: 1 2 3 4 5 6 7 8 9 3 2 6 9 5 7 1 8 4 = (1367)(49)(2)(5)(8) = (1367)(49)

2

Remark: One can find a composition of permutations using circles. Example: 1. Let α= β= We have: α ◦ β = (1532)(14)(35) = (1452)(3) = (1452) = β ◦ α = (14)(35)(1532) = (1324)(5) = (1324) = 2. Let α = 1 2 3 4 5 6 7 5 4 6 1 7 3 2 1 2 3 4 5 4 1 3 5 2 1 2 3 4 5 3 4 2 1 5 , . 1 2 3 4 5 5 1 2 4 3 1 2 3 4 5 4 2 5 1 3 = (1532)(4) = (1532), = (14)(2)(35) = (14)(35).

= (15724)(36). Find α−1 . We have: α−1 = (42751)(63)

In fact, α ◦ α−1 = (15724)(36)(42751)(63) = (1) and α−1 ◦ α = (42751)(63)(15724)(36) = (1). Theorem: The inverse of the cycle α = (i1 i2 . . . ir ) is the cycle α−1 = (ir ir−1 . . . i1 ). Theorem: Every permutation α is either a cycle or a product of disjoint (with no common elements) cycles.

Solutions
1. Determine which permutations are equal: (a) (12) = 12 (b) (1) = 12 (c) (1)(2) = (1) (d) (12)(34) = (1234) (e) (12)(34) = (123)(234) (f) (12)(34) = (123)(234)(341) 3 (g) (124)(53) = (53)(124) (h) (124)(53) = (124)(35) (i) (124)(53) = (142)(53) (j) (12345) = 12345 (k) (12345) = 23451 (l) (23451) = 23451

2. Factor the following permutations into the product of cycles: 1 2 3 4 5 6 7 8 1 2 3 5 4 6 7 8 1 2 3 4 5 6 7 8 9 10 11 12 5 3 10 4 11 12 6 9 1 2 8 7 = (4 5)

= (1 5 11 8 9)(2 3 10)(6 12 7) = (3 12 10)(4 7 8)(5 9)(6 14 13 11)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 12 7 9 14 8 4 5 3 6 10 11 13 15 3. Find the following products:

(12)(34)(56)(1234) = (24)(56) (12)(23)(34)(45) = (12345) (12)(34)(56) = (12)(34)(56) (123)(234)(345) = (12)(45) 4. Let α = (135)(24), β = (124)(35). Find: (a) αβ = (143) (b) βα = (152) (c) β −1 = (421)(53) (d) α2004 = (1)

Problems
1. Factor the following permutations into the product of cycles: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 3 6 15 8 2 7 11 10 9 1 12 13 14 4 2. Find the following products: (134)(23)(235)(45) (24)(35)(12345) (345)(234)(125) 3. Let α = (124)(3567). Find: (a) α−1 (b) α12

4

Groups
Definition: An operation on a set G is a function ∗ : G × G → G. Definition: A group is a set G which is equipped with an operation ∗ and a special element e ∈ G, called the identity, such that (i) the associative law holds: for every x, y, z ∈ G, x ∗ (y ∗ z) = (x ∗ y) ∗ z; (ii) e ∗ x = x = x ∗ e for all x ∈ G; (iii) for every x ∈ G, there is x ∈ G with x ∗ x = e = x ∗ x. Example: Set Operation “+” Operation “∗” Additional Condition

Example: Set Operation “+” Operation “∗”

5

Example:

Set {2n : n ∈ Z}

Operation “+” Operation “∗”

{2n + 1 : n ∈ Z}

{3n : n ∈ Z}

{kn : n ∈ Z}, where k ∈ N is some fixed number {an : n ∈ Z}, where a ∈ R, a = 0, ±1, is some fixed number p : p ∈ N, n ∈ Z≥0 2n

Example: Set R>0 Operation a ∗ b = ab

R>0

a ∗ b = a2 b 2

6

Definition: An operation on a set G is a function ∗ : G × G → G.

Definition: A group is a set G which is equipped with an operation ∗ and a special element e ∈ G, called the identity, such that (i) the associative law holds: for every x, y, z ∈ G, x ∗ (y ∗ z) = (x ∗ y) ∗ z; (ii) e ∗ x = x = x ∗ e for all x ∈ G; (iii) for every x ∈ G, there is x ∈ G with x ∗ x = e = x ∗ x.

Set N

“+”

“∗”

Add. Cond.

Z

Q

R

R\Q

Set Z>0 Z≥0 Q>0 Q≥0 R>0 R≥0

“+”

“∗”

Set {2n : n ∈ Z}

“+” “∗”

{2n + 1 : n ∈ Z}

{3n : n ∈ Z}

{kn : n ∈ Z} {an : n ∈ Z}, where a = 0, ±1 p 2n

: p ∈ N, n ∈ Z≥0

Set Operation R>0 a ∗ b = ab

R>0 a ∗ b = a2b2