On t-fold Totally-Concave Polyominoes

Abstract

A t-fold totally concave polyomino (t-TCP) is an edge-wise connected collection of cells of the square lattice with t or more gaps in every row and column. We describe an efficient algorithm for counting 1-TCPs (modulo translation) by area, and comment on its extension to t > 1. We prove that the minimum area of a t-TCP is 21 for t = 1, 50 for t = 2, and 6(t+1)2 −1 for t > 2. We show that the counting sequence κt(n) of t-TCPs of area n satisfies λn+o(n) as n → ∞, where λ is the same growth constant as for all polyominoes. From this, we prove that the ratio of successive terms converges to λ. For each t, we obtain an explicit constant θt such that κt(n) ≥ n−θtλn for infinitely-many values of n, complementing the fact that κt(n) ≤ n−1/2λn for every n ∈ N. We also briefly discuss the relation of t-TCPs to similar models from statistical physics.