Polyominoes
A polyomino is an n-celled "animal" composed of squares connected
at their edges. A set of polyominoes can be "free",
"one-sided", or "fixed", the distinction being the
conditions under which two polyominoes are considered distinct. Here I'll
explain these distinctions, and illustrate them using the 4-polyominoes, or
tetrominoes.
When polyominoes are mentioned without qualification, it is usually a
reference to "free" polyominoes. A free polyomino is considered
unchanged by rotation and reflection. OEIS A000105
gives the number of n celled free polyominoes. Note that the first three
tetrominoes pictured here have bilateral symmetry, while the last two do
not. Note that the axis of bilateral symmetry can be vertical, horizontal,
or diagonal. OEIS A030228
gives the number of n celled free polyominoes lacking bilateral symmetry.
|
The five free tetrominoes
|
A "one-sided" polyomino is considered unchanged by rotation, but
not by reflection. In other words, two distinct one-sided polyominoes can
be mirror images of one another. OEIS A000988
gives the number of n celled one-sided polyominoes. The set of one-sided
polyominoes of a given size consists of the free polyominoes plus the mirror
images of the polyominoes lacking bilateral symmetry. In other words, the
number of free polyominoes plus the number of free polyominoes lacking bilateral symmetry equals the number of one-sided polyominoes.
That is, A000105(n) + A030228(n) = A000988(n). The distinction between one-sided and free polyominoes isn't important for
1-, 2-, and 3-celled polyominoes because all of these small pieces have
bilateral symmetry. This distinction becomes important only for 4-celled
and larger polyominoes.
|
The seven one-sided tetrominoes
|
Rotations and reflections of "fixed" polyominoes are
considered distinct. OEIS A001168
gives the number of n celled fixed polyominoes.
|
|
|
The 19 fixed tetrominoes. For each free
tetromino (left
column), I count the number of reflections (1 if there is
bilateral symmetry; 2 otherwise) and rotations
(1, 2, or 4 depending on radial symmetry). |
|
"Positionings" of fixed n celled polyominoes within an n by
n square is a concept I think I invented. It comes in handy in the
calculation of the number of ways to combine n one-sided n-polyominoes to make
an n by n square. There are 6 ways to position the fixed "T"
tetromino  in
a 4 by 4 square. In general, the number of positionings in an n by n
square of a p by q fixed n-polyomino (the smallest enclosing rectangle has p
rows and q columns) is (n-p+1)(n-q+1). OEIS doesn't contain the
sequence of positionings, which for n=0, 1, 2, ... starts 1, 1, 4, 22, 113, ...
Polyomino Tables
For each n, I will present a table of information about n-polyominoes.
The first column gives pictures of all the free
n-polyominoes. Some rows will have more several similar
polyominoes.
|
Free gives the number of free polyominoes presented in this
row.
|
1-sided is the number of different ways to reflect the
polyomino -- 1 if it has bilateral symmetry, and 2 otherwise.
|
Rotations is the number of different ways to rotate the
polyomino -- 1, 2, or 4 depending on its radial symmetry.
|
Fixed is the number of fixed polyominoes, which is Free *
Reflections * Rotations.
|
Size is the number of rows and columns of the smallest
rectangle that can contain the polyomino.
|
Positionings each is the number of different ways to
position each fixed n-polyomino in an n by n square. Where the
size is p by q, positionings each = (n-p+1)(n-q+1).
|
Positionings is the number of positionings of fixed
polyominoes. Positionings = fixed * positionings each.
|
0-polyomino
By convention, there is one 0-polyomino.
| 0-polyomino |
Free |
1-
sided |
Rota-
tions |
Fixed |
Size |
Position-
ings each |
Position-
ings |
| |
1 |
1 |
1 |
1 |
0 x 0 |
1 |
1 |
| Total |
1 |
1 |
|
1 |
|
|
1 |
1-polyomino
| 1-polyomino |
Free |
1-
sided |
Rota-
tions |
Fixed |
Size |
Position-
ings each |
Position-
ings |
 |
1 |
1 |
1 |
1 |
1 x 1 |
1 |
1 |
| Total |
1 |
1 |
|
1 |
|
|
1 |
2-polyomino (domino)
| 2-polyomino |
Free |
1-
sided |
Rota-
tions |
Fixed |
Size |
Position-
ings each |
Position-
ings |
 |
1 |
1 |
2 |
2 |
1 x 2 |
2 |
4 |
| Total |
1 |
1 |
|
2 |
|
|
4 |
3-polyominoes
| 3-polyominoes |
Free |
1-
sided |
Rota-
tions |
Fixed |
Size |
Position-
ings each |
Position-
ings |
 |
1 |
1 |
2 |
2 |
1 x 3 |
3 |
6 |
 |
1 |
1 |
4 |
4 |
2 x 2 |
4 |
16 |
| Total |
2 |
2 |
|
6 |
|
|
22 |
4-polyominoes (tetrominoes, Tetris pieces)
| Tetromino |
Free |
1-
sided |
Rota-
tions |
Fixed |
Size |
Position-
ings each |
Position-
ings |
 |
1 |
1 |
4 |
4 |
2 x 3 |
6 |
24 |
 |
1 |
1 |
2 |
2 |
1 x 4 |
4 |
8 |
 |
1 |
1 |
1 |
1 |
2 x 2 |
9 |
9 |
 |
1 |
2 |
2 |
4 |
2 x 3 |
6 |
24 |
 |
1 |
2 |
4 |
8 |
2 x 3 |
6 |
48 |
| Total |
5 |
7 |
|
19 |
|
|
113 |
5-polyominoes
| Pentominoes |
Free |
1-
sided |
Rota-
tions |
Fixed |
Size |
Position-
ings each |
Position-
ings |
 |
1 |
1 |
1 |
1 |
3 x 3 |
9 |
9 |
 |
1 |
1 |
2 |
2 |
1 x 5 |
5 |
10 |
 |
1 |
1 |
4 |
4 |
2 x 3 |
12 |
48 |
   |
3 |
1 |
4 |
12 |
3 x 3 |
9 |
108 |
 |
1 |
2 |
2 |
4 |
3 x 3 |
9 |
36 |
 |
1 |
2 |
4 |
8 |
2 x 3 |
12 |
96 |
  |
3 |
2 |
4 |
24 |
2 x 4 |
8 |
192 |
 |
1 |
2 |
4 |
8 |
3 x 3 |
9 |
72 |
| Total |
12 |
18 |
|
63 |
|
|
571 |
6-polyominoes
7-polyominoes
. . . . . . . maybe I'll add a table for 7-polyominoes at a later date
Internet References
Tetriswiki: Square_Platforming
OEIS: A000105
— number of polyominoes with n cells - 1, 1, 1, 2, 5, 12, 35, ...
OEIS: A000988
— number of one-sided polyominoes with n cells - 1, 1, 1, 2, 7, 18, 60, ...
OEIS: A001168
— number of fixed polyominoes with n cells - 1, 1, 2, 6, 19, 63, 216, ...
Wikipedia: Polyomino is
a clear description of polyominoes — free, one-sided, and fixed.
Related pages in this website
Go Up to Counting
Tetris enumerates the ways to tile an
n-by-n square by one-sided n-polyominoes
|
