June 29th, 2010, 11:11 PM  #1 
Member Joined: Feb 2009 Posts: 76 Thanks: 0  permutations
I am SO confused. I know how to find the number of permutations but not the number of inversions. It says in order to find the number of inversions, you must find two adjacent pairs (i,j) in the opposite order: i < j Okay so in a permuations of S = {1,2,3,4,5} such that permutation ? = 52134. So, I have (2,5), (1,2 ), (1,3), (3,4). But the answer says there are 5. Also, permutation ? = 45213 has 7 inversions Also I looked at wikipedia and it gave an example: permutation ? = 23154 has three inversions: (1,3), (2,3), (4,5), for the pairs of entries (2,1), (3,1), (5,4). > why is there a (2,3) but not a (3,2) or is (2,3) = (3,2)? > Why can (1,5) be there? Arent they adjacent and it's i < j ? I am so confused T_T 
June 30th, 2010, 12:21 AM  #2 
Senior Member Joined: Jun 2010 Posts: 618 Thanks: 0  Re: permutations
Hi remeday86. I guess my inner nerd is really out on the prowl tonight! Here's my trick for counting inversions. You take the permutation you are looking at, and you want to write it as ? = (12345), where I'm taking your cue, and using a permutation on five symbols for my examples. So, suppose, like in your first example, that you have the permutation ? = (52134). Look first at the 1, and see how many places you have to move it to the left to get it to the leftmost place, as in ?. In this case, that's 2 places. So, you take the 1, and put it in front of the 5, and you tally up that you moved 2 spaces, so now you have ?(1) = (15234). Next, look at the number 2 in ?(1). How many places do you have to move it to get to the second place from the left? Well, just 1 place. So, move it there, forming ?(2) = (12534), and add the 1 to your tally, which is now 2+1=3. Next, look at 3 in ?(2). To move it into the third place from the left, you have to move it just 1 place again, so do that, forming ?(3) = (12354), and add 1 to the tally, which is now at 3+1=4. Finally, look at 4 in ?(3), and see how many places you have to move it to get it into the fourth place from the left, which is clearly just 1 place again. Do that, forming ?(4) = (12345) = ?, and add 1 to the tally which is finally 4+1=5, the number of inversions. You can and should confirm that this method will give you the correct answers for the other permutations. Also, try and see how this fits in with the definitions you have read. Best of luck! 

Tags 
permutations 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Permutations  MRWhy  Abstract Algebra  4  May 30th, 2011 09:27 PM 
Even and Odd Permutations  HairOnABiscuit  Abstract Algebra  1  December 13th, 2010 07:03 AM 
Permutations?  CalculateThis  Algebra  1  March 23rd, 2009 05:00 PM 
Permutations  gretchen  Advanced Statistics  1  February 12th, 2007 03:39 AM 
Permutations  MRWhy  Linear Algebra  1  December 31st, 1969 04:00 PM 