■漸化式と母関数(その25)

 (その1)を補足.

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

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

 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に対して

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

  Pn 〜 Qn/8

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

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