組合せの問題（２７）

こんにちは。東久留米市の学習塾塾長です。

今回は、２００８年ＡＩＭＥの組合せの問題です。

問題は、
「偶数個のＡが並ぶ列と奇数個のＢが並ぶ列を交互に並べた文字列がある。例えば、ＡＡ、ＢやＡＡＢＡＡはこれに当てはまるが、ＢＢＡＢは当てはまらない。このような文字列で１４文字であるものの個数を求めよ。」
です。

前回（組合せの問題（２６））と同じような問題です。今回も漸化式を利用します。

表１のように、１以上の整数ｎに対して偶数個のＡが並ぶ列と奇数個のＢが並ぶ列を交互に並べたｎ文字の列で、偶数個のＡで終わるものの個数をａn、奇数個のＢで終わるものの個数をｂnとします。

▲表１．ａnとｂnです

この表から、
ａn+2＝ａn　＋ｂn
ｂn+2＝ａn+1 ＋ｂn
が成り立つことが判ります。（例えば、ａn、ｂnの文字列は最後にＡが偶数個並んでいる（ｂnの場合は０個）のでその右端にＡＡを並べるとａn+2の文字列になります。一方、ａn+1の文字列は最後にＡが並んでいるのでその右端にＢを並べた場合と、ｂnの文字列は最後にＢが奇数個並んでいるのでその右端にＢＢを並べた場合にｂn+2の文字列になります）

あとは上記の漸化式を使って、

を計算していくと、表２になります。

▲表２．計算した結果です

以上から、求める文字列の個数は １７２（個） で、これが答えです。


簡単な問題です。