Introduction to Algorithms (CLRS) Ex 5.2-5 solution The following is Ex 5.2-5 from Introduction to Algorithms (CLRS), 2nd Edition.


  Let $A[1...n]$ be an array of n distinct numbers. If $i&lt;j$ and $A[i]&gt;A[j]$, then the pair $(i, j)$ is called an inversion of $A$. Suppose that the elements of $A$ form a uniform random permutation of $&lt;1,...,n&gt;$. Use indicator random variables to compute the expected number of inversions.


The solution from https://walkccc.github.io/CLRS/Chap05/5.2/ says:


  Let $X_{ij}$ be an indicator random variable for the event where the pair $A[i], A[j]$ for $i &lt; j$ is inverted. We have $\Pr\{X_{ij} = 1\} = \frac{1}{2} $, because given two distinct random numbers, the probability that the first is bigger than the second is $\frac{1}{2}$. 


I would like to ask what is the rationale for $\Pr\{X_{ij} = 1\} = \frac{1}{2}$. I know that there can be only 2 outcomes, either be $X_{ij} =1$ or $X_{ij}=0$. Also, $\Pr\{X_{ij} = 1\}+\Pr\{X_{ij} = 0\}=1$.

After looking at the answer, it kind of make sense, but I would like to ask if there is a more "systematic" way to derive/justify this probability. Note that I am being very vague about the meaning of systematic because I simply would like to have a more reliable way of deriving this probability rather than only relying on intuition.
For a permutation $\pi$, let $\pi(i\;j)$ be the permutation obtained by switching the places of elements $i$ and $j$. Since $\pi(i\;j)(i\;j) = \pi$, we can partition the set of all permutations over the elements of $A$, into $n!/2$ pairs $\{\pi,\pi(i\;j)\}$.

Consider what happens to $A$ after permuting by $\pi$ and by $\pi(i\;j)$. In exactly one of these cases, the pair $(i,j)$ is an inversion. Therefore the pair $(i,j)$ is an inversion for exactly $n!/2$ of the permutations, i.e., with probability exactly $1/2$.