[答273] ３色での塗り分け
[答273] ３色での塗り分け
図のように、14個の長方形が１列に並んでおり、両端に赤を塗ります。
中の 12個の長方形を、赤･緑･青で塗り分けます。
隣り合う長方形には異なる色を塗るとき、塗り方は何通り？
[解答1]
中の長方形がｎ個のときの塗り方を an 通りとします。
中の 12個の長方形を、左から順に、左隣と異なる色を塗る方法は、212 通りあって、
そのうちの右端が赤の塗り方は a11 通りで、それ以外が a12 通りです。
従って、a12＝212－a11 になります。
同様に、漸化式 an+1＝2n+1－an が得られます。
an+1－2n+2/3＝－(an－2n+1/3) 、
数列{ an－2n+1/3 }は公比が －1 の等比数列です。
an－2n+1/3＝(a1－4/3)(－1)n-1 、
ここで、a1＝2 だから、an＝2{2n－(－1)n}/3 になります。
a12＝2{212－(－1)12 }/3＝2730 通りです。
[解答2] uch*n*anさんのコメントより
左端が赤で n 個の長方形を並べた場合において，
さらにその右，n+1 番目が，赤を an 通り，青を bn 通り，黄を cn 通り，とすると，
an＝bn-1＋cn-1＝(an-2＋cn-2)＋(an-2＋bn-2)
＝(bn-2＋cn-2)＋2an-2＝an-1＋2an-2
ただし，a1＝2, a2＝2 です。
☆ 漸化式 an＝an-1＋2an-2 の解き方
an＋an-1＝2(an-1＋2an-2) と変形すれば、
数列{ an+1＋an }は公比が 2 の等比数列です。
an+1＋an＝(a2＋a1)･2n-1＝2n+1
以下、[解答1]と同様に解いてもいいし、
an－2an-1＝－(an-1－2an-2) と変形すれば、
数列{ an+1－2an }は公比が －1 の等比数列です。
an+1－2an＝(a2－2a1)･(－1)n-1＝2(－1)n
an+1＋an＝2n+1，an+1－2an＝2(－1)n の差をとれば、
3an＝2n+1－2(－1)n です。
[解答3] 再出発さんのコメントより
左端(第０枠)が赤で 第ｎ枠が 赤を an 通り，青または黄色を bn 通りとすると、
a1＝0，b1＝2，an+1＝bn，bn+1＝2an＋bn
が成り立ちます。
an+1＋bn+1＝2(an＋bn) だから、
数列{ an＋bn }は公比が 2 の等比数列です。
an＋bn＝(a1＋b1)･2n-1＝2n
an+1－bn+1/2＝－(an－bn/2) だから、
数列{ an－bn/2 }は公比が －1 の等比数列です。
an－bn/2＝(a1－b1/2)･(－1)n-1＝(－1)n
an＋bn＝2n，an－bn/2＝(－1)n の差をとれば、
(3/2)bn＝2n－(－1)n 、bn＝2{2n－(－1)n}/3 になります。
本問で求めるのは b12＝2{212－(－1)12 }/3＝2730 通りです。
.
