TOPICS
Search

Polyomino


A polyomino is a generalization of the domino to a collection of n squares of equal size arranged with coincident sides. Polyominos were originally called "super-dominoes" by Gardner (1957). A polyomino with n squares is known as an n-polyomino or "n-omino."

Polyominoes may be conveniently represented and visualized in the Wolfram Language using ArrayMesh.

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.

Polyominoes

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 L-triominoes). The 4-ominoes (tetrominoes) are known as the straight, L, T, square, and skew tetrominoes. The 5-ominoes (pentominoes) are called f, I, L, N, P, T, U, V, W, X, y, and Z (Golomb 1995). Another common naming scheme replaces f, I, L, and N with R, O, Q, and S so that all letters from O to Z are used (Berlekamp et al. 1982).

PolyominoesWithHoles

The first few polyominoes with holes are illustrated above (Myers).

Redelmeier (1981) computed the number of free and fixed polyominoes for n<=24, 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 1995; 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 n.

nnamefreeone-sidedfixedwith holes
SloaneA000105A000988A001168A001419
1monomino1110
2domino1120
3triomino2260
4tetromino57190
5pentomino1218630
6hexomino35602160
7heptomino1081967601
8octomino36970427256
912852500991037
104655918936446195
111707333896135268979
12636001267595058614663
13238591476270190389021474
149019711802312720487496496
153426576684977727394666425449

The best currently known bounds on the number of n-polyominoes are

 3.72^n<P(n)<4.65^n

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


See also

Column-Convex Polyomino, Convex Polyomino, Domino, Heptomino, Hexomino, Lattice Polygon, Monomino, Octomino, Pentomino, Polyabolo, Polycube, Polyform, Polyhex, Polyiamond, Polyomino Tiling, Polyplet, Row-Convex Polyomino, Self-Avoiding Polygon, Tetromino, Triomino

Explore with Wolfram|Alpha

References

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.recmath.com/PolyPages/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 n-ominoes." Can. J. Math. 25, 585-602, 1973.Update a linkLei, A. "Bigger Polyominoes." http://www.cs.ust.hk/~philipl/omino/bigpolyo.htmlUpdate a linkLei, A. "Polyominoes." http://www.cs.ust.hk/~philipl/omino/omino.htmlLunnon, 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.

Referenced on Wolfram|Alpha

Polyomino

Cite this as:

Weisstein, Eric W. "Polyomino." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Polyomino.html

Subject classifications