【１】三角形分割数

　（ｎ＋２）角形を三角形分割する方法の数はカタラン数ｃn，したがって，ｎ角形を三角形分割する方法の数はカタラン数

　　ｃn-2＝（２ｎ−４，ｎ−２）／（ｎ−１）

になる．その母関数は

　　ｃ（ｚ）＝｛１−（１−４ｚ）^1/2｝／２ｚ＝Σ（２ｎ，ｎ）ｚ^n／（ｎ＋１）

　多角形を多角形に分割する場合の母関数は

　　ｑ（ｚ）＝｛１＋ｚ−（１−６ｚ＋ｚ^2）^1/2｝／４ｚ

で，ｚ^n-2の係数が，凸ｎ角形の内側に交差しない対角線を引く方法の数になる．しかし、この係数を閉じた形に表すことはできない．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】畳の敷き方数

　２×ｎの長方形に畳を敷き詰める数はフィボナッチ数Ｆnとなる．また，３×ｎの長方形に畳を敷き詰める数は

　　Ｕ2n＝（２＋√３）^n／（３−√３）＋（２−√３）^n／（３＋√３）＝［（２＋√３）^n／（３−√３）］

でフィボナッチ数に類似している．この数は三角数Ｔn＝ｎ（ｎ＋１）／２や五角数Ｐn＝ｎ（３ｎ−２）／２にも関係しているという．

　それにに対して，

［Ｑ］ｎ畳間に畳を敷き詰める方法は何通りあるか（ｎ×２ｍの長方形の部屋にｎ×ｍ枚の畳を敷く場合の敷き方は何通りあるか）

はかなりの難問である．

［Ａ］ｍ＝１の場合はやさしい．ｎ枚の畳を鰻の寝床のように細長いｎ×２の間取りに敷くその敷き方の数Ｆnになる．半畳の正方形の１辺を単位として数えると，敷き方の数はｎを１と２に分割する組み合わせ数（ｎ段の階段を一歩で１段または２段昇ることにする昇り方の数）に一致し，それは

　　Ｆ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（ｌπ／（ｎ＋１））｝

という式が出てくるが，これはフィボナッチ数列の三角関数表現になっているとのことである．

　フィボナッチ数列は指数関数的に増加するから，Ｋ（ｎ×２ｍ）は爆発的に増加するはずである．プログラムは簡単であるから自分で計算してみると

ｍ／ｎ １ ２ ３ ４ ５

１ 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

　ｍ＝２の段を見れば

　　６畳間に畳を敷き詰める方法は１１通り

　　８畳間に畳を敷き詰める方法は３６通り

　　１０畳間に畳を敷き詰める方法は９５通り

あることがわかる．ただし，ここでは回転や鏡映で重なるものを別々のパターンとして数えている．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　フィボナッチ数列の三角関数表現

　　Ｋ（ｎ×２）＝Π(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（ｋπ／（２ｍ＋１））｝

と考えられるのである．１が消えた理由を無理矢理こじつけたようであるが，個数を数えるにはある行列式の固有値を計算する必要があるという．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】レンガの敷き詰め数

　２×１×１のレンガを用いて，２×２×ｎの柱を作る方法は，３×ｎの長方形に畳を敷き詰める問題と似ている．

　　ａn＝（２＋√３）^n+1／６＋（２−√３）^n+1／６＋（−１）^n／３＝［（２＋√３）^n+1／６］

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝