1

I'm given the permutation in $S_8$
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 7 & 8 & 4 & 1 & 2 &6 & 3 & 5\end{pmatrix}$$ and I've decomposed it into the transposition $$\sigma = (17)(73)(34)(28)(85)$$ and so $\sigma$ is an odd permutation. However, when I calculate the inversion number, I have $I(\sigma) = 16 = 0 (\mod 2)$. But shouldn't the inversion count be odd for an odd permutation?

Twenty-six colours
  • 1,881
  • 1
    Is it possible, dare I suggest, that you made an error in your calculation for $I(\sigma)$? – Angina Seng May 14 '17 at 06:52
  • Definitely. Apparently I miscounted the inversion count even though I tried it about 10 times rewriting it. Thanks. Actually, could I ask what the relationship between the inversion count and the number of transpositions is? I can't really think intuitively about it – Twenty-six colours May 14 '17 at 06:56
  • Does the inversion count "count" the amount of swaps we do with the original sequence (the first row) to obtain the bottom row? – Twenty-six colours May 14 '17 at 06:57
  • Not if you include "swaps" like $(1\ 7)$. If you write it as a product of swaps of the form $(j\ j+1)$ in the most efficient way, the number of swaps will be the inversion number. – Angina Seng May 14 '17 at 06:59
  • Generally, would this be difficult to do? – Twenty-six colours May 14 '17 at 07:02
  • I would say that I'd rather let you count $I(\sigma)$ than do it myself. – Angina Seng May 14 '17 at 07:04
  • Double posted due to internet. I think $I(\sigma)$ is quite easy to calculate (just by counting in the bottom row), but I assume that the method of converting into a product of the form $(j j+1)$ is probably difficult – Twenty-six colours May 14 '17 at 07:11
  • I don't think converting it to a product of adjacent swaps is too hard, this is essentially just recording what bubble-sort will do on the permutation (or its inverse). However, the reverse permutation in $S_n$ has an inversion number of $\binom{n}{2} \approx n^2 /2$, and so writing large permutations as adjacent swaps may get very cumbersome. You can still count the number of inversions in only $O(n \log n)$ time, via a well-known algorithm, if you're interested. – Joppy May 14 '17 at 07:26
  • @Joppy Appreciated. Unfortunately, I have barely any experience with algorithms. Also, how would you find the minimum amount of swaps (is this the inversion number?) to get to a particular sequence?
    Edit: Wouldn't the inversion no. of the reverse permutation actually be $n-1 + n-2 + ... + 1$?     – Twenty-six colours May 14 '17 at 07:53
  • I think that there would be a total of $\frac{4!}{2!}$ permutations which consist of even swaps for $S_4$, just by seeing that a the amount of permutations which displaces every single number would be $\frac{4!}{1!}$ – Twenty-six colours May 14 '17 at 07:54

0 Answers0