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 $\textit{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.
On the complexity of Jensen's algorithm for counting fixed polyominoes
3 Documents citing this article
Source : OpenCitations
Aleksandrowicz, Gadi; Asinowski, Andrei; Barequet, Gill; Barequet, Ronnie, 2014, Formulae For Polyominoes On Twisted Cylinders, Language And Automata Theory And Applications, pp. 76-87, 10.1007/978-3-319-04921-2_6.
Castiglione, Giusi; Frosini, A.; Munarini, E.; Restivo, A.; Rinaldi, Simone, 2007, Combinatorial Aspects Of L-convex Polyominoes, European Journal Of Combinatorics, 28, 6, pp. 1724-1741, 10.1016/j.ejc.2006.06.020.
Salvi, Anelize Zomkowski; Simoni, Roberto; Martins, Daniel, 2012, Enumeration Problems: A Bridge Between Planar Metamorphic Robots In Engineering And Polyforms In Mathematics, Advances In Reconfigurable Mechanisms And Robots I, pp. 25-34, 10.1007/978-1-4471-4141-9_3.