title: The expected number of inversions--From Introduction to Algorithms by Cormen
body: <p>Let A[1 .. n] be an array of n <code>distinct</code> numbers. If i &lt; j and A[i] > A[j], then the pair (i, j) is called an inversion of A. (See Problem 2-4 for more on inversions.) Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Use indicator random variables to compute the expected number of inversions.</p>
  
  <hr>
  
  <p>The problem is from exercise 5.2-5 in <em>Introduction to Algorithms</em> by Cormen. Here is my recursive solution:</p>
  
  <blockquote>
    <p>Suppose x(i) is the number of inversions in a[1..i], and E(i) is the expected value of x(i), then E(i+1) can be computed as following:<br>
    Image we have <code>i+1</code> positions to place all the numbers,  if we place <em>i+1</em> on the first position, then x(i+1) = i + x(i); if we place <em>i+1</em> on the second position, then x(i+1) = i-1 + x(i),..., so E(i+1) = 1/(i+1)* sum(k) + E(i), where k = [0,i]. Finally we get E(i+1) = i/2 + E(i).<br>
    Because we know that E(2) = 0.5, so recursively we get: E(n) = (n-1 + n-2 + ... + 2)/2 + 0.5 = n* (n-1)/4.</p>
  </blockquote>
  
  <hr>
  
  <p>Although the deduction above seems to be right, but I am still not very sure of that. So I share it here. </p>
  
  <p>If there is something wrong, please correct me.</p>