In a permutation a1.....an of n distinct integers, an inversion is a pair (ai,…
GATE · 2003 · CS
In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1.....n ?
- A.
n(n - 1)/2
- B.
n(n - 1)/4
- C.
n(n + 1)/4
- D.
2n[log2 n]
Attempted by 48 students.
Sign up free to check your answer
Sign up freeLoading lesson…