コラム「パズルワールド散策（その７）」で取り上げた畳敷きの問題（ｎ×２ｍの長方形の部屋にｎ×ｍ枚の畳を敷く場合の敷き方は何通りあるか）において，ｍ＝１の場合はやさしい．
ｎ枚の畳を鰻の寝床のように細長いｎ×２の間取りに敷くその敷き方の数は，半畳の正方形の１辺を単位として数えると，ｎを１と２に分割する組み合わせ数（ｎ段の階段を一歩で１段または２段昇ることにする昇り方の数）に一致する．
それは
Ｆn＝Ｆn-1＋Ｆn-2
の関係になるから，フィボナッチ数列（初項１，第２項２）
１，２，３，５，８，１３，２１，３４，５５，８９，・・・
Ｆn＝１／√５［｛（１＋√５）／２｝^n+1−｛（１−√５）／２｝^n+1］
が現れることになる．
細矢治夫先生によると，この問題は不思議なことに物理学の問題と深く関係しているという．物理学研究者の２つのグループが１９６１年に独立に発表した結果では，
Ｋ（ｎ×２ｍ）＝２^2m[(n+1)/2]Π(k=1~m)Π(l=1~[(n+1)/2]｛ｃｏｓ^2（ｌπ／（ｎ＋１））＋ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
とくにｍ＝１のときは
Ｋ（ｎ×２）＝Π(l=1~[(n+1)/2]｛１＋４ｃｏｓ^2（ｌπ／（ｎ＋１））｝
という式が出てくるが，これはフィボナッチ数列の三角関数表現であることは，コラム「フィボナッチ数列の三角関数表現」で紹介したとおりである．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】畳の敷き方数の一般項
Ｋ（ｎ×２）＝Π(l=1~[(n+1)/2]｛１＋４ｃｏｓ^2（ｌπ／（ｎ＋１））｝
において，ｎ→２ｍと置き換えれば
Ｋ（２ｍ×２）＝Ｋ（２×２ｍ）
＝Π(k=1~m]｛１＋４ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
となる．また，ｎ＝１のとき，畳の敷き方はただ１通りであるから，
Ｋ（１×２ｍ）＝１
１＋４ｃｏｓ^2（ｋπ／（２ｍ＋１））
の１はＫ（１×２ｍ）＝１の場合に対応していて，組み合わせ数の本質的な部分は
４ｃｏｓ^2（ｋπ／（２ｍ＋１））
と思われる．そこで，Ｋ（ｎ×２ｍ）を求めるには１の代わりに
４ｃｏｓ^2（ｌπ／（ｎ＋１））
を用いればよいことになる．
以上のことから，
Ｋ（ｎ×２ｍ）
＝Π(k=1~m)Π(l=1~[(n+1)/2]｛４ｃｏｓ^2（ｌπ／（ｎ＋１））＋４ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
＝２^2m[(n+1)/2]Π(k=1~m)Π(l=1~[(n+1)/2]｛ｃｏｓ^2（ｌπ／（ｎ＋１））＋ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
と考えられるのである．１が消えた理由を無理矢理こじつけたようであるが，・・・
フィボナッチ数列は指数関数的に増加するから，Ｋ（ｎ×２ｍ）は爆発的に増加するはずである．プログラムは簡単であるから自分で計算してみると
ｍ／ｎ １ ２ ３ ４ ５
１ 1 2 3 5 8
２ 1 5 11 36 95
３ 1 13 41 281 1183
４ 1 34 153 2245 14824
５ 1 89 571 18061 185928
ｍ＝２の段を見れば
６畳間に畳を敷き詰める方法は１１通り
８畳間に畳を敷き詰める方法は３６通り
１０畳間に畳を敷き詰める方法は９５通り
あることがわかる．ただし，ここでは回転や鏡映で重なるものを別々のパターンとして数えている．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】畳の敷き方数の数値計算誤差
ｍ，ｎが大きくなるとプログラムの数値計算誤差が顕著になってくる．たとえば単精度で計算した場合，２９６８２．５のような値が出てくるが，これでは２９６８２なのか２９６８３なのか，あるいはもっと違った値になるのか判断できないことになる．
そこで，Ｋ（ｎ×２ｍ）にフィボナッチ数列
Ｆn＝ａＦn-1＋ｂＦn-2 （２項漸化式）
やトリボナッチ数列
Ｔn＝ａＴn-1＋ｂＴn-2＋ｃＴn-3 （３項漸化式）
のような加法的関係，たとえば，
Ｋ（ｎ×２ｍ）＝ａＫ（（ｎ−１）×２ｍ）＋ｂＫ（ｎ×２（ｍ−１））＋ｃＫ（（ｎ−１）×２（ｍ−１））
が成り立てば，Ｋ（ｎ×２ｍ）の値を誤差なく求めることができることになる．
ｎ＝１の場合，畳の敷き方はただ１通りであるから，
Ｋ（１×２ｍ）＝１
ｎ＝２の場合，
Ｋ（２×２ｍ）＝Π(k=1~m)｛１＋４ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
であるから，これはＦ2m（フィボナッチ数列の第２ｍ項）になっていることがわかる．
Ｆ2m＝Ｆ2m-1＋Ｆ2m-2
と順次計算することによって
ｍ／ｎ １ ２
６ 1 233
７ 1 610
８ 1 1597
９ 1 4181
１０ 1 10946
が得られる．
一般に，ｎが偶数のときには
Ｋ（ｎ×２ｍ）＝Ｋ（２ｍ×２（ｎ／２））
という関係が成り立つが，これで得られるＫ（ｎ×２ｍ）はほとんどない．
ｎ＝３，４，・・・の場合はどうだろうか．
Ｋ（３×２ｍ）＝Π(k=1~m)Π(l=1~2)｛４ｃｏｓ^2（ｌπ／４）＋４ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
Ｋ（４×２ｍ）＝Π(k=1~m)Π(l=1~2)｛４ｃｏｓ^2（ｌπ／５）＋４ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
Ｋ（４×２ｍ）−Ｋ（３×２ｍ）＝１６^mΠ(k=1~m)｛（ｃｏｓ^2（π／５）ｃｏｓ^2（２π／５）−ｃｏｓ^2（π／４）ｃｏｓ^2（２π／４）−（ｃｏｓ^2（π／５）＋ｃｏｓ^2（２π／５）−ｃｏｓ^2（π／４）＋ｃｏｓ^2（２π／４）ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
となって，期待しているような簡単な加法的関係にはなりそうにない．
Ｋ（５×２ｍ）＝Π(k=1~m)Π(l=1~3)｛４ｃｏｓ^2（ｌπ／６）＋４ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
Ｋ（６×２ｍ）＝Π(k=1~m)Π(l=1~3)｛４ｃｏｓ^2（ｌπ／７）＋４ｃｏｓ^2（ｋπ／（２ｍ＋１））｝
Ｋ（６×２ｍ）−Ｋ（５×２ｍ）ではなおさらである．ｍ＝２，３，４，・・・としても同様であるから，この数列は加法的ではなく，本質的に乗積的関係にあるのであろう．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝