Maximum number of transpositions required to make all permutations.

[Anoonumos]

Hi,

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?

 

[xaos]

there are a maximum of N! ways of arranging N letters, if they want a number smaller than that I'm not sure how to find it. you might be able to prove by induction that the set of all adjacent transpositions form a basis. intuitively, all you need to show is that the Nth letter can be moved to normal position given that all the N-1st letters can be moved to normal position...