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

Some permutations.

  1. Jun 30, 2007 #1
    I need to find:
    1. let n be a natural number compute the number of permutations s:{1,...,3n}->{1,...,3n} on 3n terms that satisfies s(n)<s(2n)<s(3n).
    2. compute the number of permutations s:{1,...,n}->{1,..,n} that satisfy: for every i,j in 1,..,n |s(k)-s(j)|<=|k-j|
    for the first question i found that the answer is first we calculate the permutations where every member in the set gets permuted except for n,2n,3n which is (3n-3)! now for the other three we choose the biggest to be s(3n) and so on, so the answer is (3n-3)!/
    now for second question, i got that in order to satsfy this condition the follow should be met:
    either 1<=s(k)<=k and j<=s(j)<=n or k<=s(k)<=n and 1<=s(j)<=j
    i think that this is correct but i dont know how to use it to calculate the number of permutations, any tips, hints?
  2. jcsd
  3. Jun 30, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    What's hard about 1? How many choices for where to send n, then 2n, then 3n? I only as because you dont' appear to have finished a sentence (the bit that states the answer is (3n-3)!/).

    Have you attempted to work out some examples for small n for the second one?
  4. Jun 30, 2007 #3
    my final answer for the first question is (3n-3)!, cause after we choose the others, the other three slots for n and 2n and 3n are determined by the choice of the others.

    for the second, i havent, i thought i could answer it without executing an example for, but i guess i need to check it out, anyway do you have any hints regarding the second question, or even the first question, if i havent solved it correctly.
  5. Jun 30, 2007 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Again, try some examples. And 1 is not correct (I thought you intended to divide by something, which would be even more incorrect). There are certainly (3n-3)! permutations of the other 3n-3 numbers, but, whilst that is needed, it certainly isn't the answer. For example, if I wanted to send n,2n,3n to themselves, then there are clearly (3n-3)! permutations that do that alone.

    The reason I suggest examples for the second one is that it really will help you with the general answer, I believe. If you don't want to think of examples, then just think in general.

    Suppose I send 1 to r, then where must I send 2 to? And then 3?
    Last edited: Jun 30, 2007
  6. Jun 30, 2007 #5
    if you send 1 to r, then bacause s(1)=r and |r-s(2)|<=|1-2|=1 so s(2) must be r-1, |r-s(3)|<=2 so s(3) cannot be r-1 so it must be r-2 and so on.
    so if i choose the first term that goes to 1<=r<=n, then up to r every term goes to be r-k for 1<=k<=r-1 and |s(r)-r|<=|r-1| i.e now we are adjusting from r up to n the permutations of n,n-1,n-2,...,r+1.

    examples, ah?! ok. (-:
    what about the first question?
    i mean the number of permutations as you said for n,2n,3n to stay as they are is (3n-3)!, so the answer should be plus this.
    ok if s(2n) and s(3n) stay the same, but s(n) lies between 1 and 2n (not including 2n, then there are (2n-1)! to choose s(n) times (n-1)!, now if s(n) and s(3n) stay the same, then s(2n) can be between n+1 up to 3n-1 i.e (2n-1)! this times n!.
    well, i don't think it is going anywhere... bloody hell!!!
  7. Jun 30, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    1. Where can I send n to? Now how many places are left over to send 2n to? Then 3n? Clearly you can't send n to 3n-1 or 3n-2, but anywhere else will do....

    2. Why, if I send 1 to r must I send 2 to r-1? Is r+1 not also distance one from r? I don't get the impression from what you wrote that you actually now have the answer.
  8. Jul 1, 2007 #7
    1. so we have for n 3n-1 places to send if we first decide to permute n, if we first try to permute 2n, then we have from 2 to 3n-1 i.e, 3n-2 ways to permute 2n, for 3n certainly it cannot be 1 or 2, so we have 3n-2 places to send it, so the total answer should be a sum of the above, right?

    for the second one, I'll rethink it, perhaps tommorrow with a fresh start I'll succeed.
    thanks matt.
  9. Jul 1, 2007 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    No. Take n=1, if I send 1 to 2, then I can't possibly satisfactorily do anything with 2 and 3.
  10. Jul 2, 2007 #9
    sorry, it should be, we have 3n-2 places for n to go.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Some permutations.
  1. Simple permutation (Replies: 2)

  2. Circular Permutation? (Replies: 4)

  3. Permutation question (Replies: 8)