# How many ways can you order 1,2,3,4,5 without any consecutive numbers touching?

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

-
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 '14 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 '14 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 '14 at 8:18

There's not that many cases, we could draw a 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".

-

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?

-