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

 日本の畳は,畳の角が交わって十字にならないように畳敷きします.この敷方は「祝儀敷き」と呼ばれます.縁起がよいかどうかは別にして,実際,1点に4枚の畳の角が集まるのは不安定な畳敷きであって,畳の敷き方から除外したいところです.

 ところで,すべての畳敷き集合はヒッカーソンによって特徴づけられていて,対応する母関数はラスキーとウッドコックによって得られている.

  Electronic J Combinatorics 16.1 (2009) #R126

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

【1】畳敷きの母関数

  Tm(z)=ΣT(m,n)z^n=

[1]m=0のとき,1

[2]m=1のとき,1/(1−z^2)

[3]m=2のとき,(1+z^2)1/(1−z−z^3)

[4]mは奇数で,3≦m≦nのとき,

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

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

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

m\n  1  2  3  4  5  6  7  8

1    0  1  0  1  0  1  0  1

2    1  2  3  4  6  9  13  19

3    0  3  0  4  0  6  0  10

4    1  4  4  2  3  3  3  5

5    0  6  0  3  0  2  0  2

6    1  9  6  3  2  2  2  1

7    0  13  0  3  0  2  0  2

8    1  19  10  5  2  1  2  2

[1]4×7の部屋に14枚の畳を敷く場合,その敷き方の数は?

  (1+z)(1+z^2+z^4)/(1−z^3−z^5)

計算は面倒であるが,表より3通り

[2]5×6の部屋に15枚の畳を敷く場合,その敷き方の数は?

  (1+z^4+z^6)/(1−z^4−z^6)

計算は面倒であるが,表より2通り

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