For one of my homework questions we were given a 16-puzzle and we had to find out if it is solvable; and then solve it. My 16-puzzle is
\begin{array}{|c|c|c|c|}\hline 1&2&3&4\\\hline 5&6& &11\\\hline 10&9&7&8\\\hline 13&14&15&12 \\\hline \end{array}
Now, I know all about parity of permutations and all that. I find the number of inversions. That'll be
$$ 0 + 0 + 0 + 0 + 0 + 0 + 4 + 3 + 2 + 0 + 0 + 1 + 1 + 1 +0 = 12 $$
Even. So this 16-puzzle can be solved. My confusion comes from when I slide my 7 tile upwards creating \begin{array}{|c|c|c|c|}\hline 1&2&3&4\\\hline 5&6&7&11\\\hline 10&9& &8\\\hline 13&14&15&12\\\hline \end{array}
Now if I check the number of inversions I get
$$ 0+0+0+0+0+0+0+3+2+1+0+1+1+1+0=9 $$
Which is odd. That shouldn't be possible though. Did I do something wrong?
As explained at Wikipedia, you forgot to add the taxicab distance of the empty square from the lower right corner to the parity of the permuation. It's not suprising that the permutation changes parity when you apply a transposition, as a transposition has negative parity. You also forgot to add the number of inversions for the empty square (fictitiously labeled $16$); it just so happens that your move doesn't change the parity of that number.