An asymptotic lower bound on the number of polyominoes

Vuong Bui

Published 2022-11-27Version 1

Let $P(n)$ denote the number of polyominoes of $n$ cells, we show that there exist some positive numbers $A,T$ so that for every $n$, \[ P(n) \ge An^{-T\log n} \lambda^n, \] where $\lambda$ is Klarner's constant, that is $\lambda=\lim_{n\to\infty} \sqrt[n]{P(n)}$. This is somewhat a step toward the well known conjecture that there exist positive $A,T$ so that $P(n)\sim An^{-T}\lambda^n$ for every $n$. Beside the above theoretical result, we also conjecture that the ratio of the number of inconstructible polyominoes over $P(n)$ is decreasing, by observing this behavior for the available values. The conjecture opens a nice approach to bounding $\lambda$, since if it is the case, we can conclude that \[ \lambda < 4.1141, \] which is quite close to the currently best lower bound $\lambda > 4.0025$ and largely improves the currently best upper bound $\lambda < 4.5252$. The approach is merely analytically manipulating the known or likely properties of the function $P(n)$, instead of giving new insights of the structure of polyominoes.