next up previous
Next: Problem 38: Compatible Triangulations Up: The Open Problems Project Previous: Problem 36: Inplace Convex


Problem 37: Counting Polyominoes

Statement
How many polyominoes on n squares are there? A polyomino is a connected interior-disjoint union of axis-aligned unit squares joined edge-to-edge, in other words, an edge-connected union of cells in the planar square lattice. The order of a polyomino is the number of unit squares forming it. The problem asks for the number of polyominoes of order n. The key constraint here is that polyominoes must be edge-connected. There are three variations on the problem, depending on whether two polyominoes are considered equivalent by factoring out just translations (fixed polyominoes), rotations and translations (chiral polyominoes), or reflections, rotations, and translations (free polyominoes).
Origin
To quote Klarner [Kla97]: ``Polyominoes have a long history, going back to the start of the 20th century, but they were popularized in the present era initially by Solomon Golomb, then by Martin Gardner in his Scientific American columns.''
Status/Conjectures
Open.
Partial and Related Results
Asymptotically, results of Klarner et al. [Kla97, Thm. 12.3.1] show that the number of fixed n-ominoes (factoring out just translations), denoted t(n), satisfies

$\displaystyle \lim_{{n \to \infty}}^{}$[t(n)]1/n = λ

(roughly, t(n) is around nλ) for ``Klarner's constant" λ, with 4.0025 < λ < 4.5685, but the precise value of λ remains open. The lower bound of > 4 is established in [BRS15], and the upper bound in [BB15].

The exact counts have been computed for small n. See [Sloa] for the number of fixed n-ominoes for n≤28 and for related references. The current record is n = 56 by Jensen [Jen03]. See also [Epp] for related links.

Related Open Problems
There are many related problems involving polyominoes with restricted geometric shapes (e.g., [Slob]), polyiamonds (edge-to-edge unions of unit equilateral triangles), polyhexes (edge-to-edge unions of unit regular hexagons), polyabolos (edge-to-edge unions of unit right isosceles triangles), polycubes (face-to-face unions of unit cubes), etc. All of these problems are also open.
Appearances
[Kla97]
Categories
combinatorial geometry
Entry Revision History
E. Demaine & J. O'Rourke, 30Nov2001; E. Demaine, 28Aug2002; G. Barequet, 4Dec2015.

Bibliography

BB15
Gill Barequet and Ronnie Barequet.
An improved upper bound on the growth constant of polyominoes.
Electronic Notes in Discrete Mathematics, 49:167-172, 2015.

BRS15
Gill Barequet, Günter Rote, and Mira Shalah.
λ> 4.
Comm. ACM, 2015.
Accepted.

Epp
David Eppstein.
Polyominoes and other animals.
http://www1.ics.uci.edu/~eppstein/junkyard/polyomino.html.

Jen03
Iwan Jensen.
Counting polyominoes: A parallel implementation for cluster computing.
In Computational Science—ICCS 2003, pages 203-212. Springer, 2003.

Kla97
David A. Klarner.
Polyominoes.
In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 12, pages 225-242. CRC Press LLC, Boca Raton, FL, 1997.

Sloa
Neil J. A. Sloane.
Sequence A000105.
https://oeis.org/A000105.

Slob
Neil J. A. Sloane.
Sequence A204804.
https://oeis.org/A204804.


next up previous
Next: Problem 38: Compatible Triangulations Up: The Open Problems Project Previous: Problem 36: Inplace Convex
The Open Problems Project - December 04, 2015