“Polyomino”的概念、定义、习题解题方法及翻译-数学辞典

A generalization of the Domino. An

-omino is defined as a collection of

squares of equal size arranged withcoincident 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 alsocalled Lattice Animals.

Redelmeier (1981) computed the number of Free and Fixed polyominoes for

, and Mertens (1990) gives a simplecomputer program. The sequence giving the number of A000105, Ball and Coxeter1987) is shown in the second column below, and that for A014559). Thenumber 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

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

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. SequencesA014559,A000105/M1425, andA001419/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.