フィボナッチ数が現れる問題（２）の解

フィボナッチ数が現れる問題（２）の解答例を示します。

(２)の解

　明らかに、b(1)=1，b(2)=2である。求める順列は、p(n)=nを満たす順列とp(n)=n-1,p(n-1)=nを満たす順列に分類できる。
前者の個数がb(n-1)、後者の個数がb(n-2)である。したがって、

　　b(n)= b(n-1)+ b(n-2)　(n≧3)

が成り立つ。