Question

For Avavind:
There are K 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?

Answer 1

This is tricky problem. Obviously if we don't have constraints of no consecutives, then there are
\[ {k \choose 3} \]
choices.

But with the constraint, it get's trickier.

Let's look at a few examples.

If k = 5, and we label the stations 1 2 3 4 5, then there is only one option:
1 3 5

If k = 6, then there are four options:
1 3 5
1 3 6
1 4 6
2 4 6

If k=7, there are ten options:
1 3 5
1 3 6
1 3 7
1 4 6
1 4 7
1 5 7
2 4 6
2 4 7
2 5 7
3 5 7

If k=8, there are twenty options.

Answer 2

Now how to generalize ...

Answer 3

James Please hold on sec, I want to give it a fair try :)

Answer 4

Sure.

Answer 5

Guessing from pattern: \( \large \binom{K-2}{3} \)

Answer 6

Do you have a solution? @james

Answer 7

I do.

Answer 8

Intuitively, your hypothesis makes sense.

Answer 9

Okay, so what's your analysis ? :)

Answer 10

Suppose the three stations in order are located at a, b and c.

We know that a must be at least 4 stations away from the last station, hence
\[ 1 \leq a \leq k - 4\]
Now b must be at least 2 stations after a and at least 2 stations before the k-th:
\[ a + 2 \leq b \leq k - 2 \]
Similarly, c must be at least 2 stations after c:
\[ b + 2 \leq c \leq k \]


Hence c can take on \( k - (b+2) + 1 = k - b - 1 \) values.

Therefore the total number of possibilities of a,b,c is
\[ \sum_{a=1}^{k-4} \sum_{b=a+2}^{k-2} (k - b - 1) \]

Answer 11

Evaluate that (slightly brutal, make a mistake, fix it, make another, start again, finally get it) you'll find it is equal to
\[ \frac{1}{6} (k^3 - 9k^2 + 26k - 24) \]

I'd love you to show this is equal to
\[ {k-2 \choose 3} \]

Answer 12

Sure, here is it:

\[ {K-2 \choose 3} =\frac{ (K-2)(K-3)(K-4)}{6} = \frac{1}{6} (K^3 - 9K^2 + 26K - 24) \]

Answer 13

Exactly.

Now, we know for sure that
\[ { k-2 \choose 3} \]
is right, we can say that our (my?) intuitive derivation of this is right:

Given the placement of the first station, one is knocked out; then after the second is place, so is another. Hence we need to choose 3 stations from k-2.

I would not have trusted that intuitive derivation without the more formal derivation. But it's nice to know it does indeed work.

Answer 14

James what you are saying intuition is a standard trick in combinatorics, but this doesn't answer for the more general case of X stations from K intermediate stations.

Answer 15

Btw I think I should now try to hunt down a pure combinatorial analysis of this solution.

Answer 16

Gee, you're so hard to please. Round of applause please.
=====
Now, to the general problem, an obvious hypothesis is
\[ { k-x+1 \choose x } \]

Answer 17

Haha you did great job man :D Clap Clap Clap :D

Answer 18

I feel better now. I guess I don't trust that "intuitive derivation" because that knocking out of options feels like a process that could go wrong; it doesn't feel sufficiently well defined. Or it could just be I don't spend enough time around these sorts of problems. Or I'm just very skeptical, which I think is a good thing. ;-)

Answer 19

Anyway. If you find another derivation, let me know!

Answer 20

Sure :)

Answer 21

hey :)

Answer 22

So Aravind, I did all this work for you. Did you ever use this solution?

Answer 23

hmm ...yes!