Question

A train starting from Old Delhi railway station to Chandigarh railway station encounters 38 intermediate railway stations along its route. In how many ways can the train stop at exactly three intermediate stations such that no two of them are consecutive?

Answer 1

This doesn't appear to be an easy problem. The answer is 7140,
explanation below.

Consider 5 stations. There is only 1 way to have 3 stops with no
consecutive stops, namely {1,3,5}.

For 6 stations, {1,3,5} still works, as does {1,3,6}, and {2,4,6} and {1,4,6}

For 7 stations, the solutions for 6 stations still work. The new solutions
are {x,y,7} where x and y are nonconsecutive numbers less than or
equal to 5. If x=1, y can be {3,4,5}, 3 choices; if x=2, y can be
{4,5}, and if x=3, y must be 5. This yields another 6 solutions.

For 8 stations, the solutions for 7 stations still work. The new
solutions are {x,y,8}, where x and y are nonconsecutive numbers less
than or equal to 6. If x=1, y can be {3,4,5,6}. If x=2, y can be
{4,5,6}, and so on. This yields another 10 solutions.

For n stations, all the solutions for n-1 stations still work. The new
solutions are {x,y,n}, where x and y are nonconsecutive numbers less
than or equal to n-2. If x=1, y can be {3,4,5,6,...,n-2}, which gives
n-4 choices. If x=n-3, y must be n-2, 1 solution. Adding

(n-4) + (n-3) + ... 1

yields (n-3)(n-4)/2 new solutions.

So, the number of solutions for n stations is given by:

f[5] = 1
f[n] = f[n-1] + (n-3)(n-4)/2, for n>5

For 38, this is 7140.

The closed form of this recursion is C[n-2,3] aka (n-2)(n-3)(n-4)/6,
so there might be a much simpler way of thinking about this.

See also: http://oeis.org/A000292