Transposition/Inversions/Number/Exercise/Solution

We determine for every pair $(i,j)$, $i<j$, whether it is an inversion. For $i<k$ we do not have an inversion, since

$\tau (i)=i<min\{k,j\}=\tau (j).$

The same holds in case $j>\ell$. So suppose that

$k\le i<j\le \ell .$

For

$k<i<j<\ell ,$

we have $\tau (i)=i<j=\tau (j)$, and there is no inversion. For

$k=i<j<\ell ,$

we have an inversion, due to

$\tau (k)=\ell >j=\tau (j).$

In the same way we have for

$k<i<j=\ell$

an inversion. Moreover, $k<\ell$ is an inversion. This yields altogether

$(\ell -k-1)+(\ell -k-1)+1=2\ell -2k-1$

inversions.

To the exercise