Glasnik Matematicki, Vol. 45, No.2 (2010), 325-346.

POLYOMINOES WITH NEARLY CONVEX COLUMNS: AN UNDIRECTED MODEL

Svjetlan Feretić and Anthony J. Guttmann

ARC Centre of Excellence for Mathematics and Statistics of Complex Systems, Department of Mathematics and Statistics, The University of Melbourne, Parkville, Victoria 3010, Australia
e-mail: tonyg@ms.unimelb.edu.au

Abstract.   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.

2000 Mathematics Subject Classification.   05B50, 05A15.

Key words and phrases.   Polyomino, hexagonal cell, nearly convex column, area generating function, growth constant.

DOI: 10.3336/gm.45.2.03

References:

1. M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996), 1-25.
   MathSciNet     CrossRef

2. M. Bousquet-Mélou, Rapport Scientifique pour obtenir l'habilitation \`a diriger des recherches, Report No. 1154-96, LaBRI, Université Bordeaux I, 1996.

3. M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers, Discrete Math. 258 (2002), 235-274.
   MathSciNet     CrossRef

4. S. Feretić, Polyominoes with nearly convex columns: A semi-directed model, Ars Math. Contemp., submitted, arXiv:0910.4573v2.

5. S. Feretić and A. J. Guttmann, Two generalizations of column-convex polygons, J. Phys. A 42 (2009), no. 48, 485003, 17 pp.
   MathSciNet     CrossRef

6. S. Feretić and D. Svrtan, On the number of column-convex polyominoes with given perimeter and number of columns, in: Proc. of the Fifth FPSAC Conference (eds. A. Barlotti, M. Delest and R. Pinzani), Firenze, 1993, 201-214.

7. A. J. Guttmann, Analysis of coefficients, in: Phase Transitions and Critical Phenomena, Vol. 13 (C. Domb and J. L. Lebowitz, eds.), Academic Press, New York, 1989, 1-234.

8. D. A. Klarner, Cell growth problems, Canad. J. Math. 19 (1967), 851-863.
   MathSciNet    

9. D. A. Klarner and R. L. Rivest, A procedure for improving the upper bound for the number of n-ominoes, Canad. J. Math. 25 (1973), 585-602.
   MathSciNet    

10. N. Madras, A pattern theorem for lattice clusters, Ann. Comb. 3 (1999), 357-384.
    MathSciNet     CrossRef

11. H. N. V. Temperley, Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules, Phys. Rev. (2) 103 (1956), 1-16.
    MathSciNet    

12. M. Vöge and A. J. Guttmann, On the number of hexagonal polyominoes, Theoret. Comput. Sci. 307 (2003), 433-453.
    MathSciNet     CrossRef

13. Polygons, Polyominoes and Polycubes (ed. A. J. Guttmann), Lecture Notes in Phys. 775, Springer, Berlin, 2009.

14. http://www.gradri.hr/adminmax/files/staff/A_2.mw (This file is a Maple 9.5 worksheet. The file can also be obtained from Svjetlan Feretić via e-mail.)