Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Permutation without consecutive numbers, such as 1,2 or 5,4?

share|improve this question
    
You can pretty much list them directly. There are two cases to consider: one where the first "slot" uses 1 or 5 , the other in which you start any of the other numbers . Your choices for later numbers in the "sequences" are largely forced... –  RecklessReckoner Feb 3 at 2:47
    
A simple Ruby solution: (1..5).to_a.permutation.count { |p| p.each_cons(2).all? { |m,n| (m - n).abs != 1 } } –  Jacopo Notarstefano Feb 3 at 3:49
    
If you can't think of any other way to get the answer, you can simply list all the permutations of 1,2,3,4,5 and then cross out the ones that don't work. There are only 120 permutations, so it shouldn't take more than ten or fifteen minutes to solve by this method. –  MJD Feb 3 at 8:18

2 Answers 2

There's not that many cases, we could draw a decision tree:

Decision tree

By symmetry, starting with either $1$ or $5$ results in the same number of sequences. Similarly starting with either $31$ or $35$ results in the same number of sequences. So for the seven permutations we found above, we apply the permutation $(15)(24)$ to obtain its "partner".

share|improve this answer

Hint: Split into cases on the position of the number $3$.

  • If the number $3$ is not first or last, then $1$ and $5$ must be on either side of it. Then what?

  • If the number $3$ is first or last, then $1$ or $5$ will be next to it. How many ways are to fill the other numbers in?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.