S5
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View S5 as PDF for free.
More details
- Words: 1,543
- Pages: 3
How to find all possible permutations of Symmetric group on 5 elements, S5? Since order of Sn, o(Sn) = n! n! ] k-cycles 1 where ∀k ≥ 2 , k .(n − k )! hence, for example S5, the partitions of n (n = 5) with the corresponding cycle structure is shown below: and by the fact that Sn contains [
S5 Partition of n 5+0 4+1 3+2 3+1+1 2+2+1
Cycle Structure (5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1)
2+1+1+1
(2, 1, 1, 1)
1+1+1+1+1
(1, 1, 1, 1, 1)
Number of permutations 4.3.2.1 = 24 5.3.2.1 = 30 ??? 5.4 = 20 ??? 5 .4 = 10 2 1 120
Possible Permutations (1, 2, 3, 4, 5), … (1, 2, 3, 4)(5), … (1, 2, 3)(4, 5), … (1, 2, 3)(4)(5), … (1, 2)(3, 4)(5), … (1, 2)(3)(4)(5), … (1)(2)(3)(4)(5) = (1)
Now, what are the possible number of permutations for partition 3 + 2 and 2 + 2 + 1? Could you able to list out all 120 (5!) possible permutations in S5? Let’s consider the 1st case: 5 + 0, there will be 24 possible permutations can be done. Since permutation (1, 2, 3, 4, 5) is one of them, we can find the others of 23 by fixing at least one elements in (1, 2, 3, 4, 5) and then permute the others. The simplest way of doing this is by fixing 1 and 2 and then varies the last 3 terms as shown below: (1, 2, 3, 4, 5) ⇒ we have 6 possible options for leading (1, 2, _, _, _) i.e. we permute 3, 4 and 5 and thus 3P3 or 3! = 6 We’ll continue with the case of (1, 3, 2, 4, 5) which also gives us 6 permutations by permuting the last three terms. Repeat the process for leading (1, 4, _, _, _) and (1, 5, _, _, _), you will get all 4 possible pairs of 6 permutations of length 5 cycle. Hence, you have 6 x 4 = 24 possible permutations of length 5 cycle. 1
Note: Every permutation of a finite set is the identity, a single cycle or a product of disjoint cycles. The formula used to find number k-cycles is only applicable to the case of single cycle of length k. Do not ever try to apply it for the cases involving product of disjoint cycles and identity. There will always only be one identity in Sn
∀ n > 1 instead of
n! = n . It is because (1) = (2) = (3) = (4) =….(n-1) = (n) (1)(n − 1)!
which are finally considered to be the same as (1).
Case 2: 4 + 1 Suppose we do the same thing by permuting the last three terms in (1, 2, 3, 4)(5), i.e. (1, 2, 3, 4)(5). We’ll again obtain 6 possible permutations in the case of which element 5 is fixed in this cycle of length 4. How about the cases of (1, 2, 3, 5)(4), (1, 2, 4, 5)(3), (1, 3, 4, 5)(2) and (2, 3, 4, 5)(1)? [Writing down the fixed element at the back will be useful this time since this can help us to identify the trend easily]. From that, by considering S5 (n =5), we know there’ll always be one element is fixed (mapped back to itself) in the cycle of length 4. Thus, we know there are 5 possible pairs for cycle structure 4 + 1 to be concerned. Since we’ve obtained the 6 possible permutations in the 1st possible pair (i.e. 5 is fixed), hence there’ll be 6 permutations for each pair of cycle structure 4+1 by repeating the process of permuting the last 3 terms. If we’ve 5 pairs, it means that we’ve all 6 x 5 = 30 possible permutations for the case of 4+1 partition.
Case 3: 3 + 1 + 1 This is concerned with length-3 cycle as (1, 2, 3)(4)(5) = (1, 2, 3). This simply means that we permute 3 elements from 5 which are being listed, but it DOES NOT simply mean that 5P3 = 60 (why?). One way to find the 20 possible permutations is by referring to elements which are listed orderly in ascending sequence as what you’re used to apply when you’re dealing with the case n < 4. 1, 2, 3, 4, 5 We choose the 1st three terms and permute only 2 of them (usually we fix the leading term, i.e. 1). We know there’s only 2 ways to do this i.e. (1, 2, 3) and (1, 3, 2). By repeating the process of choosing (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5) and so on (where 2 and 3 turns out to be the leading term later). This process will be ended up with the permutation (3, 4, 5) and (3, 5, 4) [Check it out!]. There are all 20 permutations as what we expected to be. Hence, as you move along the line at which the elements are being stated, there’ll be 10 permutations can be obtained from (1, 2, 3), (1, 2, 4) until (3, 4, 5). Since we can only permute 2 elements from each of this permutation, they are altogether 10 x 2 = 20 permutations obtained finally. [Tips: Don’t ever look backward from the sequence of elements! For example, we do not worry about (5, 3, 2) or (5, 2, 3) when we’re doing the permutation of (2, 3, 5). The one we’d do is to permute the 2nd and the 3rd elements (3 and 5 respectively) but without changes the leading term, i.e. 2. In addition, the most surprising thing is that you can stop selecting the elements when the leading term is 3 [why we do not need to perform the cycles (4, _, _) or (5, _, _)?].
Case 4: 3 + 2 There are both length-2 and length-3 cycles to be concerned this time; everything has to be handled carefully as the repetition cases might occur without being realized. We do the same thing as previously done: fix some elements and permute the others. Since (a, b) will always be the same as (b, a), hence we do not need to permute elements in cycle of length-2. Instead, we focus on length-3 cycle by fixing the foremost element “1” in permutation (1, 2, 3)(4, 5) as suggested, then permute 2 and 3. Surprisingly, the process of permuting the elements is somehow exactly the same as what we do in length-3 cycle. Believe it or not, you’ll obtained the answer for this case exactly the same as in case 3, with the only difference is the way of writing down the element in cycle of length 2 as (a, b) rather than (a)(b). Hence, we have 20 permutations for the case of partition 3 + 2. [Alternative Method for the case 3 and 4: 4P2 + 3P2 + 2P2 = 20 permutations]. Try it! Case 5: 2 + 2 + 1 Since they are product of 2 disjoint cycles with the same length, i.e. 2, we expect that the repetition will certainly occur in this case [For example, (1, 2)(3, 4)(5) = (4, 3)(1, 2)(5)]. However, again, we make use of the fixed element to help us to identify the trend of what it’s supposed to be happening. Suppose we leave 5 be the fixed element and change the 2nd element in the first cycle from 2 to 4, we’ll only have 3 possible permutations obtained [Check!]. By repeatedly taking different fixed element (other than 5) to guide us in obtaining the result, we’ll spot the trend easily by figuring out the fact that: “for each permutation of partition 2 + 2 + 1 with one possible element which is fixed at the back, there are 3 possible permutations can be obtained”. Since the fixed elements can be 1, 2, 3, 4, or 5, thus there’ll be altogether 5 x 3 = 15 possible permutations can be obtained. Case 6: 2 + 1 + 1 + 1 I’ll leave this case for you as it’s been easy to be worked out as what you’d do for the symmetric group on n < 4. By permutation method, we’ve to permute 2 elements arbitrarily from the total 5 elements, i.e. 5P2 = 20. However, since they are all single cycles of length-2 with the fact that (a, b) = (b, a), thus, the total 20 we found earlier have to be divided by 2 because half of them from the 20 permutation are being the same. Hence, we’ll have 20/2 = 10 permutations for this case. Case 7: 1 + 1 + 1 + 1 + 1 (1)(2)(3)(4)(5) = (1) = (2) = (3) = (4) = (5) = (1) = ε Thus, by summing up all the number of permutations in 7 cases above, we have 24 + 30 + 20 + 20 + 15 + 10 + 1 = 120 = 5! permutations in S5. * Final thought: What can you conclude about A5 and what’s the unique feature can be observed from S2 to S5 about the number of odd and even permutations?
S5 Partition of n 5+0 4+1 3+2 3+1+1 2+2+1
Cycle Structure (5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1)
2+1+1+1
(2, 1, 1, 1)
1+1+1+1+1
(1, 1, 1, 1, 1)
Number of permutations 4.3.2.1 = 24 5.3.2.1 = 30 ??? 5.4 = 20 ??? 5 .4 = 10 2 1 120
Possible Permutations (1, 2, 3, 4, 5), … (1, 2, 3, 4)(5), … (1, 2, 3)(4, 5), … (1, 2, 3)(4)(5), … (1, 2)(3, 4)(5), … (1, 2)(3)(4)(5), … (1)(2)(3)(4)(5) = (1)
Now, what are the possible number of permutations for partition 3 + 2 and 2 + 2 + 1? Could you able to list out all 120 (5!) possible permutations in S5? Let’s consider the 1st case: 5 + 0, there will be 24 possible permutations can be done. Since permutation (1, 2, 3, 4, 5) is one of them, we can find the others of 23 by fixing at least one elements in (1, 2, 3, 4, 5) and then permute the others. The simplest way of doing this is by fixing 1 and 2 and then varies the last 3 terms as shown below: (1, 2, 3, 4, 5) ⇒ we have 6 possible options for leading (1, 2, _, _, _) i.e. we permute 3, 4 and 5 and thus 3P3 or 3! = 6 We’ll continue with the case of (1, 3, 2, 4, 5) which also gives us 6 permutations by permuting the last three terms. Repeat the process for leading (1, 4, _, _, _) and (1, 5, _, _, _), you will get all 4 possible pairs of 6 permutations of length 5 cycle. Hence, you have 6 x 4 = 24 possible permutations of length 5 cycle. 1
Note: Every permutation of a finite set is the identity, a single cycle or a product of disjoint cycles. The formula used to find number k-cycles is only applicable to the case of single cycle of length k. Do not ever try to apply it for the cases involving product of disjoint cycles and identity. There will always only be one identity in Sn
∀ n > 1 instead of
n! = n . It is because (1) = (2) = (3) = (4) =….(n-1) = (n) (1)(n − 1)!
which are finally considered to be the same as (1).
Case 2: 4 + 1 Suppose we do the same thing by permuting the last three terms in (1, 2, 3, 4)(5), i.e. (1, 2, 3, 4)(5). We’ll again obtain 6 possible permutations in the case of which element 5 is fixed in this cycle of length 4. How about the cases of (1, 2, 3, 5)(4), (1, 2, 4, 5)(3), (1, 3, 4, 5)(2) and (2, 3, 4, 5)(1)? [Writing down the fixed element at the back will be useful this time since this can help us to identify the trend easily]. From that, by considering S5 (n =5), we know there’ll always be one element is fixed (mapped back to itself) in the cycle of length 4. Thus, we know there are 5 possible pairs for cycle structure 4 + 1 to be concerned. Since we’ve obtained the 6 possible permutations in the 1st possible pair (i.e. 5 is fixed), hence there’ll be 6 permutations for each pair of cycle structure 4+1 by repeating the process of permuting the last 3 terms. If we’ve 5 pairs, it means that we’ve all 6 x 5 = 30 possible permutations for the case of 4+1 partition.
Case 3: 3 + 1 + 1 This is concerned with length-3 cycle as (1, 2, 3)(4)(5) = (1, 2, 3). This simply means that we permute 3 elements from 5 which are being listed, but it DOES NOT simply mean that 5P3 = 60 (why?). One way to find the 20 possible permutations is by referring to elements which are listed orderly in ascending sequence as what you’re used to apply when you’re dealing with the case n < 4. 1, 2, 3, 4, 5 We choose the 1st three terms and permute only 2 of them (usually we fix the leading term, i.e. 1). We know there’s only 2 ways to do this i.e. (1, 2, 3) and (1, 3, 2). By repeating the process of choosing (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5) and so on (where 2 and 3 turns out to be the leading term later). This process will be ended up with the permutation (3, 4, 5) and (3, 5, 4) [Check it out!]. There are all 20 permutations as what we expected to be. Hence, as you move along the line at which the elements are being stated, there’ll be 10 permutations can be obtained from (1, 2, 3), (1, 2, 4) until (3, 4, 5). Since we can only permute 2 elements from each of this permutation, they are altogether 10 x 2 = 20 permutations obtained finally. [Tips: Don’t ever look backward from the sequence of elements! For example, we do not worry about (5, 3, 2) or (5, 2, 3) when we’re doing the permutation of (2, 3, 5). The one we’d do is to permute the 2nd and the 3rd elements (3 and 5 respectively) but without changes the leading term, i.e. 2. In addition, the most surprising thing is that you can stop selecting the elements when the leading term is 3 [why we do not need to perform the cycles (4, _, _) or (5, _, _)?].
Case 4: 3 + 2 There are both length-2 and length-3 cycles to be concerned this time; everything has to be handled carefully as the repetition cases might occur without being realized. We do the same thing as previously done: fix some elements and permute the others. Since (a, b) will always be the same as (b, a), hence we do not need to permute elements in cycle of length-2. Instead, we focus on length-3 cycle by fixing the foremost element “1” in permutation (1, 2, 3)(4, 5) as suggested, then permute 2 and 3. Surprisingly, the process of permuting the elements is somehow exactly the same as what we do in length-3 cycle. Believe it or not, you’ll obtained the answer for this case exactly the same as in case 3, with the only difference is the way of writing down the element in cycle of length 2 as (a, b) rather than (a)(b). Hence, we have 20 permutations for the case of partition 3 + 2. [Alternative Method for the case 3 and 4: 4P2 + 3P2 + 2P2 = 20 permutations]. Try it! Case 5: 2 + 2 + 1 Since they are product of 2 disjoint cycles with the same length, i.e. 2, we expect that the repetition will certainly occur in this case [For example, (1, 2)(3, 4)(5) = (4, 3)(1, 2)(5)]. However, again, we make use of the fixed element to help us to identify the trend of what it’s supposed to be happening. Suppose we leave 5 be the fixed element and change the 2nd element in the first cycle from 2 to 4, we’ll only have 3 possible permutations obtained [Check!]. By repeatedly taking different fixed element (other than 5) to guide us in obtaining the result, we’ll spot the trend easily by figuring out the fact that: “for each permutation of partition 2 + 2 + 1 with one possible element which is fixed at the back, there are 3 possible permutations can be obtained”. Since the fixed elements can be 1, 2, 3, 4, or 5, thus there’ll be altogether 5 x 3 = 15 possible permutations can be obtained. Case 6: 2 + 1 + 1 + 1 I’ll leave this case for you as it’s been easy to be worked out as what you’d do for the symmetric group on n < 4. By permutation method, we’ve to permute 2 elements arbitrarily from the total 5 elements, i.e. 5P2 = 20. However, since they are all single cycles of length-2 with the fact that (a, b) = (b, a), thus, the total 20 we found earlier have to be divided by 2 because half of them from the 20 permutation are being the same. Hence, we’ll have 20/2 = 10 permutations for this case. Case 7: 1 + 1 + 1 + 1 + 1 (1)(2)(3)(4)(5) = (1) = (2) = (3) = (4) = (5) = (1) = ε Thus, by summing up all the number of permutations in 7 cases above, we have 24 + 30 + 20 + 20 + 15 + 10 + 1 = 120 = 5! permutations in S5. * Final thought: What can you conclude about A5 and what’s the unique feature can be observed from S2 to S5 about the number of odd and even permutations?
