Let A be an array that stores n distinct numbers. The efficiency of some algorithms depends on how well the array is sorted. One measure for $$sortedness$$

is the number of inversions. An inversion is a pair $($i$,$ j$)$ in $\{0,...,$ n $1\}$

$2$

$,$

where i $<$ j but A$[$i$]>$ A$[$j$].$

Suppose A stores a random permutation of $\{1,...,$ n$\}.$ What is the expected

number of inversions?