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 aj in the permutation if i < j and aj 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

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

(b) What is the distribution of Ni?

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