Gill Barequet ; Micha Moffie ; Ares Ribó ; Günter Rote - Counting Polyominoes on Twisted Cylinders

dmtcs:3446 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3446
Counting Polyominoes on Twisted CylindersArticle

Authors: Gill Barequet 1; Micha Moffie 1; Ares Ribó 2; Günter Rote ORCID2

  • 1 Department of Computer Science [Haifa]
  • 2 Institut für Informatik [Berlin]

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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: polyomino,combinatorial counting,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

26 Documents citing this article

Consultation statistics

This page has been seen 193 times.
This article's PDF has been downloaded 211 times.