Counting Polyominoes

Definitions and mathematical statement

A polyomino of order $n$ is the union of $n$ distinct unit squares $[i,i+1]\times[j,j+1]$, with $(i,j)\in\mathbb Z^2$, such that their edge-adjacency graph is connected. Meeting at a corner alone does not give adjacency. Holes are permitted unless an additional restriction is explicitly imposed.

Let $t_n$ count these objects up to translation only. Let $c_n$ count them up to translations and rotations through multiples of $\pi/2$, and let $f_n$ also identify reflections. These are respectively the fixed, one-sided (called chiral in the source), and free conventions. Determine exact general counting formulas and sharp asymptotics for these sequences.

In particular, determine the growth constant \[ \lambda=\lim_{n\to\infty} t_n^{1/n}, \] and the finer subexponential behavior of $t_n$. The limit is a growth rate per added square: its defining relation is $\log t_n/n\to\log\lambda$, not a polynomial-growth claim $t_n\approx n^\lambda$. Enumerating finitely many values does not determine this asymptotic quantity. The conventions also matter for exact counts: symmetric polyominoes have smaller rotation or reflection orbits, so the three sequences cannot be obtained by dividing every term by four or eight.

Short English statement

Count connected collections of grid squares, distinguishing rotations and reflections correctly, and determine their exponential growth rate and finer asymptotics.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500037 (AMR-054-0037), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 37. Original source indexed by AMR-054-0037. https://topp.openproblem.net/p37.