【问题】

一个 1×8 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_________种填涂方案。

【解析（方案1）】

设存在n个方格，填涂情况有2种：

1. 如果第一个是黑格，那么第二个一定是白格。共有n-2个填涂方案数。

2. 如果第一个是白格，那么第二个可以是黑格或白格。共有n-1个填涂方案数。

所以：\(f(n)=f(n-1)+f(n-2)\)

也就是说这是一个斐波那契数列问题。

边界条件是：\(f(1)=2(黑,白)\) ；\(f(2)=3(黑白,白白,白黑)\)

枚举出前几个的答案：2,3,5,8。

则有：\(f(n)=f(8)=f(6)+f(7)=55\)

【解析（方案2）】

当存在0个黑格：
\(C_{9}^{0}=1\)

当存在1个黑格：
\(C_{8}^{1}=8\)

当存在2个黑格，6个白格，有7个空可以插入：
\(C_{7}^{2}=21\)

当存在3个黑格，5个白格，有6个空可以插入：
\(C_{6}^{3}=20\)

当存在4个黑格，4个白格，有5个空可以插入：
\(C_{5}^{4}=5\)

总方案数 = 1+8+21+20+5 = 55