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."
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.
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 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 .
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.
See alsoColumn-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 ReferencesAtkin, 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 -ominoes." Can. J. Math. 25, 585-602, 1973.Lei, A. "Bigger Polyominoes." http://www.cs.ust.hk/~philipl/omino/bigpolyo.htmlLei, 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|AlphaPolyomino Cite this as:Weisstein, Eric W. "Polyomino." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Polyomino.html
Subject classificationsRetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4