Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
I don't understand from this line "The standard technique is to consider $y_i = x_i - (i-1)$", Could you please explain? –  Quixotic Jan 25 '12 at 3:23
    
Neat! You should also mention that since the $y_i$ are automatically increasing, you are counting the number of unordered configurations of the $y_i$s. –  Alex B. Jan 25 '12 at 4:52
    
@MaX: We want to count number of $(x_1,x_2, \dots, x_K)$ such that $x_{j+1} - x_j \gt 1 $. Instead, we count $(y_1, y_2, \dots, y_K)$ as there is a $1-1$ mapping. Note that the $y_i$ satisfy $y_{j+1} - y_j \gt 0$. So in effect, we need to select $K$ distinct numbers for $1,2,\dots, N-K+1$, and sort them to get the $y_i$. –  Aryabhata Jan 25 '12 at 7:11
    
@AlexB. Done. Thanks. –  Aryabhata Jan 27 '12 at 0:54
add comment

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.

share|improve this answer
    
I am quite new to the forum, so it would help me if i knew why i have been downvoted, so that i don't commit a similar mistake again. Are simple answers to be eschewd ? –  true blue anil Jan 26 '12 at 7:49
2  
+1: I believe this works and is a nice approach. Some more explanation would be good, though, because as written, it is not easy understand. As to downvote, seems like someone does not like any answers here. My answer (which is correct, IMO) was downvoted too. –  Aryabhata Jan 27 '12 at 0:45
    
For a possible explanation of the approach, once you pick 3 Xs, you are left with 7 Os and 3Xs which gives rise to the arrangement of no two consecutive Xs (and that is a 1-1 mapping). To generalize to say N=20 and k=4, you start with 16 Os, and place 17 Xs alternately and pick 4 of those, giving rise to the answer of $\binom{17}{4}$. –  Aryabhata Jan 27 '12 at 0:50
2  
@anil: Simple answers are encouraged! Answers which claim to be simple, but are are hard to understand/lacking in proper information are to be eschewed though :-) –  Aryabhata Jan 27 '12 at 0:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.