- #1
Anoonumos
- 16
- 0
Hi,
Can all permutations of {A,B,C,D} be made by multiplications of transpositions (AB), (BC), (CD)? And by multiplications of transpostion (AB) and 4-cycle (ABCD)? What is the maximum number of multiplications needed in both cases?
All permutations are a product of tranpostions.
I can prove the first part for both cases by creating all transpostions and applying the relevant 'equation'. I'm not sure how to proof what the maximum number of multiplications is.
In case 1 it takes at most 3 multiplications to put the right letter on the first spot, at most another 2 to put the right letter on the second spot and at most 1 more to put the right letters on the last two spots, so 6 at most.
However, I don't know how to prove that there is a permutation which requires at least 6 (DCBA?).
I'm not sure about how to deal with case 2.
Can someone give me some help?
Homework Statement
Can all permutations of {A,B,C,D} be made by multiplications of transpositions (AB), (BC), (CD)? And by multiplications of transpostion (AB) and 4-cycle (ABCD)? What is the maximum number of multiplications needed in both cases?
Homework Equations
All permutations are a product of tranpostions.
The Attempt at a Solution
I can prove the first part for both cases by creating all transpostions and applying the relevant 'equation'. I'm not sure how to proof what the maximum number of multiplications is.
In case 1 it takes at most 3 multiplications to put the right letter on the first spot, at most another 2 to put the right letter on the second spot and at most 1 more to put the right letters on the last two spots, so 6 at most.
However, I don't know how to prove that there is a permutation which requires at least 6 (DCBA?).
I'm not sure about how to deal with case 2.
Can someone give me some help?