Editing Polyomino (section)

==Enumeration of polyominoes==
<gallery caption="Free polyominoes (''n''=2 to 6)">
Image:Domino green.svg|The single free [[domino (mathematics)|domino]]
File:Trominoes.svg|The two free [[tromino]]es
File:Free tetrominoes.svg|The five free [[tetromino]]es
File:Free pentominos 001.svg|The 12 free [[pentomino]]es, colored according to their symmetry
Image:All 35 free hexominoes.svg|The 35 free [[hexomino]]es, colored according to their symmetry
</gallery>

===Free, one-sided, and fixed polyominoes===
There are three common ways of distinguishing polyominoes for enumeration:<ref>{{cite journal |last=Redelmeier |first=D. Hugh |year=1981 |title=Counting polyominoes: yet another attack |journal=Discrete Mathematics |volume=36 |pages=191–203 |doi=10.1016/0012-365X(81)90237-5 |issue=2|doi-access=free }}</ref><ref>Golomb, chapter 6</ref>

*''free'' polyominoes are distinct when none is a rigid transformation ([[translation (geometry)|translation]], [[rotation]], [[reflection (mathematics)|reflection]] or [[glide reflection]]) of another (pieces that can be picked up and flipped over). Translating, rotating, reflecting, or glide reflecting a free polyomino does not change its shape.
*''one-sided polyominoes'' are distinct when none is a translation or rotation of another (pieces that cannot be flipped over).  Translating or rotating a one-sided polyomino does not change its shape.
*''fixed'' polyominoes are distinct when none is a translation of another (pieces that can be neither flipped nor rotated). Translating a fixed polyomino will not change its shape.

The following table shows the numbers of polyominoes of various types with ''n'' cells.

{|class=wikitable
!rowspan=2|''n''
!rowspan=2|name
!colspan=3|free 
!rowspan=2|one-sided
!rowspan=2|fixed
|-
!total
!with holes
!without holes
|- align=right
|1 ||align=left |monomino ||1 ||0 ||1 ||1 ||1
|- align=right
|2 ||align=left |[[domino (mathematics)|domino]] ||1 ||0 ||1 ||1 ||2
|- align=right
|3 ||align=left |[[tromino]] ||2 ||0 ||2 ||2 ||6
|- align=right
|4 ||align=left |[[tetromino]] ||5 ||0 ||5 ||7 ||19
|- align=right
|5 ||align=left |[[pentomino]] ||12 ||0 ||12 ||18 ||63
|- align=right
|6 ||align=left |[[hexomino]] ||35 ||0 ||35 ||60 ||216
|- align=right
|7 ||align=left |[[heptomino]] ||108 ||1 ||107 ||196 ||760
|- align=right
|8 ||align=left |[[octomino]] ||369 ||6 ||363 ||704 ||2,725
|- align=right
|9 ||align=left |[[nonomino]] ||1,285 ||37 ||1,248 ||2,500 ||9,910
|- align=right
|10 ||align=left |[[decomino]] ||4,655 ||195 ||4,460 ||9,189 ||36,446
|- align=right
|11 ||align=left |undecomino ||17,073 ||979 ||16,094 ||33,896 ||135,268
|- align=right
|12 ||align=left |dodecomino ||63,600 ||4,663 ||58,937 ||126,759 ||505,861
|- align=right
|colspan=2|[[OEIS]]&nbsp;sequence
|{{OEIS link|id=A000105}}
|{{OEIS link|id=A001419}}
|{{OEIS link|id=A000104}}
|{{OEIS link|id=A000988}}
|{{OEIS link|id=A001168}}
|}

Fixed polyominoes were enumerated in 2004 up to {{nowrap begin}}''n'' = 56{{nowrap end}} by Iwan Jensen,<ref>{{cite web |url=http://www.ms.unimelb.edu.au/~iwan/animals/Animals_ser.html |title=Series for lattice animals or polyominoes |access-date=2007-05-06 |author=Iwan Jensen |archive-url=https://web.archive.org/web/20070612141716/http://www.ms.unimelb.edu.au/~iwan/animals/Animals_ser.html |archive-date=2007-06-12 |url-status=live }}</ref> and in 2024 up to {{nowrap begin}}''n'' = 70{{nowrap end}} by Gill Barequet and Gil Ben-Shachar.<ref>{{cite book |chapter-url=https://epubs.siam.org/doi/10.1137/1.9781611977929.10 |title=2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) - Counting Polyominoes, Revisited|chapter=Counting Polyominoes, Revisited |date=January 2024 |pages=133–143 |publisher=Society for Industrial and Applied Mathematics |doi=10.1137/1.9781611977929.10 |last1=Barequet |first1=Gill |last2=Ben-Shachar |first2=Gil |isbn=978-1-61197-792-9 }}</ref> 

Free polyominoes were enumerated in 2007 up to {{nowrap begin}}''n'' = 28{{nowrap end}} by Tomás Oliveira e Silva,<ref>{{cite web |url=http://www.ieeta.pt/%7Etos/animals/a44.html |title=Animal enumerations on the {4,4} Euclidean tiling |access-date=2007-05-06 |author=Tomás Oliveira e Silva |archive-url=https://web.archive.org/web/20070423213531/http://www.ieeta.pt/%7Etos/animals/a44.html |archive-date=2007-04-23 |url-status=live }}</ref> in 2012 up to {{nowrap begin}}''n'' = 45{{nowrap end}} by Toshihiro Shirakawa,<ref>{{cite web |url=https://www.gathering4gardner.org/g4g10gift/math/Shirakawa_Toshihiro-Harmonic_Magic_Square.pdf |title=Harmonic Magic Square, Enumeration of Polyominoes considering the symmetry}}</ref> and in 2023 up to {{nowrap begin}}''n'' = 50{{nowrap end}} by John Mason.<ref>{{cite web |url=https://oeis.org/A000105/a000105_2.pdf |title=Counting size 50 polyominoes}}</ref>

The above OEIS sequences, with the exception of A001419, include the count of 1 for the number of null-polyominoes; a null-polyomino is one that is formed of zero squares.

===Symmetries of polyominoes===
The [[dihedral group]] ''D''<sub>4</sub> is the [[group (mathematics)|group]] of [[symmetries]] ([[symmetry group]]) of a square. This group contains four rotations and four reflections. It is generated by alternating reflections about the ''x''-axis and about a diagonal. One free polyomino corresponds to at most 8 fixed polyominoes, which are its images under the symmetries of ''D''<sub>4</sub>. However, those images are not necessarily distinct: the more symmetry a free polyomino has, the fewer distinct fixed counterparts it has. Therefore, a free polyomino that is invariant under some or all non-trivial symmetries of ''D''<sub>4</sub> may correspond to only 4, 2 or 1 fixed polyominoes. Mathematically, free polyominoes are [[equivalence class]]es of fixed polyominoes under the group ''D''<sub>4</sub>.

Polyominoes have the following possible symmetries;<ref name="Redelmeier, section 3">Redelmeier, section 3</ref> the least number of squares needed in a polyomino with that symmetry is given in each case:
*8 fixed polyominoes for each free polyomino:
**no symmetry (4)
*4 fixed polyominoes for each free polyomino:
**mirror symmetry with respect to one of the grid line directions (4)
**mirror symmetry with respect to a diagonal line (3)
**2-fold rotational symmetry: ''C''<sub>2</sub> (4)
*2 fixed polyominoes for each free polyomino:
**symmetry with respect to both grid line directions, and hence also 2-fold rotational symmetry: ''D''<sub>2</sub> (2) (also known as the [[Klein four-group]])
**symmetry with respect to both diagonal directions, and hence also 2-fold rotational symmetry: ''D''<sub>2</sub> (7)
**4-fold rotational symmetry: ''C''<sub>4</sub> (8)
*1 fixed polyomino for each free polyomino:
**all symmetry of the square: ''D''<sub>4</sub> (1).

In the same way, the number of one-sided polyominoes depends on polyomino symmetry as follows:
*2 one-sided polyominoes for each free polyomino:
**no symmetry
**2-fold rotational symmetry: ''C''<sub>2</sub>
**4-fold rotational symmetry: ''C''<sub>4</sub>
*1 one-sided polyomino for each free polyomino:
**all symmetry of the square: ''D''<sub>4</sub>
**mirror symmetry with respect to one of the grid line directions
**mirror symmetry with respect to a diagonal line
**symmetry with respect to both grid line directions, and hence also 2-fold rotational symmetry: ''D''<sub>2</sub>
**symmetry with respect to both diagonal directions, and hence also 2-fold rotational symmetry: ''D''<sub>2</sub>.

The following table shows the numbers of polyominoes with ''n'' squares, sorted by symmetry groups. 
{|class=wikitable
!''n''
!none
!mirror<br/>90°
!mirror<br/>45°
!''C''<sub>2</sub>
!''D''<sub>2</sub><br/>90°
!''D''<sub>2</sub><br/>45°
!''C''<sub>4</sub>
!''D''<sub>4</sub>
|- align=right
|1 ||0 ||0 ||0 ||0 ||0 ||0 ||0 ||1
|- align=right
|2 ||0 ||0 ||0 ||0 ||1 ||0 ||0 ||0
|- align=right
|3 ||0 ||0 ||1 ||0 ||1 ||0 ||0 ||0
|- align=right
|4 ||1 ||1 ||0 ||1 ||1 ||0 ||0 ||1
|- align=right
|5 ||5 ||2 ||2 ||1 ||1 ||0 ||0 ||1
|- align=right
|6 ||20 ||6 ||2 ||5 ||2 ||0 ||0 ||0
|- align=right
|7 ||84 ||9 ||7 ||4 ||3 ||1 ||0 ||0
|- align=right
|8 ||316 ||23 ||5 ||18 ||4 ||1 ||1 ||1
|- align=right
|9 ||1,196 ||38 ||26 ||19 ||4 ||0 ||0 ||2
|- align=right
|10 ||4,461 ||90 ||22 ||73 ||8 ||1 ||0 ||0
|- align=right
|11 ||16,750 ||147 ||91 ||73 ||10 ||2 ||0 ||0
|- align=right
|12 ||62,878 ||341 ||79 ||278 ||15 ||3 ||3 ||3
|-
| [[OEIS]]&nbsp;sequence
|{{OEIS link|id=A006749}}
|{{OEIS link|id=A006746}}
|{{OEIS link|id=A006748}}
|{{OEIS link|id=A006747}}
|{{OEIS link|id=A056877}}
|{{OEIS link|id=A056878}}
|{{OEIS link|id=A144553}}
|{{OEIS link|id=A142886}}
|}

<ref>{{cite journal|doi=10.1016/0012-365X(81)90237-5 |doi-access=free |title=Counting polyominoes: Yet another attack |year=1981 |last1=Redelmeier |first1=D.Hugh |journal=Discrete Mathematics |volume=36 |issue=2 |pages=191–203 }}</ref>

===Algorithms for enumeration of fixed polyominoes===

====Inductive algorithms====
Each polyomino of size ''n''+1 can be obtained by adding a square to a polyomino of size ''n''. This leads to algorithms for generating polyominoes inductively.

Most simply, given a list of polyominoes of size ''n'', squares may be added next to each polyomino in each possible position, and the resulting polyomino of size ''n''+1 added to the list if not a duplicate of one already found; refinements in ordering the enumeration and marking adjacent squares that should not be considered reduce the number of cases that need to be checked for duplicates.<ref>Golomb, pp. 73–79</ref> This method may be used to enumerate either free or fixed polyominoes.

A more sophisticated method, described by Redelmeier, has been used by many authors as a way of not only counting polyominoes (without requiring that all polyominoes of size ''n'' be stored in size to enumerate those of size ''n''+1), but also proving upper bounds on their number. The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each ''n''-omino ''n'' times, once from starting from each of its ''n'' squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When ''n'' squares have been created, an ''n''-omino has been created.

This method ensures that each fixed polyomino is counted exactly ''n'' times, once for each starting square. It can be optimized so that it counts each polyomino only once, rather than ''n'' times. Starting with the initial square, declare it to be the lower-left square of the polyomino. Simply do not number any square that is on a lower row, or left of the square on the same row. This is the version described by Redelmeier.

If one wishes to count free polyominoes instead, then one may check for symmetries after creating each ''n''-omino. However, it is faster<ref>Redelmeier, section 4</ref> to generate symmetric polyominoes separately (by a variation of this method)<ref>Redelmeier, section 6</ref> and so determine the number of free polyominoes by [[Burnside's lemma]].

====Transfer-matrix method====
Currently, the most effective algorithms belong to the transfer-matrix paradigm. They may be called transfer matrix algorithms (TMAs) for short. Andrew Conway<ref>{{cite journal |last=Conway |first=Andrew | year=1995 | title=Enumerating 2D percolation series by the finite-lattice method: theory | journal=Journal of Physics A: Mathematical and General | volume=28 |issue=2 | pages=335–349 | zbl=0849.05003 | doi=10.1088/0305-4470/28/2/011|bibcode=1995JPhA...28..335C }}</ref> first implemented a TMA in the 90s, and calculated 25 terms of the fixed polyomino sequence ({{OEIS link|id=A001419}} in the OEIS). Iwan Jensen refined Conway's methods and implemented a TMA in parallel for the first time in a pair of papers in the early 2000s.<ref>{{cite journal |last=Jensen |first=Iwan | year=2001 | title=Enumerations of Lattice Animals and Trees | journal=Journal of Statistical Physics | volume=102 |issue=1 | pages=865–881 | doi=10.1023/A:1004855020556| arxiv=cond-mat/0007239 |bibcode=2001JSP...102..865J }}</ref><ref>{{cite conference |last=Jensen |first=Iwan | year=2003 | title=Counting Polyominoes: A Parallel Implementation for Cluster Computing | conference=International Conference on Computer Science (ICCS) | pages=203–212 | doi=10.1007/3-540-44863-2_21}}</ref> He calculated 56 terms. Because of this work, any TMA is sometimes also called Jensen's Algorithm. In 2024, Gill Barequet and his student Gil Ben-Shachar made another improvement by running a TMA on 45° rotation of the square grid, which is an equivalent problem but computationally easier.<ref>{{cite conference |last1=Barequet |first1=Gill | last2=Ben-Shachar |first2=Gil |year=2003 | title=Counting Polyominoes, Revisited | conference=Symposium on Algorithm Engineering and Experiments (SIAM) | pages=133–143 | doi=10.1137/1.9781611977929.1| arxiv=2310.20632 }}</ref> This approach holds the polyomino-counting record, with 70 terms. 

As a rule, TMAs are much faster than the previous methods, but still run in time that is exponential in ''n''. Roughly, this is achieved by fixing a width (in the diagonal case, a diagonal width), and counting polyominoes that fit in rectangles of that width. If this is done, it is only necessary to keep track of a polyomino's boundary, and since multiple polyominoes can correspond to a single boundary, this approach is faster than one generating every polyomino. Repeating this for every width gives every polyomino. 

Although it has excellent running time, the tradeoff is that this algorithm uses exponential amounts of memory (many [[gigabyte]]s of memory are needed for ''n'' above 50), is much harder to program than the other methods, and cannot currently be used to count free polyominoes.

===Asymptotic growth of the number of polyominoes===

====Fixed polyominoes====
Theoretical arguments and numerical calculations support the estimate for the number of fixed polyominoes of size n
:<math>A_n \sim \frac{c\lambda^n}{n}</math>

where ''λ'' = 4.0626 and ''c'' = 0.3169.<ref>{{cite journal |last=Jensen |first=Iwan |author2=Guttmann, Anthony J. |year=2000 |title=Statistics of lattice animals (polyominoes) and polygons |journal=Journal of Physics A: Mathematical and General |volume=33 |pages=L257–L263 |doi=10.1088/0305-4470/33/29/102 |issue=29 |arxiv=cond-mat/0007238v1 |bibcode=2000JPhA...33L.257J |s2cid=6461687 }}</ref> However, this result is not proven and the values of ''λ'' and ''c'' are only estimates.

The known theoretical results are not nearly as specific as this estimate. It has been proven that
:<math>\lim_{n\rightarrow \infty} (A_n)^\frac{1}{n} = \lambda</math>

exists. In other words, ''A<sub>n</sub>'' [[exponential growth|grows exponentially]]. The best known lower bound for ''λ'', found in 2016, is 4.00253.<ref>{{cite journal |last1=Barequet|first1=Gill |last2=Rote |first2=Gunter |last3=Shalah |first3=Mira |doi=10.1145/2851485 |journal=Communications of the ACM |volume=59 |issue=7 |pages=88–95 |title=λ > 4: An Improved Lower Bound on the Growth Constant of Polyominoes}}</ref> The best known upper bound is {{nowrap|''λ'' &lt; 4.5252}}.<ref name=":0" />

To establish a lower bound, a simple but highly effective method is concatenation of polyominoes. Define the upper-right square to be the rightmost square in the uppermost row of the polyomino. Define the bottom-left square similarly. Then, the upper-right square of any polyomino of size ''n'' can be attached to the bottom-left square of any polyomino of size ''m'' to produce a unique (''n''+''m'')-omino. This proves {{nowrap|''A<sub>n</sub>A<sub>m</sub>'' &le; ''A''<sub>''n''+''m''</sub>}}. Using this equation, one can show {{nowrap|''λ'' &ge; (''A<sub>n</sub>'')<sup>1/''n''</sup>}} for all ''n''. Refinements of this procedure combined with data for ''A<sub>n</sub>'' produce the lower bound given above.

The upper bound is attained by generalizing the inductive method of enumerating polyominoes. Instead of adding one square at a time, one adds a cluster of squares at a time. This is often described as adding ''twigs''. By proving that every ''n''-omino is a sequence of twigs, and by proving limits on the combinations of possible twigs, one obtains an upper bound on the number of ''n''-ominoes. For example, in the algorithm outlined above, at each step we must choose a larger number, and at most three new numbers are added (since at most three unnumbered squares are adjacent to any numbered square). This can be used to obtain an upper bound of 6.75. Using 2.8 million twigs, [[David A. Klarner|Klarner]] and [[Ron Rivest|Rivest]] obtained an upper bound of 4.65,<ref>{{cite journal |last=Klarner |first=D.A. |author2=Rivest, R.L. |year=1973 |title=A procedure for improving the upper bound for the number of ''n''-ominoes |url=http://historical.ncstrl.org/litesite-data/stan/CS-TR-72-263.pdf |url-status=dead |format=PDF of technical report version |journal=[[Canadian Journal of Mathematics]] |volume=25 |issue=3 |pages=585–602 |citeseerx=10.1.1.309.9151 |doi=10.4153/CJM-1973-060-4 |s2cid=121448572 |archive-url=https://web.archive.org/web/20061126083002/http://historical.ncstrl.org/litesite-data/stan/CS-TR-72-263.pdf |archive-date=2006-11-26 |access-date=2007-05-11}}</ref> which was subsequently improved by Barequet and Shalah to 4.5252.<ref name=":0">{{cite journal |last1=Barequet|first1=Gill |last2=Shalah|first2=Mira |title= Improved upper bounds on the growth constants of polyominoes and polycubes |journal=Algorithmica |year=2022 |volume=84 |issue=12 |pages=3559–3586 |doi=10.1007/s00453-022-00948-6|doi-access=free |arxiv=1906.11447 }}</ref>

====Free polyominoes====
Approximations for the number of fixed polyominoes and free polyominoes are related in a simple way. A free polyomino with no [[symmetries]] (rotation or reflection) corresponds to 8 distinct fixed polyominoes, and for large ''n'', most ''n''-ominoes have no symmetries. Therefore, the number of fixed ''n''-ominoes is approximately 8 times the number of free ''n''-ominoes. Moreover, this approximation is exponentially more accurate as ''n'' increases.<ref name="Redelmeier, section 3"/>

===Special classes of polyominoes===
Exact formulas are known for enumerating polyominoes of special classes, such as the class of ''convex'' polyominoes and the class of ''directed'' polyominoes.

The definition of a ''convex'' polyomino is different from the usual definition of [[Convex set|convexity]], but is similar to the definition used for the [[orthogonal convex hull]]. A polyomino is said to be ''vertically'' or ''column convex'' if its intersection with any vertical line is convex (in other words, each column has no holes). Similarly, a polyomino is said to be ''horizontally'' or ''row convex'' if its intersection with any horizontal line is convex.  A polyomino is said to be ''convex'' if it is row and column convex.<ref name=W151>{{cite book | last=Wilf | first=Herbert S. | author-link=Herbert Wilf | title=Generatingfunctionology | edition=2nd | location=Boston, MA | publisher=Academic Press | year=1994 | isbn=978-0-12-751956-2 | zbl=0831.05001 | page=151 }}</ref>

A polyomino is said to be ''directed'' if it contains a square, known as the ''root'', such that every other square can be reached by movements of up or right one square, without leaving the polyomino.

Directed polyominoes,<ref>{{cite journal |last=Bousquet-Mélou |first=Mireille | author-link = Mireille Bousquet-Mélou |year=1998 |title=New enumerative results on two-dimensional directed animals |journal=Discrete Mathematics |volume=180 |issue=1–3 |pages=73–106 |doi=10.1016/S0012-365X(97)00109-X|doi-access=free }}</ref> column (or row) convex polyominoes,<ref>{{cite journal |last=Delest |first=M.-P. |year=1988 |title=Generating functions for column-convex polyominoes |journal=Journal of Combinatorial Theory, Series A |volume=48 |issue=1 |pages=12–31 |doi=10.1016/0097-3165(88)90071-4|doi-access=free }}</ref> and convex polyominoes<ref>{{cite journal |last1=Bousquet-Mélou |first1=Mireille | author1-link = Mireille Bousquet-Mélou |last2=Fédou | first2 = Jean-Marc |year=1995 |title=The generating function of convex polyominoes: The resolution of a ''q''-differential system |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |volume=137 |issue=1–3 |pages=53–75 |doi=10.1016/0012-365X(93)E0161-V|doi-access=free }}</ref> have been effectively enumerated by area ''n'', as well as by some other parameters such as perimeter, using [[generating function]]s.

A polyomino is [[equable shape|equable]] if its area equals its perimeter. An equable polyomino must be made from an [[even number]] of squares; every even number greater than 15 is possible. For instance, the 16-omino in the form of a 4&nbsp;&times;&nbsp;4 square and the 18-omino in the form of a 3&nbsp;&times;&nbsp;6 rectangle are both equable. For polyominoes with 15 squares or fewer, the perimeter always exceeds the area.<ref>{{citation|title=Geometry Labs|first=Henri|last=Picciotto|year=1999|publisher=MathEducationPage.org|page=208|url=https://books.google.com/books?id=7gTMKr7TT6gC&pg=PA208}}.</ref>