We have a wall with $7$ slots. We can color the wall either with blue or red.
How many combinations do we have to color the wall if two red slots cannot be neighbors?
I thought, in a very intuitive way, to try all the different cases. For example if color $0$ slots of red, then we have 1 combination.
If we color $1$ slot of red, we have 7 combinations.
If we color $2$ slots of red then we have 5+4+3+2+1 = 15 combinations.
I thought of this case by coloring the first slot and counting the combinations, and moving the firs slot and counting again…
The point with this approach is that I get 23 since there was other two cases (3 red = 3+2+1, and 4 red = 1) but the solutions says that there are 34!
Where am I wrong? And is there another approach on how to solve this? It would also be nice if you could give me some hints on how to solve this kind of combinatorics exercises (maybe by criticizing my approach)since I often have trouble!
Best Answer
Making a complete organized list is a perfectly valid method. However, it can be painful even for mid-sized problems. Also, it is all too easy to forget to list some items.
One solution is to use a (correct) computer program. However, in our problem there is a nice approach that works in general.
Suppose we are painting $n$ slots. Call a colouring good if no two reds are neighbours. Let $g(n)$ be the number of good colourings of an $n$ slot wall.
In a good colouring of $n\ge 2$ slots, the leftmost slot is either (i) blue or (ii) red.
In case (i), there are $g(n-1)$ good ways to complete the colouring.
In case (ii) the second slot must be blue, and there are $g(n-2)$ good ways to complete the colouring.
Thus we have obtained the recurrence $$g(n)=g(n-1)+g(n-2).\tag{1}$$ Now we can compute. It is clear that $g(1)=2$ and $g(2)=3$. So from (1) we get $g(3)=5$, and then $g(4)=8$, $g(5)=13$, $g(6)=21$, and $g(7)=34$. Note that we are getting Fibonacci numbers.
Remark: Your way of tackling the problem can be modified to give an interesting general approach. It can be shown if there are $n$ slots, then there are $\binom{n-r+1}{r}$ ways to have $r$ red slots with no reds adjacent. So the count for $n=7$, $r=3$ is $\binom{5}{3}$, that is, $10$. If we combine that with your other counts, which are correct, we get $34$.