# Inversion Problem

I have a problem that says:

Find the number of inversions in each of the following permutations of S = {1,2,3,4,5}:

(a) 52134 (b) 45213 (c) 42135

In the text it doesn't do that great of a job of explaining how you find inversions, I assumed (a) was 5 inversions because the numbers are in five different positions from the orginal S. However in (b) the answer is 7, but I can't figure out why. Is there a general line of attack I should take with these types of problems?

Thanks,

-

Count one inversion for each time a number precedes a smaller number. Take $45213$, for example: $4$ precedes $2,1$, and $3$, so that’s $3$ inversions. $5$ also precedes $2,1$, and $3$; that’s $3$ more inversions, for a total of $6$. Finally, $2$ precedes $1$, and that’s your $7$-th inversion.

In $52134$ there are $4$ inversions involving the $5$, and the fifth inversion is $21$.

I’ll let you try (c) now on your own.

-
Thanks for the explanation, for (c) I got 4 which was correct using the method you described. –  eWizardII Oct 2 '11 at 0:55