My Math Forum  

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

Linear Algebra Linear Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
June 29th, 2010, 10: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
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  
Reply

  My Math Forum > College Math Forum > Linear Algebra

Tags
permutations



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 © 2017 My Math Forum. All rights reserved.