There are $12$ stations between A and B, in how many ways you can select 4 stations for a halt in such a way that no two stations are consecutive How do we solve this question with permutation and combination?
Can we solve this by Fibonacci Series?
Is the answer (12-2)C4 {10 combination 4}?
 A: It's all in the encoding. Suppose you have made a choice, i.e. you have chosen 4 stations out of 12. Let's denote by $0$ a station that you didn't choose and by $1$ a station that you did choose, and write them down left to right. We get something like this:
$$
100001010001
$$
This string can be arbitrary except two 1's are forbidden to stand together. Now, it is tempting to group each 1 with a 0 adjacent to it on the right, but we have a problem if there's a 1 on the rightmost position. What do we do? Let us add a $13$th station to the right, with the rule that noone is ever allowed to stop there. Then our encoded string becomes:
$$
1000010100010
$$
Now let us change the encoding some more. Now we have a guarantee that each 1 has a 0 immediately adjacent to it on the right. So let us replace each 10 pair by a new symbol $*$. We get
$$
*000**00*
$$
What we need to realize now is that in such an encoding we will always get four $*$ signs and five $0$ signs. More importantly, any string with four stars and five zeroes is possible. Therefore the answer is $9 \choose 4$, the number of 4-subsets in a 9-set.
