visual-learning

トリボナッチ型・階段の上り方

慶應義塾中等部 2007年度 第6問をアニメーションと樹形図で視覚的に解く

📐 問題（慶應義塾中等部 2007年度 第6問）

A 君は階段を 1 歩で 1段・2段・3段のどれかで上がれます。
  1. 4 段の階段の上り方は何通りありますか。
  2. 5 段の階段の上り方は何通りありますか。
  3. 10 段の階段の上り方は何通りありますか。
通り
⬇ 下にスクロールして解説とシミュレーションを見ていきましょう
ステップ 1

全経路をアニメーションで確認する（スライダーで段数を変更）

まずは段数を少なくして、すべての「上り方」を1つずつ確認しましょう。
青矢印 ＝ 1段上がり、橙矢印 ＝ 2段上がり、緑矢印 ＝ 3段上がりです。
「次の経路を見る」ボタンで順番に全パターンを表示します。
4 段
経路 1 / 7 合計 7 通り
1段上がり（青） 2段上がり（橙） 3段上がり（緑）
上り方一覧の樹形図（折りたたみ可能）

各分岐の「+1」は1段上がり、「+2」は2段上がり、「+3」は3段上がりを表します。葉ノード（終端）が各経路の完成です。

ステップ 2

f(n) = f(n−1) + f(n−2) + f(n−3) の仕組み ―「最後の一手」で考える

n段を上る方法のうち、
・最後に「1段上がって」到達した → その手前は (n−1) 段地点 → f(n−1) 通り
・最後に「2段上がって」到達した → その手前は (n−2) 段地点 → f(n−2) 通り
・最後に「3段上がって」到達した → その手前は (n−3) 段地点 → f(n−3) 通り
この3パターンしかないので、 f(n) ＝ f(n−1) ＋ f(n−2) ＋ f(n−3) が成り立ちます。
5
ステップ 3

トリボナッチ数列テーブルと答えの確認

「前3つを足すと次の数」というパターンが見えれば、10段まで手計算で求められます。
f(4)＝7（問1の答え）、f(5)＝13（問2の答え）、f(10)＝274（問3の答え）
n（段） f(n)（通り） 計算

💡 算数解法のポイント

  • 「最後の一手」で場合分け：n段目への到達方法は「n−1段目から1段上がる」「n−2段目から2段上がる」「n−3段目から3段上がる」の3通りしかない。重複なく・もれなく数えられる。
  • 前3つを足すと次の数：f(1)＝1, f(2)＝2, f(3)＝4 を出発点に f(n)＝f(n−1)＋f(n−2)＋f(n−3) を繰り返すだけ。電卓なしで f(10)＝274 まで書ける。
  • トリボナッチ数列：前2つを足すフィボナッチではなく、前3つを足すトリボナッチ。1段・2段に加えて3段ジャンプが選べるぶん、増え方がフィボナッチより速い。
  • 樹形図で視覚的確認：少ない段数（3〜4段）の樹形図を描くと、「前3つの葉ノード数を合算する」構造がよくわかる。