Known, that number of inversions is $k$ in permutation:
$$\begin{pmatrix}
1& …& n& \\
a_1& …& a_n&
\end{pmatrix}$$
Find number of inversions in permutation (let's call it "reverse"):
$$\begin{pmatrix}
1& …& n& \\
a_n& …& a_1&
\end{pmatrix}
$$
First, max number of inversions is $\frac{n(n-1)}{2}$. Then we can see if we get permutation with $0$ inversions than "reverse" permutation for it will have $\frac{n(n-1)}{2}$.
I can guess that for $\sigma(i)$, $\sigma(n-i+1)$ sum of inversions in them is $\frac{n(n-1)}{2}$. Thus, answer will be $\frac{n(n-1)}{2}-k$
Please help me to prove that.
Best Answer
Supposing you define an inversion of $a$ as a pair of indices $i<j$ such that $a_i>a_j$, you can easily show that $(i,j)$ with $i<j$ is an inversion of $a$ if and only if $(n+1-j,n+1-i)$ is not an inversion of the reverse of $a$. The pair of values at those indices are the same in both cases, so if you define an inversion to be the (inverted) pair of values $\{a_i,a_j\}$ then it is even easier: the set of inversions of the reverse of $a$ is the complement of the set of inversions of$~a$.