■ドミノ被覆・畳被覆(その3)

【1】畳の敷き方数の一般項

  K(n×2)=Π(l=1~[(n+1)/2]{1+4cos^2(lπ/(n+1))}

において,n→2mと置き換えれば

  K(2m×2)=K(2×2m)

 =Π(k=1~m]{1+4cos^2(kπ/(2m+1))}

となる.また,n=1のとき,畳の敷き方はただ1通りであるから,

  K(1×2m)=1

  1+4cos^2(kπ/(2m+1))

の1はK(1×2m)=1の場合に対応していて,組み合わせ数の本質的な部分は

  4cos^2(kπ/(2m+1))

と思われる.そこで,K(n×2m)を求めるには1の代わりに

  4cos^2(lπ/(n+1))

を用いればよいことになる.

 フィボナッチ数列は指数関数的に増加するから,K(n×2m)は爆発的に増加するはずである.プログラムは簡単であるから自分で計算してみると

m/n 1 2 3 4 5

1 1 2 3 5 8

2 1 5 11 36 95

3 1 13 41 281 1183

4 1 34 153 2245 14824

5 1 89 571 18061 185928

 m=2の段を見れば

  6畳間に畳を敷き詰める方法は11通り

  8畳間に畳を敷き詰める方法は36通り

  10畳間に畳を敷き詰める方法は95通り

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

===================================