Some permutations.

1. Jun 30, 2007

MathematicalPhysicist

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. Jun 30, 2007

matt grime

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?

3. Jun 30, 2007

MathematicalPhysicist

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.

4. Jun 30, 2007

matt grime

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
5. Jun 30, 2007

MathematicalPhysicist

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.
so....

examples, ah?! ok. (-:
p.s
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!!!

6. Jun 30, 2007

matt grime

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.

7. Jul 1, 2007

MathematicalPhysicist

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.

8. Jul 1, 2007

matt grime

No. Take n=1, if I send 1 to 2, then I can't possibly satisfactorily do anything with 2 and 3.

9. Jul 2, 2007

MathematicalPhysicist

sorry, it should be, we have 3n-2 places for n to go.