Proposition 15 • Statement ○ |S_n |=n! • Proof ○ First, we prove that if X and Y are sets of order n, then ○ There are n! injective functions from X to Y ○ We argue by induction on n ○ n=1 § Clear ○ n 1 § Suppose f:X→Y is injective § Let x∈X, then there are n possibilities for f(x) § f restricts to an injective function X∖{x}→Y∖{f(x)} § There are (n−1)! such functions, by induction § Thus, there are n(n−1)!=n! injective functions X→Y ○ Now, take X={1,…,n}=Y ○ Then every injection between finite sets of the same order is a bijection ○ Notice that the sets must be finite (Counterexample: f:Z→Z, n↦2n) Cycle • Definition ○ Fix n∈Z( 0). Let a_1,…,a_t∈{1,…,n} ○ The element of S_n given by § a_i↦a_(i+1) for 1≤i≤t−1 § a_t↦a_1 § j↦j if j∉{a_1,…a_t } ○ is denoted by (a_1,a_2,…,a_t ) and is called a cycle of length t • Example ○ Let σ=(1 3 2)∈S_4, then ○ (■8(i&1&2&3&4@↓&↓&↓&↓&↓@σ(i)&3&1&2&4)) ○ Notice: (1 3 2)=(3 2 1)=(2 1 3) Disjoint Cycles • Definition ○ Two cycles (a_1,…a_t ) and (b_1,…,b_k ) are disjoint if ○ {a_1,…a_t }∩{b_1,…,b_k }=∅ • Example ○ (1 2), (3 4)∈S_4 are disjoint • Fact ○ Every element of S_n can be written as a product of disjoint cycles ○ S_1={(1)} ○ S_2={(1),(1 2)} ○ S_3={(1), (1 2), (1 3), (2 3),(1 2 3), (1 3 2)} ○ S_4 = {(1), (1 2), (1 3), (1 4), (2 3), (2 4), (3 4), (1 2 3), (1 2 4), (1 3 2), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3), (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2), (1 2)(3 4), (1 4)(2 3), (1 3)(2 4s)} ○ Note: We write the identity of S_n as (1) Cycle Decomposition for Permutations • Algorithm Method Example a≔min{x∈Nx not appeared in previous cycles} (1 Begin the new cycle: (a b≔σ(a) σ(1)=12=b If b=a 12≠1 • close the cycle with a right parenthesis So write (1 12 • return to step 1 If b≠a • write b next to a in this cycle: (a b c≔σ(b) σ(12)=8 If c=a 8≠1 • close the cycle with a right parenthesis So continue the cycle as: • return to step 1 (1 12 8 If c≠a • write c next to in this cycle: (a b c b≔c and repeat this step until the cycle closes Naturally this process stops when all the numbers from {1,2, …,n} have appeared in some cycle. σ = (1 1 2 8 10 4)(2 1 3)(3)(5 1 1 7)(6 9) Remove all cycles of length 1 σ = (1 1 2 8 10 4)(2 1 3)(5 1 1 7)(6 9) • Example ○ Take σ∈S_13 to be the following ○ (■8(i&1&2&3&4&5&6&7&8&9&10&11&12&13@↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓@σ(i)&12&13&3&1&11&9&5&10&6&4&7&8&3)) ○ Start with 1, σ(1)=12, so write 12 after 1. ○ Keep going until you cycle back to 1 ○ Start with the smallest number which hasn t yet appeared, and repeat. ○ Repeat this step until 1,…,13 have all appeared. Product of Cycles • Reminder: Read from right to left • Example ○ Write σ=(1 2 3)(1 2)(3 4) as a product of disjoint cycles ○ What is σ(1)? § (3 4) maps 1 to 1 § (1 2) maps 1 to 2 § (1 2 3) maps 2 to 3 § Thus σ(1)=3 ○ Similarly σ(3)=4, σ(4)=1 ○ Thus we close the cycle (1 3 4) ○ We won t write down (2), since it is the identity ○ Thus σ=(1 3 4)(2)=(1 3 4) ○ Note: σ∈S_4, but it make sense to think of σ∈S_n for n 4 • Commutativity of S_n ○ (1 2)(1 2 3)=(2 3) ○ (1 2 3)(1 2)=(3 1) ○ In particular S_3 is not abelian ○ Therefore S_n is not abelian for n≥3
