We improve the lower bounds on Klarner's constant, which describes the exponential growth rate of the number of polyominoes (connected subsets of grid squares) with a given number of squares. We achieve this by analyzing polyominoes on a different surface, a so-called twisted cylinder by the transfer matrix method. A bijective representation of the "states'' of partial solutions is crucial for allowing a compact representation of the successive iteration vectors for the transfer matrix method.
Gadi Aleksandrowicz;Andrei Asinowski;Gill Barequet;Ronnie Barequet, Lecture notes in computer science, Formulae for Polyominoes on Twisted Cylinders, pp. 76-87, 2014, 10.1007/978-3-319-04921-2_6.
Anelize Zomkowski Salvi;Roberto Simoni;Daniel Martins, Springer eBooks, Enumeration Problems: A Bridge Between Planar Metamorphic Robots in Engineering and Polyforms in Mathematics, pp. 25-34, 2012, 10.1007/978-1-4471-4141-9_3.
Cristopher Moore;Stephan Mertens, Oxford University Press eBooks, When Formulas Freeze: Phase Transitions in Computation, pp. 723-818, 2011, 10.1093/acprof:oso/9780199233212.003.0014.
Cristopher Moore;Stephan Mertens, Oxford University Press eBooks, Who is the Hardest One of All? NP-Completeness, pp. 127-172, 2011, 10.1093/acprof:oso/9780199233212.003.0005.