Editing Polyomino (section)

===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"/>