Gill Barequet, Micha Moffie, Ares Ribó, and Günter Rote:

Counting polyominoes on twisted cylinders

  1. Discrete Mathematics and Theoretical Computer Science AE (2005), 369-374. Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb'05), 2005, Berlin, Germany. Editor: Stefan Felsner.
  2. INTEGERS: The Electronic Journal of Combinatorial Number Theory 6 (2006), article #A22, 37 pages.


Using numerical methods, we analyze the growth in the number of polyominoes on a twisted cylinder as the number of cells increases. These polyominoes are related to classical polyominoes (connected subsets of a square grid) that lie in the plane. We thus obtain an improved lower bound of 3.980137 on the growth rate of the number of polyominoes, which is also known as Klarner's constant. We use a dynamic programming approach. For storing information about partial polyominos, we make use of a bijection between "states" of our system and Motzkin paths.
  PostScript file (gzipped)   pdf file
other papers about this subject

Note after publication (2018)

Our main tool for certifying the quality of the eigenvalue approximation, Lemma 2 in the paper 1 and Lemma 9 in the paper 2, turned out to be a classical result, known under the name Collatz–Wielandt inequality.

Last update: November 22, 2018.