Permutations on 3n Terms and Conditions: Calculating Total Possibilities

[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 don't know how to use it to calculate the number of permutations, any tips, hints?

 

[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?

 

[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 haven't solved it correctly.

 

[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?

 

[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!

 

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

 

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

 

[matt grime]

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

 

[MathematicalPhysicist]

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