How many ways? - difficult combinatorics These are from an archival local math contest:


*The city purchased train rails in two colors: gray and black. The only difference between them is the color. The project assumes that the rails will be installed in series of 10. We say that the series is elegant when no two black rails are directly adjacent to each other. How many different elegant series of 10 rails are possible?

I made some observations:

*

*In 3. I know the answer is supposed to be 144. If we have 6 black rails or more we cannot make an elegant series. For 1 black rail we can make 10 different series (the order matters), for two it is 8 + 7 + ... + 1 = 36 (i placed the first rail and looked where I can place the second one). For 5 rails there are two elegant series. However I cannot calculate the numbers for 3 or 4 black rails, is there any nice and clean way?


I will answer the third one first.
For 1,2 and 5 black rails you have already calculated it so I would not bother calculating again.
We will use the gap method
Case 1: 3 black rails
First, you lay down 7 grey rails so there are 8 gaps
Out of those 8 gaps, you select 3 because there are 3 black rails.
So $\dbinom{8}{3} = 56$
Case 2: 4 black rails
You lay down 6 grey rails so 7 gaps are left and you have to select 4 for 4 black rails
.
So $\dbinom{7}{4} = 35$
You have made an error in the case where there are 5 black rails. The answer should be 6 for that case(6C1)
Total = 10 + 36 + 56 + 35 + 6 +1= 144
