A generalization of the Domino. An -omino is defined as a collection of 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 , 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).
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 -polyominoes are
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 -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.
© 1996-9 Eric W. Weisstein