Inversion 2

Probability Level 2

In a permutation $a_{1}, a_2, \ldots, 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,2,3,\ldots,n$ ?

\frac{n(n-1)}{4}

\frac{n(n+1)}{2}

\frac{n(n-1)}{6}

\frac{n(n-1)}{2}

1 solution

Abhishek Sinha
Mar 13, 2016

There are $\binom{n}{2}$ pairs and each pair is inverted with probability $\frac{1}{2}$ . Hence the expected number of inversion is $\frac{1}{2}\binom{n}{2}=\frac{n(n-1)}{4}.$

Inversion 2

1 solution

0 pending reports