3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

Hints.

  • Think of some permutation $ι$ on $[n]$ so that for any permutation $σ$ on $[n]$, “$σ$-reverse” is $σι$.
  • An inversion of any permutation $σ$ on $[n]$ is a pair $(i,j)$ with $i < j$ such that $\frac{σ(i) - σ(j)}{i-j} < 0$.
  • For permutations $σ$, $τ$ on $[n]$ you have $\frac{(στ)(i) - (στ)(j)}{i - j} = \frac{σ(τ(i)) - σ(τ(j))}{τ(i) - τ(j)}·\frac{τ(i) - τ(j)}{i - j}$.
  • What does this imply for the inversions of $στ$ in terms of the inversions of $σ$ and $τ$?
  • How many inversions does $ι$ have?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.