Difference between revisions of "TADM2E 4.19"

Latest revision as of 00:52, 1 August 2020

1) Starting from left to right, the number of inversions

 for 1st number is n-1
 for 2nd number is n-2
 ...
 ..
 ....nth number is n-n = 0

Total number of inversions is the sum of all of the above sum of integers from 0 to n - 1 = n(n-1)/2

2. We know that the maximum num of inversions is n(n-1)/2.

 Consider a permutation P.
 a1 a2 ai..ak...aj..am.... an-1 an

 ai and aj are out of order
 ak and am are in order.  
 For Pr,
 ai and aj will get reversed, and will become in order.
 ak and am will get reversed and will become out of order.

 Every In order pair becomes an inversion.
 And every inversion becomes corrected.
  

If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs. Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.

Summing up the inversions in P and Pr we get n(n-1)/2

3. To calculate the max inversions in part 1, every ith position had n - i inversions. i.e following a number, all other numbers will be out of order. In the average case, we can argue that about 1/2 of the number will be out of order....

 for 1st number  (n-1)/2
 for 2nd number   (n-2)/2
 ...
 ..
 ....nth number is (n-n)/2 = 0

Total number of inversions is the sum of all of the above sum of integers from 0 to (n - 1)/2 = n(n-1)/4...

Alternative solution to 3: Any permutation of any set is equally likely. Previous result shows that every permutation has its reversal. If we put pair up every permutation of a set with its reversal, they combine to n(n-1)/2 inversions. There are half as much pairs as there are permutations so the result is n(n-1)/2 * 1/2 = n(n-1)/4