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

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

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

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.