■ポリオミノ(その8)

【1】nオミノ問題

(Q)同じ大きさの正方形の辺と辺をつなげたタイルで,正方形をn枚使ったものをnオミノと呼ぶ.nオミノは何種類あるか?

(A)回転や反転で同型になるものは同じと数えると,モノミノ(1),ドミノ(1),トロミノ(2),テトロミノ(5),ペントミノ(12),ヘキソミノ(35),ヘプトミノ(108),オクトミノ(369),ノノミノ(1285),デコミノ(4655)・・・.別に数えると,モノミノ(1),ドミノ(2),トロミノ(6),テトロミノ(19),ペントミノ(63),ヘキソミノ(216),ヘプトミノ(760),オクトミノ(2725),ノノミノ(9910),デコミノ(36446),・・・

 nオミノの種類はnとともに急速に増加する.前者の個数をPn,後者の個数をQnと表すと

n    Pn     Qn     n    Pn     Qn     

1 1 1 10 4655 36446

2 1 2 11 17073 135268

3 2 6 12 63600 505861

4 5 19 13 238591 1903890

5 12 63 14 901971 7204874

6 35 216 15 3426576 27394666

7 108 760 16 13079255 104592937

8 369 2725 17 50107911 400795860

9 1285 9910 18 192622052 1540820542

 nオミノの数Pnを正確に表すnの式はまだ見つかっていない.

  Pn+1/nPn=Cn

とおくと,C1=1,C2=1,C3=.833,C4=.600,C5=.583,C6=.514,C7=.488,C8=.435,C9=.386となる.

 大きなnに対して

  Qn 〜 a^n  (a=3.72〜4.5)

  Pn 〜 Qn/8

という漸近評価が得られている.

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

【2】クラーナーの定数(1966年)

 クラーナーは

  Pn 〜 K^n

となる定数Kが存在すること=Pnのn乗根が極限をもつことを示した.現在の下限は3.87565,上限は4.649551である.

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