Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Maximum number of transpositions required to make all permutations.

  1. Feb 14, 2012 #1

    1. The problem statement, all variables and given/known data
    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?

    2. Relevant equations
    All permutations are a product of tranpostions.

    3. 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?
  2. jcsd
  3. Feb 14, 2012 #2
    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...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook