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 |
translation t(n)
|
2-d rotation r(n)
|
3-d rotation p(n) |
t(n) / t(n-1) |
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 |
translation t(n)
|
t(n) / t(n-1) |
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.
|