3
$\begingroup$

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,

2 Answers 2

4

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.

2

http://mathworld.wolfram.com/PermutationInversion.html This webpage may help you in answering your question

  • 0
    @eWizardII Yeah Its good2011-10-02