フィボナッチ数列の問題。

「15段の階段があります。この階段を昇るのに一歩、または二歩（一段とばし）でしか昇れません。
この時の昇り方の総数は？？」

この問題について、数学の初学者にも分かるような解説をいただけませんか。

数列の問題、ということはかろうじて判断できますが、答えを聞いても、自分では導けません。。
ちなみに文系クラスで数列を学んだのが約１０年前
で、それ以来一切数学に触れていない、というレベルです。

No.5 回答者： kapura 回答日時： 2006/04/20 02:08

# 数列だとか変に数学用語を意識する必要はないと思います

n段の階段の場合の上り方をリストで表して、それら全リストを@nと表すことにします。例えば、2段の階段では、まず1段、次に1段という上り方と、一気に2段という上り方があるので、@2: [1, 1], [2] という風に表します。次のようにnが小さい場合から考えていくと、規則性が見えてくると思います。必要ならば、階段の図を描いて考えるといいでしょう。

@1: [1]
@2: [1, 1], [2]
@3: [1, 1, 1], [1, 2], [2, 1]
@4: [1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]
@5: [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [1, 2, 2], [2, 1, 1, 1], [2, 1, 2], [2, 2, 1]

こうやって見ていくと@nは、@n-1の各リストの左端に1をつけ加えてできるリストと、@n-2の各リストの左端に2をつけ加えてできるリストであるという規則性がわかってくると思います。どうしてこうなるかを少し考えれば、n段の場合の第1歩目が決まれば、残りはその第1歩目に応じて残りn-1段かn-2段であり、それは既に全ての上り方がわかっている @n-1、@n-2 の結果を使えばいいからだとわかると思います。

@n: [1, ...], ..., ← @n-1のリストの左端に1をつけ加えたもの
　　[2, ...], ... ← @n-2のリストの左端に2をつけ加えたもの

これはNo.2の方と同じ見方をした説明ですが、No.4の方のように最後に1段か2段を残す上り方という風に考えて、@n-1の各リストの右端に1をつけ加えるのと、@n-2の右端に2をつけ加えたものと考えてもいいでしょう。No.1の方の説明はnが1と2だけを使って何通りの足し算で表現できるかという見方で、場合分けをしてそれぞれで足し算の並び順を変えて数え上げていますが、既にわかっている@n-1と@n-2の足し算方法を使えばいいと考えた方が簡単だと思います。どの考え方をしても結果的に同じ@nが得られるのがわかるでしょう。

解答としては具体的な上り方まで必要なくて、@nのリストの総数でいいので、それをf(n)で表せば、f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 8, ...、つまり f(n) = f(n-1) + f(n-2) となります。問題はf(15)を求めればいいわけですが、順にf(15)までf(n) = f(n-1) + f(n-2)を使って筆算すればいいでしょう。もっと大きなnだと、コンピュータを使うとか別の方法を考えないとやってられない計算ですね。

別に問題を解くのに用語を知っている必要はないですが、他の方も言われているように、このリストの総数を並べた数列はフィボナッチ数列と言われるものです。
http://mathworld.wolfram.com/FibonacciNumber.html

# この話を発展させて、もし2段とばしも認めるとすると、いわゆるトリボナッチ数列になると思います。もちろん、3段とばしも認めれば、テトラナッチ数列、・・・。
http://mathworld.wolfram.com/TribonacciNumber.html
http://mathworld.wolfram.com/TetranacciNumber.html
http://mathworld.wolfram.com/Fibonaccin-StepNumb …


# 以下ははぼやきです。
# マルチポストで消されるなんてことがあるなんて、唖然。初体験です。
# 消す作業は自動的にやっているのか手動でやっているのか知らないけど、いずれにしても変。
# 自動的にやるなら質問投稿時に重複を確認しないのはなぜだろう？
# 手動ならなぜ回答が多い方を消したのかな？間違えて消したなら取り消せるだろうし。
# 単純に回答をつなぎ合わせることくらいできないのかな？
# 付加した回答にはそれとわかる印を付けてもいいし。
# そんなに難しいプログラミングとは思えないんだけど。
# もう自動でコピーしてよ。手動でまた同じこと書くのはうんざりする作業。ブツブツ。

No.4 回答者： nekochari 回答日時： 2006/04/17 21:37

マルチポストの被害に遭うのはこれで２回目です。

以下再度記入です（サイト側が全文メールで返送してくれたので有難いです）。下記の#3さんがと書いてあるのは、削除された方の質問への回答ですので、こちらの方の回答#3ではないです。
--------------------------------
f(n)=f(n-1)+f(n-2) というような式を漸化式といいますが、この問題の場合、この漸化式の立て方はすごく単純です。

たとえば、５段目まで昇る場合の数をf(5)と書くとして、考えると、５段目まで昇る場合の数は、４段目まで昇ってから１段さらに昇るか、３段目まで昇ってから一気に２段上るかの二通りの場合の合計ですから、f(4)+f(3)となります。n段目f(n)を考えるとその一段下まで昇ってから１段上る場合f(n-1)と二段下まで昇ってから２段上る場合f(n-2)の合計ですから、f(n)=f(n-1)+f(n-2)となります。
　漸化式を使ってf(n)を求める場合、初期値が必要です。
　１段目まで昇る場合の数f(1)は１、２段目まで昇る場合の数は１段ずつ２階昇る場合と、一気に２段上る場合の２通りで２、ですから、f(1)=1、f(2)=2ですね。
　これで条件が整いました。
　f(1)=1、
　f(2)=2、
　f(n)=f(n-1)+f(n-2)
これで、nを２から１つずつ増やしながら計算するとどんなnについても計算できます。（時間と根気があればですが）
　この、f(n)=f(n-1)+f(n-2) において、f(1)=1、f(2)=1 の場合がフィボナッチ数列として有名です。いろいろと美しい関係があり、また自然界にもこの数列に従った値をとるものがいろいろあるそうです。
　なお、フィボナッチ数列の場合には、順番に計算しなくても、n の値から一気に答えを求める数式もあります。#3 さんがお書きになっていますが、計算式にはルートが入っているのに、計算していくと全部ルートが消えて整数になるのは何やら感動的です。
-------------------------
　f(1)=1、f(2)=1 から始まるフィボナッチ数列の一般項f(n)は、
　{ ( (1 + √5) / 2 )^n - ( (1 - √5) / 2 )^n } / √5
です。

No.3 回答者： sanori 回答日時： 2006/04/16 21:02

折角の、ご質問の題目が正しくて、私のようなド素人でない有識者の回答が沢山ぶら下がってたほうが、マルチポストの為に消えちゃいましたね。

（笑）

Ｎｏ．１の私の回答は、下記の通り、差し替えたこととして読んでくださいませ。＞皆様


> ■回答 ［ 2006-04-16 02:01 sanori ］
> こういう問題、初めて見ます。
> フィボナッチ数列という言葉は知ってます。
> １　１　２　３　５　８　１３　２１　・・・・・
> ですよね？
> 小さい子供が読む数学絵本にも載ってました。
> 自然界の現象、例えば、木の葉っぱの数と関連があるらしい話も聞いています。
>
> しかし、この問題との関連は知りません。
> ですが、やってみます。
（以降は同じ）

No.2 回答者： moritan2 回答日時： 2006/04/16 20:30

n段の階段の上り方の組み合わせ数を f(n) とします。

最初の一歩は１段か２段のどちらかで、最初の一歩が１段の時は残り n-1段なので f(n-1) 通りの組み合わせが可能です。また、最初の一歩が二段の時は残り n-2段なので f(n-2) 通りの組み合わせが可能です。両方を合計すると、

f(n)=f(n-1)+f(n-2)

となります。これはまさにフィボナッチ数列です。

0段、1段では選択の余地がないので、

f(0)=1
f(1)=1

あとは一つ前と２つ前をたして、

f(2)=2
f(3)=3
f(4)=5
f(5)=8
f(6)=13
f(7)=21
f(8)=34
f(9)=55
f(10)=89
f(11)=144
f(12)=233
f(13)=377
f(14)=610
f(15)=987
f(16)=1597
f(17)=2584
f(18)=4181
f(19)=6765
f(20)=10946
f(21)=17711
f(22)=28657
f(23)=46368
f(24)=75025
f(25)=121393
f(26)=196418
f(27)=317811
f(28)=514229
f(29)=832040
f(30)=1346269
f(31)=2178309
f(32)=3524578
f(33)=5702887
f(34)=9227465
f(35)=14930352
f(36)=24157817
f(37)=39088169
f(38)=63245986
f(39)=102334155

f(15)=987なので、答えは987です。

No.1 回答者： sanori 回答日時： 2006/04/16 01:57

こういう問題、初めて見ます。

フィボッチ数列という言葉も知りません。
しかし、やってみます。

１．
２歩の回数は、どのような種類あるか？
それを全部列挙します。
Ａ　０回　＝　２歩０回、１歩１５回
Ｂ　１回　＝　２歩１回、１歩１３回
Ｃ　２回　＝　２歩２回、１歩１１回
Ｄ　３回　＝　２歩３回、１歩９回
Ｅ　４回　＝　２歩４回、１歩７回
Ｆ　５回　＝　２歩５回、１歩５回
Ｇ　６回　＝　２歩６回、１歩３回
Ｈ　７回　＝　２歩７回、１歩１回


２．
上記それぞれ個別に、何通りの歩き方があるかを計算。

Ａ　＝　１通り　　これは、簡単。

次からが問題。

Ｂ
トランプのような数字カードがあり、「２」のカードが１枚、「１」のカードが１３枚。
これを１列に並べるとき、並べ方の場合の数は
14Ｐ14 ÷ 1Ｐ1 ÷ 13Ｐ13 ＝ １４！÷１！÷１３！ ＝ １４

なぜか13Ｐ13で割るかというと、１のカード１３枚は相互に取り替えてもよいから。
（取り替え方の種類は、１３枚使って１３枚全部を並べる順列なので）

Ｃ
１３！ ÷ ２！ ÷ １１！ ＝ １３×１２÷２ ＝

Ｄ
１２！ ÷ ３！ ÷ ９！ ＝ １２×１１×１０÷３÷２ ＝

・・・・・

Ｇ
９！ ÷ ６！ ÷ ３！ ＝ ９×８×７÷３÷２ ＝

Ｈ
８！ ÷ ７！ ÷ １！ ＝ ８

以上を全部足したものが、答えになりそうです。


私は計算は苦手ですが、計算をしなくても良く、式だけ示せばよい問題であるならば、

１つの式で書けば、

Σ(n=0→7) ［（１５－ｎ）！÷ｎ！÷（１５－２ｎ）！］

が答えとなりそうですね。