Polyominoes Home Page    
     


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.

 Polyominoes Home Page    
Copyright © 2004-2006 Kevin L. Gong