Asymptotics of Z-convex polyominoes

¹ School of Mathematics and Statistics, The University of Melbourne, Australia
² Department of Theoretical and Applied Science, University of Insubria, Italy

^* Corresponding author: paolo.massazza@uninsubria.it

Received: 2 December 2022
Accepted: 23 February 2024

Abstract

The degree of convexity of a convex polyomino P is the smallest integer k such that any two cells of P can be joined by a monotone path inside P with at most k changes of direction. In this paper we show that one can compute in polynomial time the number of polyominoes of area n and degree of convexity at most 2 (the so-called Z-convex polyominoes). The integer sequence that we have computed allows us to conjecture the asymptotic number a_n of Z-convex polyominoes of area n, ɑ_n ∼ C·exp(π)√11n/4⁄n^3/2.