info prev up next book cdrom email home

Polyomino

A generalization of the Domino. An $n$-omino is defined as a collection of $n$ squares of equal size arranged with coincident sides. Free polyominoes can be picked up and flipped, so mirror image pieces are considered identical, whereas Fixed polyominoes are distinct if they have different chirality or orientation. Fixed polyominoes are also called Lattice Animals.


Redelmeier (1981) computed the number of Free and Fixed polyominoes for $n\leq 24$, and Mertens (1990) gives a simple computer program. The sequence giving the number of Free polyominoes of each order (Sloane's A000105, Ball and Coxeter 1987) is shown in the second column below, and that for Fixed polyominoes in the third column (Sloane's A014559). The number of possible holes is shown in the fourth column (Sloane's A001419).

$n$ Free Fixed Pos. Holes
1 1 1 0
2 1 2 0
3 2 6 0
4 5 19 0
5 12 63 0
6 35 216 0
7 108 760 1
8 369 2725 6
9 1285 9910 37
10 4655 39446 195
11 17073 135268  
12 63600 505861  
13 238591 1903890  
14 901971 7204874  
15 3426576 27394666  
16 13079255 104592937  
17 50107909 400795844  
18 192622052 1540820542  
19 742624232 5940738676  
20 2870671950 22964779660  
21 11123060678 88983512783  
22 43191857688 345532572678  
23 168047007728 1344372335524  
24 654999700403 5239988770268  

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

\begin{displaymath}
3.72^n<P(n)<4.65^n
\end{displaymath}

(Eden 1961, Klarner 1967, Klarner and Rivest 1973, Ball and Coxeter 1987). For $n=4$, the quartominoes are called Straight, L, T, Square, and Skew. For $n=5$, the pentominoes are called $f$, $I$, $L$, $N$, $P$, $T$, $U$, $V$, $W$, $X$, $y$, and $Z$ (Golomb 1995).

\begin{figure}\begin{center}\BoxedEPSF{Polyominoes.epsf scaled 1300}\end{center}\end{figure}

See also Domino, Hexomino, Monomino, Pentomino, Polyabolo, Polycube, Polyhex, Polyiamond, Polyking, Polyplet, Tetromino, Triomino


References

Polyominoes

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.; Gosper, R. W.; and Schroeppel, R. Item 77 in HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 48-50, Feb. 1972.

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. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/rndprc/rndprc.html

Gardner, M. ``Polyominoes and Fault-Free Rectangles.'' Ch. 13 in Martin Gardner's New Mathematical Diversions from Scientific American. New York: Simon and Schuster, 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, rev. enl. 2nd ed. Princeton, NJ: Princeton University Press, 1995.

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.

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.

Martin, G. Polyominoes: A Guide to Puzzles and Problems in Tiling. Washington, DC: Math. Assoc. Amer., 1991.

Mertens, S. ``Lattice Animals--A Fast Enumeration Algorithm and New Perimeter Polynomials.'' J. Stat. Phys. 58, 1095-1108, 1990.

Read, R. C. ``Contributions to the Cell Growth Problem.'' Canad. J. Math. 14, 1-20, 1962.

Redelmeier, D. H. ``Counting Polyominoes: Yet Another Attack.'' Discrete Math. 36, 191-203, 1981.

Ruskey, F. ``Information on Polyominoes.'' http://sue.csc.uvic.ca/~cos/inf/misc/PolyominoInfo.html.

Sloane, N. J. A. Sequences A014559, A000105/M1425, and A001419/M4226, in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

von Seggern, D. CRC Standard Curves and Surfaces. Boca Raton, FL: CRC Press, pp. 342-343, 1993.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26