ニコリのパズルを解いていたら思いついた、たぶん有名な問題。
1)n個の正方形の辺と辺をくっつけてできた図形は、何通りあるか。
ただし
- 辺と辺は頂点と頂点がくっつくようにつける。
- 回転したり裏返したりして同じ形になるものは同じと見なす
- 正方形は互いに重ならない
2)上記の図形を n について列挙するプログラムを書け
n=1, 2 なら、1通り。
n=3 なら、 2通り。
n=4 なら、LITSO の5通り
n=5 なら、12通り。ここまでは有名または自明。
以下、http://www.yotor.com/wiki/en/po/Polyomino.htm によると、
n=6 なら、35通りらしい。
n=7 なら、108通りらしい。煩悩の数と同じだ。
n=8 なら、369通りらしい。
n=9 なら、1285通りらしい。
n=10 なら、4655通りらしい。
n=11 なら、17073通りらしい。
n=12 なら、63600通りらしい。
n=13 なら、238591通りらしい。（10/12 追記：jmuk さんのコメントによる）
行きがかり上発見した http://www.yotor.com/wiki/en/po/Polyomino.htm を見た感じでは、各項を表す具体的な式は見つかってないらしいが、見積もりはできているようである。
検索してみると、なぜかどのページも n=12/dodecomino でやめていて、n=13/tridecomino*1 の計算をしていない。というわけで、n=13とそれより上の計算をすれば世界一詳しいサイトになれるのかもしれない。
しかし、n=13 だと、ざっと 40万通り。n=14なら120万通りとなる。これは ruby には荷が重いかも。
*1:この綴りであっているのかどうか、非常に心許無い
