フィボナッチ数列と置換

━━━━━━━━━━━━━━━━━━━━
数学月間SGK通信 ［2018.10.16］ No.237
<<数学と社会の架け橋＝数学月間>>
━━━━━━━━━━━━━━━━━━━━
フィボナッチ数列というのは，1,1,2,3,5,8,13,....のように続く数列です．
この数列のn項a(n)は，a(n)=a(n-1)+a(n-2)と再帰的に定義できます．
フィボナッチ数列は，様々な分野の思いがけないところで出現します．
この再帰的な機構が支配している現象が様々な分野にあるからです．

集合S(n)=｛1,2,3,....,n｝を考えます．この集合の上の置換を考えます．
置換の結果は，n個の文字の順列になりますから，n!個の置換があります．

さて，文字が始めの位置から移動しない，あるいは，たかだか隣への移動だけが許される
と制限してみます．つまり，どの文字も1つおいた隣以上の移動はしない置換だけを対象にします．
このような置換を，「距離１の置換」と呼ぶことにします．
具体例（次の図）を示すので，「距離１の置換」とは何かは理解できるでしょう．

 Qestion
S(n)上の「距離１の置換」の数をa(n)個とします．ｎ≧1に対してa(n)を求めなさい．
Answer
S(1)に対しては，a(1)=1
S(2)に対しては，a(2)=2
S(3)に対しては，a(3)=3
であることを，確認してください．
次は，a(n)=a(n-1)+a(n-2)が成立することを証明します．
・S(n)の最後のnを動かさない「距離１の置換」の数は，S(n-1)上の「距離1の置換」の数a(n-1)と同じ．
・S(n)で最後のnを動かすとすれば，nの行先はn-1で，空いたnの位置に来れるのはn-1しかありません．
従って，この場合の「距離１の置換」の数はS(n-2)上の「距離１の置換」の数a(n-2)と同じです．

さて，S(n)の最後のnが動くか/動かないかは互いに背反の事象ですから，
両者の和　a(n-1)+a(n-2)がa(n)に等しくなります．（証明終わり）

この式の形は，フィボナッチ数列の定義と同じ形ですから，
a(n)は，第1項が１,第2項が２から始まるフィボナッチ数列になります．