1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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)