Counting train stops using combinatorics

Question

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.

Answer 1

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.

            A   |   x   x   x   |   x   x   |   x   |   x   x   B

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$:

            A   |   x   |   x   |   x   |   B  
              1     2       3       4     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$.

Answer 2

The problem asks for

number of ways to order 4 "stop" and 8 "pass" such that no two "stop" are consecutive.

However, the "consecutive" criterion is hard to handle. We can sidestep it by noticing that each stop must be followed by a pass, and then rephrase the problem to

number of ways to order 4 "stop then pass" and 4 "pass".

But that's not quite right, because now we have lost all of the solutions that stop at station 12. Fix that by adding a virtual station between 12 and B where the train never stops. Then what we need to count is

number of ways to order 4 "stop then pass" and 5 "pass".

which is easily answered by standard techniques.

Answer 3

If the train is stopping in $4$ stations Then train is not stopping in $8$ stations. Let us denote halting stations with | and non halting stations with x Then,

   x  x  x  x  x  x  x  x

Now, between these $8$ non-halting stations we have $9$ places and we select these $9$ places as halt between these 8 stations. Thus answer should be $\binom{9}{4}$.

Answer 4

The answers for such type of problems can be found by a simple method:

$$ \frac{(n-p+1)!}{p!(n-2p+1)!} $$

Example here we can see that there are 12 stations. So, $n=12$, $p=4$. So, the answer would be

$$ \frac{(12-4+1)!}{4!(12-8+1)!} = \frac{9!}{4!5!} $$

If you know about combinations, then you can simply use, $^{(n-p+1)}C_p$. In this question, $n$ is number of stations and $p$ is number of stations on which you want to stop.