Izvorni znanstveni članak

https://doi.org/10.3336/gm.45.2.03

Polyominoes with nearly convex columns: An undirected model

Svjetlan Feretić ; Faculty of Civil Engineering, University of Rijeka, Viktora Cara Emina 5, 51000 Rijeka, Croatia
Anthony J. Guttmann orcid.org/0000-0003-2209-7192 ; ARC Centre of Excellence for Mathematics and Statistics of Complex Systems, Department of Mathematics and Statistics, The University of Melbourne, Parkville, Victoria 3010, Australia

Sažetak

Column-convex polyominoes were introduced in 1950's by Temperley, a mathematical physicist working on ``lattice gases''. By now, column-convex polyominoes are a popular and well-understood model. There exist several generalizations of column-convex polyominoes. However, the enumeration by area has been done for only one of the said generalizations, namely for multi-directed animals. In this paper, we introduce a new sequence of supersets of column-convex polyominoes. Our model (we call it level m column-subconvex polyominoes) is defined in a simple way: every column has at most two connected components and, if there are two connected components, the gap between them consists of at most m cells. We focus on the case when cells are hexagons and we compute the area generating functions for the levels one and two. Both of those generating functions are q-series, whereas the area generating function of column-convex polyominoes is a rational function. The growth constants of level one and level two level two column-subconvex polyominoes are 4.319139 and 4.509480, respectively. For comparison, the growth constants of column-convex polyominoes, multi-directed animals and all polyominoes are 3.863131, 4.587894 and 5.183148, respectively.

Ključne riječi

Polyomino; hexagonal cell; nearly convex column; area generating function; growth constant

Hrčak ID:

62691

URI

https://hrcak.srce.hr/62691

Datum izdavanja:

24.12.2010.

Posjeta: 1.278 *