Two generalizations of column-convex polygons
Svjetlan Feretić, Anthony John Guttmann · Journal of Physics A Mathematical and Theoretical · 2009
Column-convex polygons were first counted by area several decades ago, and the result was found to be a simple, rational, generating function. In this work we generalize that result. Let a p -column polyomino be a polyomino whose columns can have 1, 2, ..., p connected components. Then column-convex polygons are equivalent to 1-convex polyominoes. The area generating function of even the simplest generalization, namely 2-column polyominoes, is unlikely to be solvable. We therefore define two classes of polyominoes which interpolate between column-convex polygons and 2-column polyominoes. We derive the area generating functions of those two classes, using extensions of existing algorithms. The growth constants of both classes are greater than the growth constant of column-convex polyominoes. Rather tight lower bounds on the growth constants complement a comprehensive asymptotic analysis.