Let A[1 .. n] be an array of n distinct numbers. If i <> A[j], then the pair (i, j) is called an inversion of A. Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Compute the expected number of inversions.
Is the following solution correct -
ReplyDeleteLet Xij be the event that when two distinct random numbers i and j are selected between 1 and n and i <> a[j].
Probability of occurence of Xij = 1-1/n
We need to sum this probability over i and j from 1 to n and i<>j
Does this solution work?