フィボナッチの畳屋さん

基本30

　右の図のような、たて2m、横1mの たたみがたくさんあります。これらのたたみを、たて2m横8mの長方形の全面に、すきまができないようにならべてゆきます。たたみのならべ方は何通りありますか。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　

解説
横の長さが2mのときは、下の図のように2通りあり、同じく3mのときは3通りある。

横が4mのときは、下のA図の空いている部分に、上図の3通りのならべ方があり、B図の空いている部分に、上図の2通りのならべ方がある。

以上をまとめると、

横1mのとき　　1通り

横2mのとき　　2通り

横3mのとき　　1＋2＝3通り

横4mのとき　　2＋3＝5通り

横５mのとき　 3＋5＝８通り

横6mのとき　　5＋8＝13通り

横7mのとき　　8＋13＝21通り

横8mのとき　　13＋21＝34通り　　　　　　　　　　答え　34通り

考察

このように、前2つの整数の和で作られる数列をフィボナッチ数列といいます。階段を1段ずつまたは1段とばしで上がる問題でもおなじみですね。2段とばしも加わると前3つの整数の和になります。