Hi,(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.

**Physics Forums | Science Articles, Homework Help, Discussion**