Permutations on 3n Terms and Conditions: Calculating Total Possibilities

  • Context: Graduate 
  • Thread starter Thread starter MathematicalPhysicist
  • Start date Start date
  • Tags Tags
    Permutations
Click For Summary

Discussion Overview

The discussion revolves around calculating the number of permutations of terms in two distinct scenarios involving natural numbers. The first scenario involves permutations of the set {1,...,3n} that satisfy specific conditions regarding the positions of n, 2n, and 3n. The second scenario concerns permutations of the set {1,...,n} with constraints on the differences between the positions of elements.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant proposes that for the first question, the answer involves calculating permutations of 3n terms while fixing the positions of n, 2n, and 3n, suggesting the answer is (3n-3)!. However, this is challenged by others who indicate that this may not be the complete answer.
  • Another participant questions the reasoning behind the proposed solution and suggests that examples for small n could clarify the approach.
  • There is a discussion about the implications of sending specific numbers to certain positions and how that affects the remaining choices for other numbers in both questions.
  • One participant attempts to clarify the conditions for the second question, indicating that if a number is sent to a specific position, it restricts the possible positions for subsequent numbers based on defined distance constraints.
  • Another participant highlights the need to reconsider the approach for the second question and expresses uncertainty about the correctness of their reasoning.
  • There is a back-and-forth regarding the number of available positions for n, 2n, and 3n, with some participants correcting earlier statements about the number of choices available.

Areas of Agreement / Disagreement

Participants express differing views on the correctness of the proposed solutions, particularly regarding the first question. There is no consensus on the final answers, and multiple competing interpretations of the conditions and calculations remain evident throughout the discussion.

Contextual Notes

Some participants note that examples may help clarify the reasoning, particularly for the second question, but no specific examples are provided in the discussion. There are also indications of confusion regarding the implications of certain choices on the overall permutations.

MathematicalPhysicist
Science Advisor
Gold Member
Messages
4,662
Reaction score
372
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?
 
Physics news on Phys.org
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?
 
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.
 
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:
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!
 
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.
 
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 tomorrow with a fresh start I'll succeed.
thanks matt.
 
No. Take n=1, if I send 1 to 2, then I can't possibly satisfactorily do anything with 2 and 3.
 
sorry, it should be, we have 3n-2 places for n to go.
 

Similar threads

High School Combinatorics and Magic squares
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
6K
Undergrad Can Generating Functions Simplify the Calculation of Currency Combinations?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Probability of ending up with Rhode island
  • · Replies 4 ·
Replies
4
Views
1K
MHB The number of possible permutations for the assessment
  • · Replies 2 ·
Replies
2
Views
3K
QFT: Normalization of coherent states
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Is this a proof of the Collatz Conjecture?
  • · Replies 8 ·
Replies
8
Views
3K
Undergrad If n is an integer, and 3n+2 is even, prove that n is also even
  • · Replies 7 ·
Replies
7
Views
9K
Undergrad How to find the nth binary permutation?
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Computing a variance in astrophysics context
  • · Replies 1 ·
Replies
1
Views
2K