# Enumeration

Most of my research into polyominoes has been on enumeration -- counting polyominoes. I've counted 2-dimensional and 3-dimensional polyominoes.

2-dimensional polyominoes are collections of squares. For a given size (number of squares), there are 3 main sets of polyominoes.

• The translation polyominoes are the set of polyominoes which are unique with respect to translation -- which means any two polyominoes in the set can't be made identical by moving them horizontally and vertically.
• The rotation polyominoes are the set of polyominoes which are unique with respect to rotation and translation -- which means any two polyominoes can't be made identical by rotating them 90, 180, or 270 degrees and by moving them horizontally and vertically. These are also referred to as 1-sided polyominoes.
• The 3-d rotation polyominoes are the set of polyominoes which are unique with respect to 3-d rotation, 2-d rotation, and translation. Any two polyominoes in this set can't be made identical by flipping, rotating, or translating them.

It is easy to prove that t(n) / r(n) <= 4 for all n, and that r(n) / p(n) <= 2 for all n.

Here is a list of the number of 2-dimensional polyominoes of each size up to 27.

• p(n) values for n <= 24 were calculated by D.H. Redelmeier in 1981.
• p(n) values for n = 25 thru 28 were calculated by Tomas Oliveira e Silva by using over 20 Pentium machines using a combined total of over 2 years of CPU time (in 1999?). See his results here [external link].
• r(n) for n <= 21 was calculated by Kevin Gong in August/September 1997 on a Power Macintosh 8500/120.
• r(n) for n = 22 was calculated by Kevin Gong in 83 hours in July 1999 on a Power Macintosh G3/400.
• t(n) for n <= 16 was calculated by W. F. Lunnon.
• Lunnon computed t(n) for n = 17 to be 400795860, but the correct number is 400795844, as computed independently by myself, Uwe Schult, and Tomas Oliveira e Silva.
• t(n) for n = 17 through 21 was calculated by Kevin Gong in August/September 1997 on a Power Macintosh 8500/120.
• t(n) for n = 22 thru 27 was calculated by Uwe Schult (Switzerland), n = 27 being computed on September 28, 1998 after running for 64 days on a 266Mhz Apple PowerMac G3.
• t(n) for n = 28 was calculated by Tomas Oliveira e Silva (see above).
• t(n) for n = 29 through 46 was calculated by Tony Guttmann, Iwan Jensen (University of Melbourne) and Ling Heng Wong, possibly published in "Punctured polygons and polyominoes on the square lattice." in J. Phys. A 33, 1735-1764 (2000), but that's just a guess. See MathSoft's page for more information. The values for 41-46 were apparently wrong when I originally looked at their web page in January 2001, they had different values listed in November 2001, which are listed here. Thanks to J K Haugland for pointing this out.
• r(n) for n = 23 was calculated by Kevin Gong in 8 days in November/December 2004 on a Power Mac G5.

 n 3-d rotation p(n) t(n) / t(n-1) translation t(n) 2-d rotation r(n) t(n) / r(n) r(n) / p(n) 1 1 1 1 - 1.00 1.00 2 2 1 1 2.00 2.00 1.00 3 6 2 2 3.00 3.00 1.00 4 19 7 5 3.17 2.71 1.40 5 63 18 12 3.32 3.50 1.50 6 216 60 35 3.43 3.60 1.71 7 760 196 108 3.52 3.88 1.81 8 2725 704 369 3.59 3.59 1.91 9 9910 2500 1285 3.64 3.96 1.95 10 36446 9189 4655 3.68 3.97 1.97 11 135268 33896 17073 3.71 3.99 1.99 12 505861 126759 63600 3.74 3.99 1.99 13 1903890 476270 238591 3.76 4.00 2.00 14 7204874 1802312 901971 3.78 4.00 2.00 15 27394666 6849777 3426576 3.80 4.00 2.00 16 104592937 26152418 13079255 3.82 4.00 2.00 17 400795844 100203194 50107909 3.83 4.00 2.00 18 1540820542 385221143 192622052 3.84 4.00 2.00 19 5940738676 1485200848 742624232 3.86 4.00 2.00 20 22964779660 5741256764 2870671950 3.87 4.00 2.00 21 88983512783 22245940545 11123060678 3.87 4.00 2.00 22 345532572678 86383382827 43191857688 3.883 - - 23 1344372335524 336093325058 168047007728 3.890 - - 24 5239988770268 - 654999700403 3.897 - - 25 20457802016011 - 2557227044764 3.904 - - 26 79992676367108 - 9999088822075 3.910 - - 27 313224032098244 - 39153010938487 3.916 - - 28 1228088671826973 - 153511100594603 3.921 - -

 n t(n) / t(n-1) translation t(n) 29 4820975409710116 3.926 30 18946775782611174 3.930 31 74541651404935148 3.934 32 293560133910477776 3.938 33 1157186142148293638 3.942 34 4565553929115769162 3.945 35 18027932215016128134 3.949 36 71242712815411950635 3.952 37 281746550485032531911 3.955 38 1115021869572604692100 3.958 39 4415695134978868448596 3.960 40 17498111172838312982542 3.963 41 69381900728932743048483 3.965 42 275265412856343074274146 3.967 43 1092687308874612006972082 3.970 44 4339784013643393384603906 3.972 45 17244800728846724289191074 3.974 46 68557762666345165410168738 3.976

Counting 3-dimensional polyominoes is similar. Again, for a given size (number of cubes), there are 3 main sets of polyominoes.

• The translation polyominoes are the set of polyominoes which are unique with respect to translation -- which means any two polyominoes in the set can't be made identical by moving them horizontally and vertically.
• The 3-d rotation polyominoes are the set of polyominoes which are unique with respect to rotation and translation -- which means any two polyominoes can't be made identical by rotating them in 3 dimensions and by translating them.
• The 4-d rotation polyominoes are the set of polyominoes which are unique with respect to 4-d rotation, 3-d rotation, and translation. It may sound strange to think of 4-d rotation, but think of it as just flipping. A good example is your hands. You have a right hand and a left hand; they would be distinct elements in the translation set and the 3-d rotation set. But they would be considered the same element in the 4-d rotation set. You can flip a left hand through 4-d space to create a right hand.

It is easy to prove that t(n) / r(n) <= 24 for all n, and that r(n) / p(n) <= 2 for all n.

Here is a list of the number of 3-dimensional polyominoes of each size up to 12

• t(n), r(n), and p(n) for n <= 6 were calculated by Lunnon (by hand!) in 1972.
• t(n), r(n), and p(n) for n = 7 through 9 were calculated by Kevin Gong in 1992, on a 12-processor Sequent computer.
• t(n), r(n), and p(n) for n = 10 through 15 were computed by Kevin Gong in August/September 1997, on a Power Macintosh 8500/120.
• t(n), r(n), and p(n) for n = 16 was computed by Kevin Gong in 11 days in November/December 2004, on a Power Mac G5.

 n translation t(n) 3-d rotation r(n) 4-d rotation p(n) t(n) / t(n-1) 1 1 1 1 - 2 3 1 1 3.00 3 15 2 2 5.00 4 86 8 7 5.73 5 534 29 23 6.21 6 3481 166 112 6.52 7 23502 1023 607 6.75 8 162913 6922 3811 6.93 9 1152870 48311 25413 7.08 10 8294738 346543 178083 7.19 11 60494549 2522522 1279537 7.29 12 446205905 18598427 9371094 7.38 13 3322769321 138462649 69513546 7.45 14 24946773111 1039496297 520878101 7.51 15 188625900446 7859514470 3934285874 7.56 16 1435074454755 59795121480 29915913663 7.61

It appears plausible that t(n) / t(n-1) > t(n-1) / t(n - 2) for all n > 2. I don't know of any known proof, however.