漸化式タイプの場合の数

最後に着目するタイプ

例題1

a,b,cという3種類の文字を、左から順に並べます。同じ文字を何度使ってもかまいません。ただし、aの右となりは必ずcであり、bの右となりはa,bcのどれでもよく、cの右となりはbかcであるものとします。
この規則で2個並べるのは下のように6通りです。

中学受験算数カンガープリント 場合の数・フィボナッチ型最後に着目2210
左から6個並べる場合の並べ方は何通りありますか。

解説

吹き出し用まなぶくんイラスト

はい、完全に前の問題と同じ解き方ですね!
最後の文字が何かで表に整理します。

また、2個並べた6通りを最後の文字でグループ分けすれば、
・最後がaは(ba)
より、bから

・最後がbは(bb、cb)
より、bとcから

・最後がcは(ac、bc、cc)
より、aとbとcから。

中学受験算数カンガープリント 場合の数・フィボナッチ型最後に着目2211
吹き出し用カンガルー先生イラスト

はい、良くできていますね。
ちなみに「最後がc」は、「1つ前の合計」と同じです。

中学受験算数カンガープリント 場合の数・フィボナッチ型最後に着目2212
吹き出し用まなぶくんイラスト

そうですね。
「1つ前のa+b+c」とは、「1つ前の合計」のことですね。
あとはひたすら表をうめるだけですね。

吹き出し用カンガルー先生イラスト

ちなみにこの表は、矢印が重ならないため、あまりぐちゃぐちゃにはなりません。

中学受験算数カンガープリント 場合の数・フィボナッチ型最後に着目2214
吹き出し用まなぶくんイラスト

そうですね。
同じように表をうめていくと・・・

中学受験算数カンガープリント 場合の数・フィボナッチ型最後に着目2216
吹き出し用まなぶくんイラスト

求まりました。
141通りです。

吹き出し用カンガルー先生イラスト

正解です。

吹き出し用まなぶくんイラスト

確かにフィボナッチ数列にはなりませんでした。

吹き出し用カンガルー先生イラスト

そうですね。
フィボナッチ数列にならない問題もたくさんありますからね。