星取りの場合の数

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

横綱・大関の休場で少し寂しかった大相撲秋場所は、一人横綱の日馬富士が意地の優勝で幕を閉じました。ということで、今回は相撲の星取りの問題です。

問題は、
「大相撲（１日１番１５日間対戦する）で、連敗のない星の取り方は何通りあるか」
です。

ここは、漸化式 を利用するのが簡単です。

ｎ日目の相撲が終わったあとの連敗のない星の取り方を Ａ（ｎ）とすると、
Ａ（１）＝２　　（○または●）
Ａ（２）＝３　　（○○、○●または●○）
です。

続いて、ｎ≧３のとき、Ａ（ｎ）をＡ（ｎ－１）とＡ（ｎ－２）で表しましょう。

初日○の場合、２日目は○でも●でもよいので、２日目以降のｎ－１回の対戦の星の取り方は、 Ａ（ｎ－１）通り です。

一方、初日●の場合、２日目は○でなければならず、そして３日目は○でも●でもよいので、３日目以降のｎ－２回の対戦の星の取り方は、 Ａ（ｎ－２）通り になります。

したがって、
Ａ（ｎ）＝Ａ（ｎ－１）＋Ａ（ｎ－２）
が成り立ちます。

あとは、Ａ（１）＝２、Ａ（２）＝３を使って逐次計算するだけで、
　Ａ（３）＝　Ａ（２）＋　Ａ（１）＝５
　Ａ（４）＝　Ａ（３）＋　Ａ（２）＝８
　Ａ（５）＝　Ａ（４）＋　Ａ（３）＝１３
　Ａ（６）＝　Ａ（５）＋　Ａ（４）＝２１
　Ａ（７）＝　Ａ（６）＋　Ａ（５）＝３４
　Ａ（８）＝　Ａ（７）＋　Ａ（６）＝５５
　Ａ（９）＝　Ａ（８）＋　Ａ（７）＝８９
Ａ（１０）＝　Ａ（９）＋　Ａ（８）＝１４４
Ａ（１１）＝Ａ（１０）＋　Ａ（９）＝２３３
Ａ（１２）＝Ａ（１１）＋Ａ（１０）＝３７７
Ａ（１３）＝Ａ（１２）＋Ａ（１１）＝６１０
Ａ（１４）＝Ａ（１３）＋Ａ（１２）＝９８７
Ａ（１５）＝Ａ（１４）＋Ａ（１３）＝１５９７
から、連敗のない星の取り方は １５９７通り で、これが答えです。

ちなみに、一般項は、

になります。