How many distinct
n-
square polyominoes are there? This is actually an
open problem of
statistical mechanics!
For concreteness, we'll consider polyominoes distinct if they're (nonsymmetrical) reflections; this can only throw our count off by a factor of 2, of course. These are also called "animals".
There are exponentially many n-square polyominoes. Indeed, if we pick a square and proceed (for n-1 steps) by picking either the next square up or the next square right, we'll get 2n-1 polyominoes that are distinct, except maybe they can be rotated onto each other. So there are at least 2n-3 polyominoes -- exponentially many.
On the other hand, note that every self-avoiding walk on the lattice has a polyomino as its image, so there are no more than 4×3n-1 polyominoes.
We'd like to say there are Θ(bn) polyominoes; what is b?