Gill Barequet, Micha Moffie, Ares Ribó, and Günter Rote:
Counting polyominoes on twisted cylinders
- 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.
→BibTeX
- INTEGERS: The
Electronic Journal of
Combinatorial Number Theory 6 (2006), article #A22, 37 pages.
doi:10.5281/zenodo.8275374
→BibTeX
Abstract
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.
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: March 5, 2024.