An inversion in a permutation of the integers 1 to n is a pair of numbers (not necessarily adjacent) such that the larger number is listed first. For example, in the permutation 4, 2, 3, 1, the inverted pairs are (4, 2), (4, 3), (4, 1) (2, 1) and (3, 1). By listing out all 24 permutations and counting the number of inversions in each (if you are lazy you can write a program to do this and attach the code as a separate file), calculate the expected number of inversions in a random permutation of 1, 2, 3 and 4. Then, using this result, posit a guess for the general result, in terms of n for permutations of 1, 2, 3, …, n. Try to prove this guess via a route that uses less calculation, but looks at an arbitrary pair of indexes into the permutation, say i and j with i < j and counts how many permutations for which this pair is "in order" and that this pair is in inverted.