Let \(A[1..n]\) be an array of \(n\) distinct numbers. If \(i < j\) and \(A[i] > A[j]\), then the pair \((i, j)\) is called an inversion of \(A\). (See Problem 2-4 for more on inversions.) Suppose that the elements of \(A\) form a uniformrandom permutation of \(\{1, 2, \dots, n\}\). Use indicator random variables to compute the expected number of inversions.

Let \(X_{i, j}\) be the indicator random variable for the event that \((i, j)\) is an inversion of \(A\). We have \(Pr\{X_{i, j}\} = \frac{1}{2}\) because it is equally likely that two distinct integers are ordered in increasing or decreasing order. This also means that \(E[X_{i, j}] = \frac{1}{2}\).

Next, let \(X\) be the random variable that represents the umber of inversions in array \(A\): \(X = \sum\limits_{i = 1}^{n-1} \sum\limits_{j = i + 1}^{n} X_{i, j}\). The expected value of this random variable is

\[\begin{split} E[X] &= E \left[ \sum\limits_{i = 1}^{n-1} \sum\limits_{j = i + 1}^{n} X_{i, j} \right] \\ &= \sum\limits_{i = 1}^{n-1} \sum\limits_{j = i + 1}^{n} E[ X_{i, j}] \\ &= \sum\limits_{i = 1}^{n-1} \sum\limits_{j = i + 1}^{n} \frac{1}{2} \\ &= {n \choose 2} \frac{1}{2} \\ &= \frac{n(n-1)}{2} \cdot \frac{1}{2} \\ &= \frac{n(n-1)}{4} \\ \end{split}\]