Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Counting > Polyominoes

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.

Tetromino Reflec-
tions
Rota-
tions
Fixed  Fixed Tetrominos
1 4 4      
1 2 2  
1 1 1
2 2 4  

 

2 4 8      

     

Total     19  19

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, ...

Tetromino Reflec-
tions
Rota-
tions
Fixed Size Position-
ings each
Position-
ings
1 4 4 2 x 3 6 24
1 2 2 1 x 4 4 8
1 1 1 2 x 2 9 9
2 2 4 2 x 3 6 24
2 4 8 2 x 3 6 48
Total     19     113

There are 113 "positionings" of fixed tetrominoes within a
4 by 4 square

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

Hexominoes Free 1-
sided
Rota-
tions
Fixed Size Position-
ings each
Position-
ings
1 1 2 2 1 x 6 6 12
1 1 2 2 2 x 3 20 40
   2 1 4 8 2 x 4 15 120
1 1 4 4 2 x 5 10 40
     3 1 4 12 3 x 3 16 192
   2 1 4 8 3 x 4 12 96
1 2 2 4 2 x 4 15 60
1 2 2 4 2 x 5 10 40
     3 2 2 12 3 x 4 12 144
     3 2 4 24 2 x 4 15 360
     3 2 4 24 2 x 5 10 240
       4 2 4 32 3 x 3 16 512
    

     

   

10 2 4 80 3 x 4 12 960
Total 35 60   216     2816

 

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

Tetris enumerates the ways to tile an n-by-n square by one-sided n-polyominoes

Tetromino Soup is a puzzle asking for the probability of forming each of the five free tetrominoes by a random walk

 

The webmaster and author of this Math Help site is Graeme McRae.