## Tuesday, February 23, 2010

### Inversions

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.

#### 1 comment:

1. Is the following solution correct -

Let 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?