For the permutation $\begin{pmatrix}5&2&4&3&6&1\\4&1&3&2&6&5\end{pmatrix}$, determine if it is even based on its inversions.
So here's my trouble; I've worked out the inversions for the top row as $(5,2),(5,4),(5,3),(5,1),(2,1),(4,3),(4,1),(6,1)$ for a total of $8$ and for the bottom row $(4,1),(4,2),(4,3),(3,2),(6,5)$ for a total of $5$.
This sums to 13 inversions for the permutation making it odd? My understanding is that I look at a number and see how many smaller numbers are to the right, each pair forms an inversion ie. $(5,2)$ from the top row.
Can anyone shed some light on this? Is there some double-counting rule I'm missing
Best Answer
Let's call your permutation $p$, so that $p = \begin{pmatrix}5&2&4&3&6&1\\4&1&3&2&6&5\end{pmatrix}$.
Using this definition of an inversion, I'm not quite sure why you've done the work you have done. We need to find pairs $(i, j)$, such that $i > j$ yet $p(i) < p(j)$.
I personally think it helps to write your permutation in the standard way, with the top row increasing:
$$p = \begin{pmatrix}1&2&3&4&5&6\\5&1&2&3&4&6\end{pmatrix}.$$
Now finding inversions amounts to counting pairs $(p(i), p(j))$ in the bottom row, where $p(i)$ appears to the left of $p(j)$, yet $p(i) > p(j)$. In that case, I'm only seeing $4$ inversions, not $13$.
I don't think you're missing any double counting rules or anything, but rather that only when the top row is $(1\ 2\ \ldots\ n)$ can we find inversions by looking for decreasing pairs in the bottom row.