A polyomino is a generalization of the domino to a collection of  squares of equal size arranged with coincident
sides. Polyominos were originally called "super-dominoes" by Gardner (1957).
A polyomino with  squares is known as an  -polyomino or " -omino."
Free polyominoes can be picked up and flipped, so mirror image pieces are considered identical. One-sided polyominoes may
not be flipped, but may be rotated, so different rotational orientations are the
same, but pieces having different chiralities are considered distinct. Fixed polyominoes (also called "lattice animals")
are considered distinct if they have different chirality or orientation.
When the type of polyomino being dealt with is not specified, it is usually assumed that they are free. There is a single unique 2-omino (the domino), and two distinct 3-ominoes (the straight- and  -triominoes).
The 4-ominoes (tetrominoes) are known
as the straight, L, T, square, and skew tetrominoes. The 5-ominoes (pentominoes) are called  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , and  (Golomb 1995).
Another common naming scheme replaces  ,  ,  , and  with  ,  ,  , and  so that all letters
from O to Z are used (Berlekamp et al. 1982).
The first few polyominoes with holes are illustrated above (Myers).
Redelmeier (1981) computed the number of free and fixed polyominoes for  , and Mertens
(1990) gives a simple computer program. The following table gives the number of free (Lunnon 1971, 1972; Read 1978; Redelmeier
1981; Ball and Coxeter 1987; Conway and Guttmann 1995; Goodman and O'Rourke 1997,
p. 229), fixed (Redelmeier 1981),
and one-sided polyominoes (Redelmeier 1981; Golomb 1994; Goodman and O'Rourke 1997,
p. 229), as well as the number containing holes (Parkin et al. 1967,
Madachy 1969, Golomb 1994) for the first few  .
The best currently known bounds on the number of  -polyominoes are
(Eden 1961, Klarner 1967, Klarner and Rivest 1973, Ball and Coxeter 1987).
Generalizations of polyominoes to other base shapes other that squares are known as polyforms, with the best-known
examples being the polyiamonds and
polyhexes.
Atkin, A. O. L. and Birch, B. J. (Eds.). Computers in Number Theory: Proc. Sci. Research Council Atlas Symposium
No. 2 Held at Oxford from 18-23 Aug., 1969. New York: Academic Press,
1971.
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York:
Dover, pp. 109-113, 1987.
Beeler, M. Item 112 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 48-50,
Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/polyominos.html#item112.
Beineke, L. W. and Wilson, R. J. (Eds.). Selected Topics in Graph Theory. New York: Academic Press,
pp. 417-444, 1978.
Berge, C.; Chen, C. C.; Chvátal, V.; and Seow, C. S. "Combinatorial
Properties of Polyominoes." Combin. 1, 217-224, 1981.
Berlekamp, E. R.; Conway, J. H; and Guy, R. K. Winning Ways for Your Mathematical Plays, Vol. 1: Adding Games,
2nd ed. Wellesley, MA: A K Peters, 1982.
Berlekamp, E. R.; Conway, J. H; and Guy, R. K. Winning Ways for Your Mathematical Plays, Vol. 2: Games in
Particular. London: Academic Press, 1982.
Bousquet-Mélou, M.; Guttmann, A. J.; Orrick, W. P.; and Rechnitzer, A. "Inversion Relations, Reciprocity and Polyominoes." 23 Aug 1999. http://arxiv.org/abs/math.CO/9908123/.
Clarke, A. L. "Polyominoes." http://www.geocities.com/alclarke0/PolyPages/Polyominoes.html.
Conway, A. R. and Guttmann, A. J. "On Two-Dimensional Percolation."
J. Phys. A: Math. Gen. 28, 891-904, 1995.
Eden, M. "A Two-Dimensional Growth Process." Proc. Fourth Berkeley Symposium Math. Statistics and Probability, Held at the Statistical Laboratory, University
of California, June 30-July 30, 1960. Berkeley, CA: University of California
Press, pp. 223-239, 1961.
Finch, S. R. "Klarner's Polyomino Constant." §5.19 in Mathematical Constants. Cambridge, England: Cambridge University
Press, pp. 378-382, 2003.
Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150-156,
May 1957.
Gardner, M. "Polyominoes and Fault-Free Rectangles." Ch. 13 in Martin
Gardner's New Mathematical Diversions from Scientific American. New York:
Simon and Schuster, pp. 150-161, 1966.
Gardner, M. "Polyominoes and Rectification." Ch. 13 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions
and Other Mathematical Sleight-of-Mind from Scientific American. New York:
Vintage, pp. 172-187, 1978.
Golomb, S. W. "Checker Boards and Polyominoes." Amer. Math. Monthly 61,
675-682, 1954.
Golomb, S. W. Polyominoes: Puzzles, Patterns, Problems, and Packings, 2nd ed.
Princeton, NJ: Princeton University Press, 1995.
Goodman, J. E. and O'Rourke, J. (Eds.). Handbook of Discrete & Computational Geometry. Boca
Raton, FL: CRC Press, 1997.
Keller, M. "Counting Polyforms." http://members.aol.com/wgreview/polyenum.html.
Klarner, D. A. "Cell Growth Problems." Can. J. Math. 19,
851-863, 1967.
Klarner, D. A. and Riverst, R. "A Procedure for Improving the Upper Bound for the Number of  -ominoes." Can. J. Math. 25,
585-602, 1973.
 Lei, A. "Bigger
Polyominoes." http://www.cs.ust.hk/~philipl/omino/bigpolyo.html
Lei, A. "Polyominoes."
http://www.cs.ust.hk/~philipl/omino/omino.html
Lunnon, W. F. "Counting Polyominoes." In Computers in Number Theory (Ed. A. O. L. Atkin
and B. J. Brich). London: Academic Press, pp. 347-372, 1971.
Lunnon, W. F. "Counting Hexagonal and Triangular Polyominoes." In Graph Theory and Computing (Ed. R. C. Read).
New York: Academic Press, 1972.
Madachy, J. S. "Pentominoes: Some Solved and Unsolved Problems." J.
Rec. Math. 2, 181-188, 1969.
Martin, G. Polyominoes: A Guide to Puzzles and Problems in Tiling.
Washington, DC: Math. Assoc. Amer., 1991.
Marzetta, A. "List of Polyominoes of order 4..7." http://wwwjn.inf.ethz.ch/ambros/polyo-list.html.
Mertens, S. "Lattice Animals--A Fast Enumeration Algorithm and New Perimeter
Polynomials." J. Stat. Phys. 58, 1095-1108, 1990.
Montgomery-Smith, S. "Polyomino Puzzles Software." http://www.math.missouri.edu/~stephen/software/polyomino/.
Myers, J. "Polyomino Tiling." http://www.srcf.ucam.org/~jsm28/tiling/.
Parkin, T. R.; Lander, L. J.; and Parkin, D. R. "Polyomino Enumeration
Results." SIAM Fall Meeting. Santa Barbara, CA, 1967.
Putter, G. "Gerard's Universal Polyomino Solver." http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html.
Read, R. C. "Contributions to the Cell Growth Problem." Canad.
J. Math. 14, 1-20, 1962.
Read, R. C. "Some Applications of Computers in Graph Theory." In Selected
Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson).
New York: Academic Press, pp. 417-444, 1978.
Redelmeier, D. H. "Counting Polyominoes: Yet Another Attack." Discrete
Math. 36, 191-203, 1981.
Ruskey, F. "Information on Polyominoes." http://www.theory.csc.uvic.ca/~cos/inf/misc/PolyominoInfo.html.
Schroeppel, R. Item 77 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 30,
Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/proposed.html#item77.
Sloane, N. J. A. Sequences A000105/M1425, A000988/M1749, A001168/M1639, and A001419/M4226 in "The On-Line Encyclopedia of Integer
Sequences."
Vichera, M. "Polyforms." http://www.vicher.cz/puzzle/polyforms.htm.
von Seggern, D. CRC Standard Curves and Surfaces. Boca Raton, FL: CRC Press,
pp. 342-343, 1993.
Weisstein, E. W. "Books about Polyominoes." http://www.ericweisstein.com/encyclopedias/books/Polyominoes.html.
Wells, D. The Penguin Dictionary of Curious and Interesting Geometry.
London: Penguin, p. 117, 1991.
Wells, D. Recreations in Logic. New York: Dover, 1979.
|
Contact the MathWorld Team
