=+let X„(w) be the number of smaller elements (between 1 and k - 1) lying to the right of k in the bottom row. The sum S ,, = X ... + . +X ,.,, is the total number of inversions-the number of pairs appearing in the bottom row in reverse order of size. For the permutation in Example 5.6 the values of X11 ,..., X77 are 0, 0, 0, 2, 4, 2, 4, and S, = 12. Show that X„,), ..., X ,, are independent and P[X ,. = i] = k-1 for 0 ≤i < k. Calculate E[S„] and Var[S ,, ].

Show that S ,, is likely to be near n2 / 4.