■いろいろの漸化式と母関数(その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
という漸近評価が得られている.
===================================