# Inversion of permutations (Algorithms problem)

• SpiffyEh
In summary, we have shown that a permutation of n items has at most n(n−1)/2 inversions, and that any permutation and its reverse have a total of exactly n(n − 1)/2 inversions. This allows us to argue that the maximum number of inversions for any permutation is n(n-1)/2.
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

## 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?

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.

## 1. What is an inversion in a permutation?

An inversion in a permutation is when two elements in the permutation are in the wrong order. For example, in the permutation (3,1,2), the elements 3 and 1 are in the wrong order, creating one inversion.

## 2. What is the purpose of solving the inversion of permutations?

The inversion of permutations is a common problem in computer science and mathematics. It has various applications, such as in sorting algorithms, data compression, and cryptography.

## 3. How can I determine the number of inversions in a permutation?

The number of inversions in a permutation can be determined by counting the number of times a smaller element appears after a larger element. This can be done in O(n^2) time for a permutation of length n.

## 4. Is there an efficient algorithm for solving the inversion of permutations?

Yes, there are efficient algorithms for solving the inversion of permutations, such as the Merge Sort algorithm, which has a time complexity of O(n*log(n)). Other algorithms, such as the Fenwick Tree and Binary Indexed Tree, can also solve this problem in O(n*log(n)) time.

## 5. What are some real-life applications of solving the inversion of permutations?

The inversion of permutations has applications in various fields, including DNA sequencing, computer graphics, and analyzing financial data. It is also used in sorting algorithms, such as in the popular sorting algorithm, QuickSort.

• Engineering and Comp Sci Homework Help
Replies
2
Views
2K
• Math Proof Training and Practice
Replies
23
Views
1K
• Linear and Abstract Algebra
Replies
3
Views
2K
• Programming and Computer Science
Replies
8
Views
2K
• Linear and Abstract Algebra
Replies
28
Views
3K
• Programming and Computer Science
Replies
11
Views
871
• Precalculus Mathematics Homework Help
Replies
3
Views
2K
• General Math
Replies
1
Views
825
• Calculus and Beyond Homework Help
Replies
8
Views
1K
• Engineering and Comp Sci Homework Help
Replies
2
Views
3K