GATE CS 2003 Q61 — Searching, Sorting, Hashing

To find the expected number of inversions in a randomly chosen permutation of $n$ distinct integers, we can use the linearity of expectation.

Let the permutation be $a_1, a_2, \dots, a_n$. An inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j$.

For any pair of indices $(i, j)$ with $1 \le i < j \le n$, let $X_{ij}$ be an indicator random variable defined as:

Since all permutations are equally likely, by symmetry, the probability that $a_i > a_j$ is exactly $\frac{1}{2}$ (as it is equally likely that $a_i > a_j$ or $a_i < a_j$).

Therefore, the expected value of each indicator variable is:

The total number of such pairs $(i, j)$ with $i < j$ is given by the combination $\binom{n}{2}$:

Let $X$ be the total number of inversions, so $X = \sum_{1 \le i < j \le n} X_{ij}$. By the linearity of expectation:

Thus, the expected number of inversions is $\dfrac{n(n-1)}{4}$.