There are 12 intermediate stations on a railway line between 2 stations. Find the number of ways a train can be made to stop at 4 of these so that no two stopping stations are consecutive.
My attempt:
Initially I found the maximum allowed stop number for the first stop that satisfies the consecutive station condition.
$$A \quad 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \quad 9 \quad 10 \quad 11 \quad 12 \quad B$$
I can have a stop at stations 8, 10, 12. Hence the train can travel a maximum of 6 stations before coming to its first stop, so number of ways $= 6 \cdot 1 \cdot 1 \cdot 1 = 6$.
Then I shift the first stop to station number 5. Now I have 5 options for stop 1 and 2 possible options for any of the next three stops. Hence number of ways $= 5 \cdot 2 \cdot 3 \cdot 1 = 30$.
Again, I shift the first stop to station number 4. Now I have 4 options for stop 1 and 3 possible options for any of the next 3 stops. Hence number of ways $= 4\cdot 3\cdot 3 = 36$.
Continuing the same logic, I arrive at an answer of 156. But the answer I have with me is 126.
Help appreciated. Thanks in advance.
Best Answer
The easiest way to solve it is to think of the four stops as fixed points and ask in how many ways the other stations can be inserted between them, if you must have at least one station between stops.
Here, I’ve used bars to mark the four stops and $x$’s to mark the other stations. This is almost a standard stars-and-bars problem. You have five ‘blocks’ of stations, one before the first stop, three between stops, and one after the fourth stop. In my diagram I’ve put $0,3,2,1$, and $2$ stations into those blocks. Each of the middle three blocks must contain at least one station; the end blocks can be empty. In other words, I’m starting from this picture and have five stations left to distribute, each of which may go into any of the blocks numbered $1$ through $5$:
This amounts to counting the arrangements of a string of four bars and five $x$’s: there are $\binom94=126$ to choose which $4$ of the $9$ positions will be occupied by the bars.
Your approach will work if you count carefully enough. As you say, there are $6$ possibilities if the last three stops are at $8,10$, and $12$. Now leave the last two stops at $10$ and $12$ and move the second stop forward to $7$: there are just $5$ possibilities for the first stop. If you move the second stop forward to $6$, there are $4$, and so on, with just one when you move it all the way to $3$; these cases give you a total of $6+5+\ldots+1=\frac{6\cdot7}2=21$ possibilities. Now move the third stop forward to $9$; the same analysis will show that you have $5+\ldots+1=\frac{5\cdot6}2=15$ possibilites. As you keep moving the third stop forward, you get $4+3+2+1=10$, $3+2+1=6$, $2+1=3$, and $1$ possibility, for a total at this point of $21+15+10+6+3+1=56$ possibilities. Now repeat with the fourth stop moved forward to $11$. You’ll quickly find that most of the counting is a repetition of what you’ve already done, and you end up with $15+10+6+3+1=35$ possibilities. Similarly, with the last stop at $10$ you end up with $10+6+3+1=20$ possibilities. In the end you find yourself adding up $56+35+20+10+4+1$ to get $126$.