Glasnik Matematicki, Vol. 45, No.2 (2010), 325-346.
POLYOMINOES WITH NEARLY CONVEX COLUMNS: AN UNDIRECTED MODEL
Svjetlan Feretić and Anthony J. Guttmann
Faculty of Civil Engineering,
University of Rijeka,
Viktora Cara Emina 5, 51000 Rijeka,
ARC Centre of Excellence for Mathematics and Statistics of Complex Systems,
Department of Mathematics and Statistics,
The University of Melbourne,
Parkville, Victoria 3010,
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.
Key words and phrases. Polyomino, hexagonal cell, nearly convex column, area generating function, growth constant.
Full text (PDF) (free access)
- M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996), 1-25.
- M. Bousquet-Mélou, Rapport Scientifique pour obtenir l'habilitation \`a diriger des recherches, Report No. 1154-96, LaBRI, Université Bordeaux I, 1996.
- M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers, Discrete Math. 258 (2002), 235-274.
- S. Feretić, Polyominoes with nearly convex columns: A semi-directed model, Ars Math. Contemp., submitted, arXiv:0910.4573v2.
- S. Feretić and A. J. Guttmann, Two generalizations of column-convex polygons, J. Phys. A 42 (2009), no. 48, 485003, 17 pp.
- 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.
- 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.
- D. A. Klarner, Cell growth problems, Canad. J. Math. 19 (1967), 851-863.
- 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.
- N. Madras, A pattern theorem for lattice clusters, Ann. Comb. 3 (1999), 357-384.
- 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.
- M. Vöge and A. J. Guttmann, On the number of hexagonal polyominoes, Theoret. Comput. Sci. 307 (2003), 433-453.
- Polygons, Polyominoes and Polycubes (ed. A. J. Guttmann), Lecture Notes in Phys. 775, Springer, Berlin, 2009.
(This file is a Maple 9.5 worksheet. The file can also be obtained from Svjetlan Feretić via e-mail.)
Glasnik Matematicki Home Page