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

 日本の畳は1×2の長方形で,4枚の畳が角で合わないように敷き詰める.その敷き方数についてクヌースは,mが偶数で0≦m−2≦nのとき,

  K(z)=(1+z)^2(z^m-2+z^m)/(1−z^m-1−z^m+1)

と予想した.

 クヌースはthe art of computer programmingなど,大部の文筆家として有名である.その編集作業のために自らTeXを開発したほどである.彼の才能は当該書を読めばすぐわかる.アルゴリズムの性能解析などにそれは現れているが,話題の豊富さに驚かされるだろう.

 mは偶数で,4≦m≦nのとき,

  (1+z)(1+z^m-2+z^m)/(1−z^m-1−z^m+1)

が正しい答えなのであるが,日本の畳の敷き方数についても,ざっとの程度でいいから見積もっただけで,ほぼ正解を得ていたというわけである.

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