Octomino

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The 369 free octominoes

An octomino (or 8-omino) is a polyomino of order 8, that is, a polygon in the plane made of 8 equal-sized squares connected edge-to-edge.[1] The name of this type of figure is formed with the prefix oct(a)-. When rotations and reflections are not considered to be distinct shapes, there are 369 different free octominoes. When reflections are considered distinct, there are 704 one-sided octominoes. When rotations are also considered distinct, there are 2,725 fixed octominoes.[2][3]

Symmetry[edit]

The figure shows all possible free octominoes, coloured according to their symmetry groups:

  • 316 octominoes (coloured grey) have no symmetry. Their symmetry group consists only of the identity mapping.
  • 23 octominoes (coloured red) have an axis of reflection symmetry aligned with the gridlines. Their symmetry group has two elements, the identity and the reflection in a line parallel to the sides of the squares.
Reflection symmetrical octominoes 90 deg.svg
  • 5 octominoes (coloured green) have an axis of reflection symmetry at 45° to the gridlines. Their symmetry group has two elements, the identity and a diagonal reflection.
Reflection symmetrical octominoes 45 deg.svg
  • 18 octominoes (coloured blue) have point symmetry, also known as rotational symmetry of order 2. Their symmetry group has two elements, the identity and the 180° rotation.
Rotation symmetrical octominoes (C2).svg
  • 1 octomino (coloured yellow) has rotational symmetry of order 4. Its symmetry group has four elements, the identity and the 90°, 180° and 270° rotations.
Rotation symmetrical octomino (C4).svg
  • 4 octominoes (coloured purple) have two axes of reflection symmetry, both aligned with the gridlines. Their symmetry group has four elements, the identity, two reflections and the 180° rotation. It is the dihedral group of order 2, also known as the Klein four-group.
  • 1 octomino (coloured orange) has two axes of reflection symmetry, both aligned with the diagonals. Its symmetry group is also the dihedral group of order 2 with four elements.
  • 1 octomino (coloured blue-green) has four axes of reflection symmetry, aligned with the gridlines and the diagonals, and rotational symmetry of order 4. Its symmetry group, the dihedral group of order 4, has eight elements.
Rotation and reflection symmetric octominoes h.svg

The set of octominoes is the lowest polyomino set in which all eight possible symmetries are realized. The next higher set with this property is the dodecomino (12-omino) set.[3]

If reflections of an octomino are considered distinct, as they are with one-sided octominoes, then the first, fourth and fifth categories above double in size, resulting in an extra 335 octominoes for a total of 704. If rotations are also considered distinct, then the octominoes from the first category count eightfold, the ones from the next three categories count fourfold, the ones from categories five to seven count twice, and the last octomino counts only once. This results in 316 × 8 + (23+5+18) × 4 + (1+4+1) × 2 + 1 = 2,725 fixed octominoes.

Packing and tiling[edit]

Of the 369 free octominoes, 320 satisfy the Conway criterion and 23 more can form a patch satisfying the criterion.[4] The other 26 octominoes (including the 6 with holes) are unable to tessellate the plane.[5]

Since 6 of the free octominoes have a hole, it is trivial to prove that the complete set of octominoes cannot be packed into a rectangle, and that not all octominoes can be tiled.

Octominoes with holes.svg

References[edit]

  1. ^ Golomb, Solomon W. (1994). Polyominoes (2nd ed.). Princeton, New Jersey: Princeton University Press. ISBN 0-691-02444-8. 
  2. ^ Weisstein, Eric W. "Octomino". From MathWorld – A Wolfram Web Resource. Retrieved 2008-07-22. 
  3. ^ a b Redelmeier, D. Hugh (1981). "Counting polyominoes: yet another attack". Discrete Mathematics. 36 (2): 191–203. doi:10.1016/0012-365X(81)90237-5. 
  4. ^ Rhoads, Glenn C. (2005). "Planar tilings by polyominoes, polyhexes, and polyiamonds". Journal of Computational and Applied Mathematics. 174 (2): 329–353. doi:10.1016/j.cam.2004.05.002. 
  5. ^ Gardner, Martin (August 1975). "More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes". Scientific American. 233 (2): 112–115.