Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Permutations of a given set with exact inversions

  1. May 23, 2012 #1
    1. The problem statement, all variables and given/known data

    How many permutations of S = {1,2,3,4,5,6} have exactly 15 inversions, 14 inversions, and 13 inversions? I think I got the first one, but not sure how to go about finding the rest

    2. Relevant equations
    There are 6 digits so we'll name them: a1 a2 a3 a4 a5 a6 after 1 2 3 4 5 6 from the problem.

    3. The attempt at a solution
    Make a table:a1 a2 a3 a4 a5 a6
    0 0 0 0 0 0
    1 1 1 1 1
    2 2 2 2
    3 3 3
    4 4

    The first column of the table is derived from the first digit a1 = 1, since there is no integer larger than 1 to the left of it, so 0 is the null space...However, if a6 = 1 then there would be 5 integers to the left of 1 that would be larger than it. The rest of this logic is used to complete the table.

    The last digits in the table are 543210, and they add up to 15. So, (ai + 1) to each digit to get 654321, which has exactly 15 inversions. I think it's the only one, but I'm not sure how to prove that. Also, I'm not sure how to figure out how many permutations have exactly 13 and 14 inversions.
    Last edited: May 23, 2012
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted