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?
 A: 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}$$
A: 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\;\;$ (so $7$ noughts)
$X\;\;\;  0\;\;\;  X\;\;\;  0\;\;\;  X\;\;\;  0\;\;\;  X\;\;\;  0\;\;\;  X\;\;\;  0\;\;\;  X\;\;\;  0\;\;\;  X\;\;\;  0\;\;\;  X$
Any $3$ of the $8$ crosses  can be stopping stations, and so
number of ways $= \Large\binom83 = 56$
The formula generalizes to $\Large\binom{N-k+1}{k}$
Note, btw, that the stations are numbered AFTER determining the stops.
A: 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
