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