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?
Best Answer
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}$$