涂色问题中1×3+2×2是什么意思？有无其它解法

hjfmhh

如图，这是一面含 $A, B, C, D,E, F$ 六块区域的墙，现有五种不同颜色的油漆，一位工人要对这面墙涂色，相邻的区域不同色，则共有  1200  种不同的涂色方法；若区域 $D$ 不能涂甲颜色，则共有  960  种不同的涂色方法．

［解析］第一空：若 $C, E$ 的涂色相同，则共有 $5 \times 4 \times 3 \times 2 \times 3=360$ 种不同的涂色方法；若 $C, E$ 的涂色不相同，则共有 $5 \times 4 \times 3 \times 2 \times(1 \times3+2 \times 2)=840$ 种不同的涂色方法．故共有 $360+840=1200$ 种不同的涂色方法．第二空：因为区域 $D$ 不能涂甲颜色，所以区域 $D$ 的涂色方法有 4 种．若 $C, E$ 的涂色相同，则共有 $4 \times4 \times 3 \times 3 \times 2=288$ 种不同的涂色方法；若 $C,E$ 的涂色不相同，则共有 $4 \times 4 \times 3 \times 2 \times(1 \times3+2 \times 2)=672$ 种不同的涂色方法．故共有 $288+672=960$种不同的涂色方法．

涂色问题中$1\times3+2\times2$是什么意思？有无其它解法，是从A开始涂色还是从D开始涂色的？是否一定要分CE同色与不同色？

kuing

我将解决更一般情况。

先考虑一串的情况，如图：$\boxed{A_1}{-}\boxed{A_2}{-}\boxed{A_3}{-}\cdots{-}\boxed{A_n}$
用 `m` 种颜色给这一串 `n` 块涂色，相邻不同色，容易知道，方法数为 `m(m-1)^{n-1}`。

然后考虑变成环的情况，如下图：

设这种情况的涂色方法数为 `f(n)`，易知 `f(2)=m(m-1)`。

我们再看回前面那一串，当 `n\geqslant3` 时：
如果那串的 `A_1` 与 `A_n` 不同色，那将它们首尾相接便得到符合要求的环；
如果那串的 `A_1` 与 `A_n` 同色，那就将 `A_n` 剪掉！然后再首尾相接，此时便得到符合条件的 `n-1` 块的环。
因此，我们得到
\[m(m-1)^{n-1}=f(n)+f(n-1),\quad\forall n\geqslant3,\]
注意到 `m(m-1)^{n-1}=(m-1)^n+(m-1)^{n-1}`，由此容易求出 `f(n)` 的通项为
\[f(n)=(m-1)^n+(-1)^n(m-1).\]

回到原题，第一空：
先涂 `D`，有 `5` 种方法；
涂完 `D` 后，周围的五块相当于一个环，用四色涂该环，因此上式取 `m=4` 及 `n=5`，方法数为 `240`。
所以答案就是 `5\times240=1200`；
第二空：即第一步减少一种方法，第二步一样，所以就是 `4\times240=960`。

hjfmhh

\begin{aligned}
& f(n)+f(n-1)=(m-1)^n+(m-1)^{n-1}, f(n)-(m-1)^n=-\left[f(m-1)-(m-1)^{n-1}\right], n \geqslant 3 \\
& \text{令 } a_n=f(n)-(m-1)^n, a_2=f(2)-(m-1)^2=m(m-1)-(m-1)^2=m-1 \neq 0 . \therefore\left\{a_n\right\} \text { 是等比数列} \\
& a_n=a_2(-1)^{n-2}=(-1)^n(m-1) \text {, 即 } f(n)=(m-1)^n+(-1)^n(m-1) .
\end{aligned}