Animal enumerations on the {4,4} Euclidean tiling



Introduction

The animals on the {4,4} regular tiling of the Euclidean plane are called polyominoes, a name coined by Solomon Golomb in 1953 [1]. An alternative name would be square animals, since the {4,4} regular tiling is composed of squares. Each polyomino may be equal to its mirror image (achiral) or different from its mirror image (chiral). The vast majority of the polyominoes do not have any kind of symmetry.

Redelmeier [2] developed an algorithm to enumerate the polyominoes of a given area, counting all their possible orientations (called fixed polyominoes). He developed another program to enumerate the polyominoes of a given area with a predefined symmetry (axial, rotational, mirror image). By combining the results of the different enumerations it is possible to infer the number of polyominoes with different shapes, ie., disregarding orientation and mirror images (called free polyominoes). Using 8 months of CPU time, he was able to count the number of polyominoes with areas up to 24. In 1998, with the help of some friends (who donated computational power), I managed to extend this to areas up to 28. In 2000 there occurred a spectacular progress in the enumeration of fixed polyominoes of a given area, with Jensen and Guttmann [3] reporting results for areas up to 46 (the current computational limit appears to be area 56; see the appendix of [4] and the notes attached to the POLYNUM and POLYSAVE programs kindly made available by Donald E. Knuth, who was the first to obtain correct results for area 47). The number of free polyominoes, however, only appears to be known up to area 28 (see results below).

In 2014 I developed a program capable of classifying each free polyomino according to its number of holes and their areas. The program uses an algorithm similar to the parallel version of the Redelmeier algorithm [5]. For each area, the fixed polyominoes were generated, and only those in canonical form (one representative of each free polyomino) were classified. The program was relatively fast, and since it was possible to run it in parallel, it was possible to collect data up to area 28.

Tables with counts of the number of polyominoes (December 28, 2015)

The following table presents counts of the number of polyominoes classified according to Redelmeier's symmetry classes [2].

 Area Number of polyominoes
 Fixed  Free  None  Rot  Axis  Diag  Rot2  Axis2  Diag2  All 
111       1
221     1  
362   1 1  
4195111  1 1
563125122 1 1
62163520562 2  
776010884497 31 
82725369316182351411
9991012851196193826 4 2
103644646554461739022 81 
1113526817073167507314791 102 
1250586163600628782783417931533
13190389023859123739428356432621732
14720487490197189926510761294301 305 
152739466634265763422111109021481186 356 
1610459293713079255130690264125489611171260145
17400795844501079095009109541838195435276494
18154082054219262205219258315215939186124212 11720 
195940738676742624232742560511161053134916119 12820 
202296477966028706719502870523142616287098315849442365612
21889835127831112306067811122817672621701203576017425241327
22345532572678431918576884319128575123938827192160089 45980 
231344372335524168047007728168046076423240907463712226146 47664 
245239988770268654999700403654997492842932230104555922842616593722420
25204578020160112557227044764255722345980593644717925828548039091211411
26799926763671089999088822075999908027076636419454034832872404 1813315 
273132240320982443915301093848739152997087077365161869505793247207 1789217 
28122808867182697315351110059460315351106736476014262540156195073342579603370686345

The following table presents counts of the number of polyominoes classified according to their number of holes.

 Area Number of free polyominoes
 No 
 holes 
 One 
 hole 
 Two 
 holes 
 Three 
 holes 
 Four 
 holes 
 Five 
 holes 
 Six 
 holes 
 Seven 
 holes 
 Eight 
 holes 
11        
21        
32        
45        
512        
635        
71071       
83636       
9124837       
104460195       
11160949754      
1258937462241      
1321711721128346      
148054759410923843     
1530011274108201456069     
1611230003176659181863798     
1742161529750617943317270218    
1815878110631596240219275251775179    
195995638931319916191072625233995825091   
2022695060625479921835109420320538722560921   
218609442688226347761223825928011665593214932573   
2232725637373930938617810920530686319294515789849140   
231246218333543815008205749346522983297982781053626010541764  
24475368834568155859235424220347678371670466031654116459827672131  
2518161033457526350674786289740751911982567623653839814997919375380224 
266948228104703258173770403942691682818139992202198215611446857387444480713329 
272661867150598910474587325120185725357557719043100308411678888362383757344487267910332 
281021027883623034242297046798080277491306238937265502316141324260324102923664236023918822137

References

[1] S. Golomb, Polyominoes: puzzles, patterns, problems, and packings, Princeton University Press, Princeton, NJ, second edition, 1994.
[2] D. H. Redelmeier, Counting polyominoes: yet another attack, Discrete mathematics, vol. 36, no. 2, pp. 191-203, 1981.
[3] Iwan Jensen and Anthony J. Guttmann, Statistics of lattice animals (polyominoes) and polygons, Journal of Physics A: Mathematical and General, vol. 33, pp. L257-L263, 2000.
[4] Anthony J. Guttmann (editor), Polygons, polyominoes and polycubes, Lecture notes in Physics, vol. 775, Springer, 2009.
[5] S. Mertens, Counting lattice animals: a parallel attack, Journal of Statistical Physics, vol. 66, no. 1/2, pp. 669-678, Jan. 1992.

Additional links