4
$\begingroup$

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?

3 Answers 3

2

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

  • 0
    @AlexB. Done. Thanks.2012-01-27
2

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.

  • 2
    @anil: Si$m$ple answers are encouraged! Answers which claim to be simple, but are are hard to understand/lacking in proper information are to be eschewed though :-)2012-01-27
0

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