display | more...
A geometric shape consisting of some number of squares attached at their edges. These are named for the number of squares in the shape, e.g., monomino, domino. triomino, etc.

There is one monomino, a square.

There is one domino, a 1x2 rectangle.

There are two distinct triominoes, a straight chain of three squares, and a bent one. The bent triomino is the basis for Sid Sackson's game Tromino Go.

There are five distinct tetrominoes, or seven if you count reflections as distinct. These seven pieces were the basis for the game Tetris.

There are twelve distinct pentominoes. These pieces are the subject of many games and puzzles (especially tiling puzzles) in recreational mathematics.

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?

Log in or register to write something here or to contact authors.