engleski

Two generalizations of column-convex polygons

Column-convex polygons were first counted by area several decades ago, and the result was found to be a simple, rational, generating function. The aim of our recent work (summarized in this paper) is to 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 generalisation, namely to 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 write down the area generating functions of those two classes and then give an asymptotic analysis. The growth constants of the both classes are greater than the growth constant of column-convex polyominoes.

column-convex polygon; level m column-subconvex polyomino; simple-2-column polyomino; area generating function; growth constant

nije evidentirano