How can I figure out how many inversions of permutations? I have the answers but I don't know how to get there.
Questions:
(1,2,3,4) has 0, (4,1,3,2) has 4 , and (4,3,2,1) has 6.
An inversion in a permutation is a pair of numbers such that the larger number appears to the left of the smaller one in the permutation.
In (4,1,3,2) 4 is to the left of 1,2,3 and 3 is to the left of 2 -- 4 inversions
the others should now be clear.
Thank you!
To determine the number of inversions in a permutation, you can follow these steps:
1. Start by identifying the permutation you want to analyze. Let's take the permutation (4,1,3,2) as an example.
2. Write down the numbers 1, 2, 3, 4 vertically as individual rows.
```
1
2
3
4
```
3. Go through each number in the permutation from left to right.
- Start with the first number, which is 4. Count the number of smaller numbers that come after it. In this case, there are 3 smaller numbers: 1, 3, and 2. Write down the count above the number 4.
```
3
1 3 2
4
```
- Move on to the next number, which is 1. There are no smaller numbers that come after it, so the count is 0.
```
3
1 3 2
4 0
```
- Continue this process for the remaining numbers in the permutation.
```
3
1 3 2
4 0 2
```
4. Lastly, add up the counts you wrote above each number. In this case, the sum is 3 + 0 + 2 = 5. This is the number of inversions in the permutation (4,1,3,2).
Using this method, you can determine the number of inversions for any permutation. Apply the steps to the permutations (1,2,3,4) and (4,3,2,1) to confirm that they have 0 and 6 inversions, respectively.