71. Let ax < a2 < < an denote a set of numbers,

71. Let ax < a2 < · · · < an denote a set of ç numbers, and consider any permutation of these numbers. We say that there is an inversion of tff and üj in the permutation if / < j and aj precedes a{. 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 al9a2i >··,áç—in the sense that each of the ç ! permutations is equally likely to be chosen—and let TV denote the number of inversions in this permutation. Also, let Ni = number of k: k < /, #f precedes ak in the permutation and note that Í = Ó"=é

(i) Show that Nx, ..., Nn are independent random variables.

(ii) What is the distribution of TV,?

(iii) Compute E[N] and Var(7V).