From: Noam D. Elkies <elkies@majabberwockyth.harvard.edu>
Newsgroups: rec.puzzles,sci.math
Subject: n-omino enumeration [Re: I need VERY challenging puzzle.....Hows this.....]
Date: 24 Nov 1998 06:31:06 GMT

In article <365A3616.5A5E@starnetinc.com>, R.M. <sparkey@starnetinc.com> wrote:
>Martin Gardner said this has not yet been done and probably is not possible.

>There is [one monomino,] one Dominoe...two Triominoes...five
>quadominoes.... [usually called "tetromino[e]s", as in "tetris" --NDE]
>twelve pentominoes....etc. to infinity. There is no known
>statement that relates the number of (n)ominoes to (n)...
>not counting mirror images or rotations (each in the family
>must be topologically unique). Further... there is no method      
>(program) other than trial and error, brute force, or random 	
>generation and seive.

It's even worse, according to a chapter in _The Mathematical Gardner_
(D.A.Klarner, ed.; Boston : Prindle, Weber, and Schmidt, c.1981)
by Klarner:

Let N(n) be the number of n-ominos.  Let r(n) be the n-th root of N(n).
It is possible, though not easy, to show that there are numbers A,B
with 1<A<B<infinity such that A<r(n)<B for all n>2.  For instance,
one may take B=27/4 (already this is not entirely trivial, and might
keep your cousin occupied for more than the customary few hours).

Experimentally it is observed that r(n) is an increasing function of n.
If this is true then it follows that r(n) approaches a limit, say R,
as n approaches infinity.

As of 1981, it was not proved that r(n) approaches a limit, let alone
that r(n) is increasing.  If the limit R does exist, it was also not
known whether R>4, R<4, or conceivably R=4.  From the information at
http://www.cs.ust.hk/~philipl/omino/bigpolyo.html  it is apparently
now known that R exists and is between 3.9 and 4.65 [the actual
statement there is the much stronger "grows like K^n as n goes to
infinity" but without consulting the source I don't know whether
that's an accurate quotation or a mistranslation of "r(n)^(1/n) -> K"].

I cross-post this to sci.math to find out if anyone there can
provide more recent information on this problem or its variations
and generalizations (polyhexes, polycubes, etc.; symmetric poly-
whatevers; simply connected polyominoes, or ones with a prescribed
number of holes; polyominoes with given area and perimeter; etc.).

--Noam D. Elkies (remove nonsense from e-address to reply)