０２０	平成２１年度前期	横浜国立大学	工学部	・・・	場合の数（数学ＡＢ）	標準

　この問題では、問題の趣旨を的確に捉えて漸化式の計算に持ち込めば完答できるだろう。
漸化式が作れないと厳しいと思う。


横浜国立大学　工学部前期（２００９）

　赤、青、黄の３色を用いて、横一列に並んだ ｎ 個のマスを、隣り合うマスは異なる色にな
るように塗り分ける。ただし、使わない色があってもよい。両端のマスが同じ色になる場合
の数を ａ_ｎ とし、両端のマスが異なる色になる場合の数を ｂ_ｎ とする。次の問いに答えよ。
　（１）　ａ₃ 、 ｂ₃ 、 ａ₄ 、 ｂ₄　を求めよ。
　（２）　ａ_ｎ 、 ｂ_ｎ　（ｎ≧３） を ｎ の式で表せ。

（解）（１）　ａ₃＝３×２＝６　で 、 ａ₃＋ｂ₃＝３×２×２＝１２　より、　ｂ₃＝６

　　　　　　 ａ₄＝３×２＝６　で 、 ａ₄＋ｂ₄＝３×２×２×２＝２４　より、　ｂ₄＝１８

　　（２）　題意より、　ａ_ｎ+1＝ｂ_ｎ　、　ｂ_ｎ+1＝２ａ_ｎ＋ｂ_ｎ　である。

　　　　実際に、１　〜　ｎ ， ｎ＋１　のマスがあって両端が同じ色の場合に、１　〜　ｎ のマス

　　　　の両端は異なる色なので、その場合の数は ｂ_ｎ 通りある。

　　　　　よって、　ａ_ｎ+1＝ｂ_ｎ

　　　　同様にして、１　〜　ｎ ， ｎ＋１　のマスがあって、両端が異なる色の場合に、

　　　　　（イ）　１　〜　ｎ のマスの両端が同じ色のときの場合の数は ａ_ｎ×２ 通りある。

　　　　　（ロ）　１　〜　ｎ のマスの両端が異なる色のときの場合の数は ｂ_ｎ 通りある。

　　　　　よって、　ｂ_ｎ+1＝２ａ_ｎ＋ｂ_ｎ

　　　　ａ_ｎ+1＝ｂ_ｎ　を　ｂ_ｎ+1＝２ａ_ｎ＋ｂ_ｎ　に代入して、　ａ_ｎ+2−ａ_ｎ+1−２ａ_ｎ＝０

　　　　　このとき、　ａ_ｎ+2＋ａ_ｎ+1＝２（ａ_ｎ+1＋ａ_ｎ）　より、

　　　　　　　　　　ａ_ｎ+1＋ａ_ｎ＝２^ｎ-3（ａ₄＋ａ₃）＝１２・２^ｎ-3＝３・２^ｎ-1

　　　　　また、　ａ_ｎ+2−２ａ_ｎ+1＝−（ａ_ｎ+1−２ａ_ｎ）　より、

　　　　　　　　　　ａ_ｎ+1−２ａ_ｎ＝（−１）^ｎ-1（ａ₄−２ａ₃）＝−６・（−１）^ｎ-1＝６・（−１）^ｎ

　　　　　よって、　３ａ_ｎ＝３・２^ｎ-1−６・（−１）^ｎ　より、　ａ_ｎ＝２^ｎ-1−２・（−１）^ｎ

　　　　　　　　　　ｂ_ｎ＝ａ_ｎ+1＝２^ｎ−２・（−１）^ｎ+1＝２^ｎ＋２・（−１）^ｎ　　（終）

（コメント）　場合の数と漸化式の典型的な問題ですね！