Question

what is the maximum number of inversions that a permutation {1,..,n} can have? give the unique permutation with this many inversions. how many permutations have one fewer inversions than the minimum.

Answer 1

(a) maximum number of inversions that a permutation {1,..,n} can have

observe that the number of inversions cannot exceed the number of ways to choose two numbers (since each pair accounts for at most one inversion).

Hence, the number of inversions cannot exceed

(n2)=n(n?1)2

(b) give the unique permutation with this many inversions

Put everything in reverse order. So  {n,n-1 ,n-2,...........,3,2,1}

here every pair is inverted, and thus we have the full (n2)=n(n?1)2 inversions.

(C) permutations have one fewer inversions

Start with an arbitrary permutation with one less inversion. The only inversion must be between two adjacent elements.

• Suppose we had a<band the permutation will be like {...,b,...,a,...}
• If any element between b and a is less than b, then it creates another inversion with
  b. However, if it is greater than
  b, it must create an inversion with
  a.
• Any element in between can't be equal to
  b either.
• Hence, we can't have an element in between if there's only one inversion.

The permutations with one less inversion are then the n-1 permutations like {n,n-1,n-2,.....3,2,1}    with two adjacent elements swapped.