OMC206(E) - やや愚直な数え上げ方での解法

　一般に正 $n$ 角柱 $P_1P_2…P_nQ_1Q_2…Q_n$ の塗り分けを考える．また $P_{n+1}, Q_{n+1}$ をそれぞれ $P_1, Q_1$ に塗った色と同じとし，三色の並びについて赤 $\rarr$ 青 $\rarr$ 緑 $\rarr$ 赤の順を「正の順」，赤 $\rarr$ 緑 $\rarr$ 青 $\rarr$ 赤を「負の順」と定義する．条件を満たす塗り方について，$(P_k, Q_k)$ の色と $(P_{k+1},Q_{k+1})$ の色は「正負が同じ順で色の組みが異なるもの」もしくは「正負が違う順で色の組みが同じもの」のどちらかとなる．$($ 例えば $(P_1,Q_1)=($ 赤，青 $)$ のとき $(P_2,Q_2)$ は $($ 青，緑 $)$ $($ 緑，赤 $)$ $($ 青，赤 $)$ のいずれかである $)$
　したがって正 $n$ 角形 $A_1A_2…A_n$ の各頂点に赤，青，緑を割り振って，さらに正負を一つ定めることで「 $(P_1,Q_1)$ が定めた正負の順で，$P_k, Q_k, A_k$ が全て異なる色にする」という手順で $(P_n,Q_n)$ まで色を決定できる．この手順で $A_k$ と $A_{k+1}$ が同色の時，$(P_k,Q_k)$ と $(P_{k+1},Q_{k+1})$ は正負が違う順となるので，$(P_1,Q_1)$ と $(P_{n+1},Q_{n+1})$ が一致するためには，正 $A_1A_2…A_n$ 角形の辺で両端点の色が同一のものが偶数本である必要がある．逆に偶数本であれば条件を満たす $P_1P_2…P_nQ_1Q_2…Q_n$ の塗り分けを決定できる．以上から，「正 $n$ 角形 $A_1A_2…A_n$ の各頂点を赤，青，緑で塗り分ける方法で，両端点が同一色の辺が偶数本であるものの個数」を求めれば良い．これを $p_n$ 通りとする．
　まず，正 $n$ 角形 $A_1A_2…A_n$ の各頂点に赤，青，緑を同一色が隣り合わないように割り振る方法を $a_n$ 通りとしてこれを求める．$a_2=6, a_3=6, a_4=18$ であり，$a_{n+2}$ は $A_{n+2}$ と $A_n$ が同一色のとき $(=a_n$ 通り $)$ ，$A_{n+1}$ の色は $2$ 通りあり，$A_{n+2}$ と $A_n$ が異なる色のとき $(=a_{n+1}$ 通り $)$ ，$A_{n+1}$ の色は $1$ 通りなので $a_{n+2}=a_{n+1}+2a_n$ となる．これを解き $a_n=2^n+2(-1)^n$ が得られる．
　$p_{2n}$ 通りの中で両端点が同一色の辺が $2m$ 本であるものは，$a_{2n-2m}$ 通りそれぞれについて $A_1,A_2…A_{2n-2m},A_{2n-2m+1}$ から重複を許して $2m$ 個を選び「 $A_k$ が選ばれたとき辺 $A_kA_{k+1}$ 上に $A_k$ と同じ色の点を増やす，$A_{2n-2m+1}$ が選ばれたときは辺 $A_{2n-2m}A_1$ 上に $A_1$ と同じ色の点を増やす」という操作と対応させられるので $$p_{2n}=\displaystyle\sum_{m=0}^na_{2n-2m} \times {}_{2n-2m+1}\mathrm{H}_{2m}= \displaystyle\sum_{m=0}^n(2^{2n-2m}+2){}_{2n}\mathrm{C}_{2m}=\dfrac{(2+1)^{2n}+(2-1)^{2n}}2 +((1+1)^{2n}+(1-1)^{2n})=\dfrac{3^{2n}+1}2 +2^{2n}$$ となる．これに $(P_1,Q_1)$ の順の正負を考えることで，条件を満たす塗り分けの方法は $n$ が偶数の場合 $3^n+2^{n+1}+1$ で表されることがわかる．あとは本解説と同様に求めれば良い．