OMC075(C)

　包除原理を用いて解く．まず，以下の問題を $k=0,1,\ldots, 8$ について考える．

• $i=1,2,\ldots, 8$ のうち，決められた $k$ 個が $A_{i}=A_{i+1}$ を満たすとき，$A$ として考えられるものは何通りですか？

この問題の答えは $k\neq 8$ のとき $3^{8-k}$ 通り，$k=8$ のとき $3$ 通りである．
　$8$ 個のうち，$k$ 個を決める方法は ${}_{8}\mathrm{C}_{k}$ 通りであることから，元の問題の答えは以下のように表せる：

$$\sum_{k=0}^{8}{{}_{8}\mathrm{C}_{k}(-1)^{k}3^{8-k}}+2(-1)^8=(3-1)^8+2=\mathbf{258}.$$

　以上の議論から，一般に長さを $n~(\geq 2)$，$A$ の数字の種類を $m$ とすると，答えは $(m-1)^n+(m-1)(-1)^n$ であると拡張することができる（一般化した答えが求まると，その式が正しいかどうかを $n,m$ が小さいときに確かめることができる）．