53 votes

In a permutation \(a_1 ... a_n\), of n distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\).

If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of \(1. . . n\)?

- \(\frac{n(n-1)}{2}\)
- \(\frac{n(n-1)}{4}\)
- \(\frac{n(n+1)}{4}\)
- \(2n[\log_2n]\)

0 votes

**Ans -B **

Let \(X_{ij}\) be an indicator random variable s.t. $$X_{ij} = \begin{cases} 0 &\mbox{if } (a_i,a_j) \text {not inverted} \\ 1 & \mbox{if } otherwise. \end{cases}$$ Let random variable \(X\) denotes total number of inversions. So clearly \(X=\sum\limits_{\substack{i,j \\ i<j}}X_{ij}\). Note that their are \(^n\mathrm{C}_2\) terms in summation, because there are total \(^n\mathrm{C}_2\) pairs, and each pair is either inverted or not.

So now we want to find \(E(X)\). Now \(E(X)=\sum\limits_{\substack{i,j \\ i<j}}E(X_{ij})\). But \(E(X_{ij}) = \frac{1}{2}\), because for any pair, probability of inversion is same as of not inversion.

So \(E(X) = \frac{^n\mathrm{C}_2}{2} = \frac{n(n-1)}{4}\).

So option **(B)** is correct.