いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

1歩で1段か2段のぼるとき10段の階段をのぼる方法は何通りあるか

 1歩で1段か2段のぼることのできる人が10段の階段をのぼります。何通りののぼり方があるでしょうか。なお、例えば1,1,1,1,2,2,2(1段ずつ4歩、2段ずつ3歩の順にのぼる)と1,2,1,2,1,2,1(1段、2段、1段、2段、……)は区別します。

 解き方はいくつかあります。例えば、

①2段ずつ5歩

②2段ずつ4歩、1段を2歩

③2段ずつ3歩、1段を4歩

……

で②は何通りか考えます。2を4個、1を2個並べて何通りの順列ができるか、言い方を変えると「単語」がいくつできるか求めればよいので、同じものを含む順列の公式から

f:id:Inuosann:20200607184020p:plain

(6個の数字があり、内訳は2が4個、1が2個)

通り。③も④も同様に考えます。

 もうひとつ、ちょっと面白い方法を。n段のぼるのにf(n)通りののぼり方があるとします。今、知りたいのはf(10)です。ところで例えばf(5)=f(4)+f(3)です。なぜか。5段上る方法は大きく分けて2通り。ひとつは最初に1段のぼってあと4段のぼる方法、そしてもうひとつは最初に2段のぼってあと3段のぼる方法です。前者はf(4)通り、後者はf(3)通りのはずなのでf(5)=f(4)+f(3)ということになります。f(1)=1、f(2)=2ですから(f(2)は1段、1段とのぼるか、2段を1回でのぼるかで2通り)、f(3)=f(2)+f(1)=2+1=3。f(4)=f(3)+f(2)=3+2=5。f(5)=f(4)+f(3)=5+3=8。……と順に計算して、結局f(10)=f(9)+f(8)=55+34=89通りとなります。

 プログラミングで言うと「再帰的なプログラム」みたいな感じで、ちょっと面白い気がします。f(10)を計算するのに最初の解き方のような、f(10)の言わば中身に立ち入って考える、ということをしないんですね。階乗の計算でも、g(n)=n!として例えばg(10)を求めたいときは、g(9)を求めてそれに10をかければよいのです。g(10)=10×g(9)=10×9×g(8)=……とすればg(10)を求められます。

  最初の問題ではf(n)=f(n-1)+f(n-2)が成立するのでした。こんなのを漸化式と呼びます。これは隣合う3項間の漸化式。漸化式を使う問題で、「どの2本も平行でないn本の直線が平面を何個の領域に分けるか」など、面白いものが他にもあります。高校のときにはこうした問題が新鮮に見えました。