問題概略
8 段の階段を次のような方法で登ります。登り方は何通りあるでしょうか。
- 「一歩で 1 段」「一歩で 2 段」「一歩で 3 段」の 3 通りの登り方ができる
- 使わない登り方があってもよい
- 「一歩で 2 段」は連続しない
- 「一歩で 3 段」も連続しない
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
漸化式を立てる
フィボナッチっぽい問題ですね。最後の一歩に注目して漸化式を立てます。
段登るとして最後の一歩が 1, 2, 3 段の方法がそれぞれ
,
,
通りあるとします。
\begin{array}{l}
a_{n}=a_{n-1}+b_{n-1}+c_{n-1}\mbox{ ……(1)}\\
b_{n}=a_{n-2}+c_{n-2}\mbox{ ……(2)}\\
c_{n}=a_{n-3}+b_{n-3}\mbox{ ……(3)}\\
a_1=1,\, b_1=0,\, b_2=1,\, c_1=c_2=0,\, c_3=1\mbox{ ……(4)}
\end{array}
とおくと答えは
です。表のようになって答えは「55 通り」でした。
fn だけの式にする
(1)～(5)から の漸化式を導けます。
まず(1)と(5)から得られる を使って(2)(3)を書き直します。
\begin{array}{l}
b_{n}=f_{n-3}+c_{n-2}\mbox{ ……(7)}\\
c_{n}=f_{n-4}+b_{n-3}\mbox{ ……(8)}
\end{array}
(6)～(8)を辺ごとに足します。
\begin{align*}
f_{n}&=f_{n-1}+f_{n-3}+f_{n-4}+b_{n-3}+c_{n-2}\\
&=f_{n-1}+f_{n-3}+f_{n-4}+(f_{n-6}+c_{n-5})+(f_{n-6}+b_{n-5})\\
&=f_{n-1}+f_{n-3}+f_{n-4}+2f_{n-6}+b_{n-5}+c_{n-5}
\end{align*}
これに を使うと 7 項間漸化式が導けます。
ただ，これを手計算には向かないですね。これはプログラムを組んで解くとき向きの関係式です。
～
を求めるのに
などを使って，その後は(9)を使う mathematica のコードを書いてみました。
程度だと
～
を使うのとほぼ同じ計算時間ですが，
がある程度大きくなるとこちらの方が速くなります。
In[]:= AbsoluteTiming[
nmax = 8;
a[1] = 1;
b[1] = 0; b[2] = 1;
c[1] = 0; c[2] = 0; c[3] = 1;
a[n_] := a[n] = a[n - 1] + b[n - 1] + c[n - 1];
b[n_] := b[n] = a[n - 2] + c[n - 2];
c[n_] := c[n] = a[n - 3] + b[n - 3];
Do[f[k] = a[k] + b[k] + c[k], {k, 6}];
f[n_] := f[n] = f[n - 1] + f[n - 3] + f[n - 4] + f[n - 5] + f[n - 6];
ans = f[nmax]]
Out[]= {0.0000723, 55}
