The area generating function for simple-2-column polyominoes with hexagonal cells

S. Feretic, N. Trinajstic

Published 2009-11-13Version 1

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 chapter 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 to 2-column polyominoes, is unlikely to be solvable. We therefore define a class of polyominoes which interpolates between column-convex polygons and 2-column polyominoes. We derive the area generating function of that class, using an extension of an existing algorithm. The growth constant of the new class is greater than the growth constant of column-convex polygons. A rather tight lower bound on the growth constant complements a compelling numerical analysis.