My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum

LinkBack Thread Tools Display Modes
June 29th, 2010, 10:11 PM   #1
Joined: Feb 2009

Posts: 76
Thanks: 0


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
remeday86 is offline  
June 29th, 2010, 11:21 PM   #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!
 is offline  

  My Math Forum > College Math Forum > Linear Algebra


Thread Tools
Display Modes

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

Copyright © 2018 My Math Forum. All rights reserved.