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?




*A good way to count 3's and 4's is to "fix" the first rail, and the second, variate the third, then variate the second and so on. You could try complementary counting, but to my knowledge, casework is the best approach.

