Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

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

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

share|improve this answer
1  
Thanks, I may add this site was also good in explaining it to me - kr.cs.ait.ac.th/~radok/math/mat3/m14.htm –  eWizardII Oct 2 '11 at 0:55
    
@eWizardII Yeah Its good –  Ramana Venkata Oct 2 '11 at 1:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.