Inversion of permutations (Algorithms problem)

[SpiffyEh]

Homework Statement

An inversion of a permutation is a pair of elements that are out of order.
(a) Show that a permutation of n items has at most n(n−1)/2 inversions. Which
permutation(s) have exactly n(n − 1)/2 inversions?
(b) Let P be a permutation and Pr be the reversal of this permutation. Show
that P and Pr have a total of exactly n(n − 1)/2 inversions.
(c) Use the previous result to argue that the

Homework Equations

The Attempt at a Solution

I honestly have no idea where to even start with this problem. I don't completely understand it. can someone please guide me through it?

 

[KataKoniK]

Hello, thank you for your question. I will try my best to guide you through this problem.

(a) To show that a permutation of n items has at most n(n−1)/2 inversions, we can think about the worst case scenario. Let's say we have a permutation of n items, and all the elements are in reverse order. In this case, there will be n-1 inversions between the first and second element, n-2 inversions between the second and third element, and so on until there are 0 inversions between the second to last and last element. This would result in a total of (n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2 inversions. This is the maximum number of inversions that can occur in a permutation of n items.

To find a permutation that has exactly n(n−1)/2 inversions, we can use the example above where all the elements are in reverse order.

(b) To show that P and Pr have a total of exactly n(n − 1)/2 inversions, we can use the same logic as in part (a). If we reverse a permutation, the number of inversions will remain the same, but the order of the elements will be reversed. Therefore, the total number of inversions between P and Pr will be the same as the total number of inversions between the initial permutation and the reverse permutation. As shown in part (a), this is equal to n(n-1)/2.

(c) Using the result from part (b), we can argue that any permutation and its reverse will have the same number of inversions, which is n(n-1)/2. Therefore, we can say that for any permutation, the number of inversions will be at most n(n-1)/2. This is because even if the permutation is not in reverse order, the maximum number of inversions will still be n(n-1)/2.

I hope this helps you understand the problem better. Please let me know if you have any further questions.