Page 98 - DMTH403_ABSTRACT_ALGEBRA

Unit 8: Permutation Groups

We represent any f  S in n 2-line form as Notes
n
 1 2 .... n 
f    .
 f(1) f(2) .... f(n) 
Now, there are n possibilities for f(l), namely, 1, 2, . . . , n. Once f(1) has been specified, there are
(n – 1) possibilities for f(2), namely, {1, 2, . . . , n} \ {f(1)}. This is because f is 1-1. Thus, there are
n(n – 1) choices for f(1) and f(2). Continuing in this manner, we see that there are n! different
ways in which f can be defined. Therefore, S, has n! element.
Now, let us discuss at the algebraic structure of S(X), for any set X. The composition of
permutations is a binary operation on S(X). To help you regain practice in computing the
composition of permutations, consider an example.

 1 2 3 4   1 2 3 4 
Let f =  2 4 1 3  and g   4 1 3 2  be in S .
4
   
Then, to get fog we first apply g and then apply f.
 f o g(1) = f(g(1)) = f(4) = 3.
f o g (2) = f(g(2)) f(1) = 2.
f o g (3) = f(g(3)) = f(3) = 1.

f o g (4) = f(g(4)) = f(2) = 4.

 1 2 3 4 
 f o g =  
 3 2 1 4 
We show this process diagrammatically in Figure 8.1.

Figure 8.1: (1 2 3 4) o (1 4 2) in S 4

Now, let us go back to S(X), for any set k.
Theorem 1: Let X be a non-empty set. Then the system (S(X), 0 ) forms a group, called the
symmetric group of X.
Thus, S is a group of order n!. We call S , the symmetric group of degree n. Note that if f  S , then
n
n
n
f  1    f(1) f(2) .... f(n)  .
 1 2 .... n 

LOVELY PROFESSIONAL UNIVERSITY 91