Я сделал по другому.
Посчитал возможное число комбинаций, удовлетворяющих условию для 4-х ячеек. Получилось - 8. Вот они.
0101
0110
0111
1010
1101
1011
1110
1111
Начинаются или оканчиваются нулем по три комбинации.
Количество комбинаций для 8 ячек будет равно 8*8-3*3=55
Хотя про Фибоначчи, конечно, выглидит солиднее
