Maximum number of transpositions required to make all permutations.

In summary, the conversation is discussing whether all permutations of the letters A, B, C, and D can be achieved through multiplications of transpositions, and what the maximum number of multiplications needed would be in both cases. The first part can be proven by creating all transpositions and applying the relevant equation, but the maximum number of multiplications needed is still unknown. It is suggested that there are a maximum of N! ways of arranging N letters, and that a proof by induction may be possible.
  • #1
Anoonumos
16
0
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?
 
Physics news on Phys.org
  • #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...
 

Related to Maximum number of transpositions required to make all permutations.

What is the maximum number of transpositions required to make all permutations?

The maximum number of transpositions required to make all permutations is equal to half of the number of elements in the permutation. For example, if there are 6 elements in the permutation, the maximum number of transpositions needed is 3.

How is the maximum number of transpositions calculated?

The maximum number of transpositions is calculated using the formula n/2, where n is the number of elements in the permutation. This is because each transposition can swap two elements, and to make all permutations, we need to swap half of the elements.

What is the significance of the maximum number of transpositions?

The maximum number of transpositions is important in understanding the complexity of making all permutations. It gives us an upper bound on the number of steps required to reach all possible permutations.

Can the maximum number of transpositions be exceeded?

No, the maximum number of transpositions cannot be exceeded. This is because each transposition can only swap two elements, and making all permutations requires swapping half of the elements. Therefore, the maximum number of transpositions is the limit.

How can the maximum number of transpositions be used in practical applications?

The maximum number of transpositions can be used in the field of combinatorics to calculate the number of possible combinations for a given set of elements. It can also be used in sorting algorithms to determine the maximum number of steps needed to sort a list of elements using transpositions.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Math Proof Training and Practice
Replies
23
Views
642
  • Calculus and Beyond Homework Help
Replies
7
Views
534
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • General Math
Replies
1
Views
735
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
6K
Back
Top