# In how many ways a train can stop at $K$ of $N$ intermediate stations without stopping in any consecutive stations

There are $N$ intermediate stations on a railway line from one terminus to another. In how many ways can a train stop at three of these intermediate stations if no two of these stopping stations are to be consecutive?

I observed that $N \ge 5$ and for $N=5,6,7,8,9,10$ the answers are $1, 4, 10, 20, 35, 56$.

Then with the aid of tetrahedral numbers, I guessed that the general answer should be ${ N-2 \choose 3}$. and this happens to be correct.

I was wondering how to prove this (preferably a combinatorial way)? And what about the more general problem of the train stopping in $K$ of $N$ intermediate stations?

-

Number the stations $1,2,\dots, N$ with $j,j+1$ being adjacent.

You need to pick $K$ numbers $x_1 \lt x_2 \lt \dots \lt x_K$ from these so that no two are consecutive.

The standard technique is to consider $y_i = x_i - (i-1)$.

These $y_i$ are distinct numbers in $1, 2, \dots, N-K+1$ and there is a $1-1$ mapping between the $x_i$ and $y_i$.

To get the $y_i$, we can pick $K$ distinct numbers from $1,2, \dots, N-K+1$ and just sort them in ascending order. Since this is again a $1-1$ mapping, the number we need is same as choosing $K$ distinct numbers from $1,2,\dots, N-K+1$ and thus the answer is

$$\binom{N-K+1}{K}$$

-
I don't understand from this line "The standard technique is to consider $y_i = x_i - (i-1)$", Could you please explain? –  VelvetThunder Jan 25 '12 at 3:23
Neat! You should also mention that since the $y_i$ are automatically increasing, you are counting the number of unordered configurations of the $y_i$s. –  Alex B. Jan 25 '12 at 4:52
@MaX: We want to count number of $(x_1,x_2, \dots, x_K)$ such that $x_{j+1} - x_j \gt 1$. Instead, we count $(y_1, y_2, \dots, y_K)$ as there is a $1-1$ mapping. Note that the $y_i$ satisfy $y_{j+1} - y_j \gt 0$. So in effect, we need to select $K$ distinct numbers for $1,2,\dots, N-K+1$, and sort them to get the $y_i$. –  Aryabhata Jan 25 '12 at 7:11
@AlexB. Done. Thanks. –  Aryabhata Jan 27 '12 at 0:54

You may like a less technical explanation. Let the stations at which NOT stopped be denoted by noughts, and permissible places for stoppages by crosses, as under, for N = 10, k = 3

x 0 x 0 x 0 x 0 x 0 x 0 x 0 x

Any 3 of the crosses can be stopping stations, and so

# of ways = C(8,3) = 56

The formula generalises to C(N-k+1,k)

Note, btw, that the stations are numbered AFTER determining the stops.

-
I am quite new to the forum, so it would help me if i knew why i have been downvoted, so that i don't commit a similar mistake again. Are simple answers to be eschewd ? –  true blue anil Jan 26 '12 at 7:49
+1: I believe this works and is a nice approach. Some more explanation would be good, though, because as written, it is not easy understand. As to downvote, seems like someone does not like any answers here. My answer (which is correct, IMO) was downvoted too. –  Aryabhata Jan 27 '12 at 0:45
For a possible explanation of the approach, once you pick 3 Xs, you are left with 7 Os and 3Xs which gives rise to the arrangement of no two consecutive Xs (and that is a 1-1 mapping). To generalize to say N=20 and k=4, you start with 16 Os, and place 17 Xs alternately and pick 4 of those, giving rise to the answer of $\binom{17}{4}$. –  Aryabhata Jan 27 '12 at 0:50
@anil: Simple answers are encouraged! Answers which claim to be simple, but are are hard to understand/lacking in proper information are to be eschewed though :-) –  Aryabhata Jan 27 '12 at 0:52

If the train is stopping in 3 stations Then train is not stopping in (N-3) stations. Now , Between these (N-3) Non-Halting stations we have N-2 places and we select these N-2 places as halt between these N stations. Thus answer should be N-2C3

-