Question

Give the transpose of the permutation \([2,5,1,6,3,4],\) and find the number of inversions in both permutations. What is the total number of inversions?

Short answer

The transposed permutation of \( [2,5,1,6,3,4] \) is \( [4,3,6,1,5,2] \) and the total number of inversions in the two permutations is 17.

Step-by-step solution

Transpose the given permutation

The transpose of a permutation is found by writing it in reverse order. The transpose of the given permutation \( [2,5,1,6,3,4] \) thus becomes \( [4,3,6,1,5,2] \).

Count the inversions in the original permutation

In the permutation \( [2,5,1,6,3,4] \), the inversions are (2,1), (5,1), (5,3), (5,4), (6,1), (6,3), (6,4). So, there are 7 inversions.

Count the inversions in the transposed permutation

In the transposed permutation \( [4,3,6,1,5,2] \), the inversions are (4,3), (4,1), (4,2), (6,1), (6,5), (6,2), (3,1), (3,2), (5,1), (5,2). So, there are 10 inversions.

Calculate the total number of inversions

The total number of inversions in the permutation and its transposition is the sum of the number of inversions in each. Therefore, \(7 (from the original permutation) + 10 (from the transposed permutation) = 17 \).