# 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 and $$A[i]>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 $$<1,...,n>$$. 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 < 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$$.