順列生成（応用）問題（４）の考察２

　順列生成（応用）問題（４）の考察２を示します。

問題（４）考察２

　集合{1,2,...,n}上のフィボナッチ順列の個数をf(n)とする。

求める順列において、p(n)=n　または、p(n)=n-1が成り立つ。

そこで、求める順列をp(n)=nとp(n)=n-1で分類する。

前者は、f(n-1)個、後者は、p(n-1)=nとなるので、f(n-2)個となる。

したがって、

　　f(n) = f(n-1) + f(n-2) (n≧3)　f(1)=1, f(2)=2

を得る。これは、フィボナッチ数である。