62. Let a1 < a2 < ··· < an denote a set of n numbers, and consider any permutation of these numbers. We say that there is an inversion of ai and a j in the permutation if i < j and a j precedes ai . For instance the permutation 4, 2, 1, 5, 3 has 5 inversions—(4, 2), (4, 1), (4, 3), (2, 1), (5, 3). Consider now a random permutation of a1, a2,..., an—in the sense that each of the n! permutations is equally likely to be chosen—and let N denote the number of inversions in this permutation.

Also, let Ni = number of k : k < i, ai precedes ak in the permutation and note that N = n i=1 Ni .

(a) Show that N1,..., Nn are independent random variables.

(b) What is the distribution of Ni ?

(c) Compute E[N] and Var(N).