Report Number: CS-TR-72-263
Institution: Stanford University, Department of Computer Science
Title: A procedure for improving the upper bound for the number of n-ominoes.
Author: Klarner, David A.
Author: Rivest, Ronald L.
Date: February 1972
Abstract: An n-omino is a plane figure composed of n unit squares joined together along their edges. Every n-omino is generated by joining the edge of a unit square to the edge of a unit square in some (n-1)-omino so that the new square does not overlap any squares. Let t(n) denote the number of n-ominoes, then it is known that the sequence \${((t(n))}^{1/n} : n = 1,2,\ldots )\$ increases to a limit \$\Theta\$ , and 3.72 < \$\Theta\$ < 6.75 . A procedure exists for computing an increasing sequence of numbers bounded above by \$\Theta\$. (Chandra recently showed that the limit of this sequence is \$\Theta\$ .) In the present work we give a procedure for computing a sequence of numbers bounded below by \$\Theta\$ . Whether or not the limit of this sequence is \$\Theta\$ remains an open question. By computing the first ten terms of our sequence, we have shown that \$\Theta\$ < 4.65 .
http://i.stanford.edu/pub/cstr/reports/cs/tr/72/263/CS-TR-72-263.pdf