<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue1" %>
An Object Grammar for Column-Convex Polyominoes
E. Duchi1 and S. Rinaldi2
1École des Hautes Études en Sciences Sociales, Centre d'Analyse et de Mathématique Sociales, Bureau 231, 54, bd Raspail, 75270 Paris Cedex 06, France
enrica.duchi@ehess.fr
2Università di Siena, Dipartimento di Scienze Matematiche ed Informatiche, via del Capitano, 15, 53100 Siena, Italy
rinaldi@unisi.it
Annals of Combinatorics 8 (1) p.27-36 March, 2004
AMS Subject Classification: 05A15
Abstract:
In this paper we propose an object grammar decomposition for the classes of column-convex, and directed column-convex polyominoes. As a consequence, we obtain the enumeration of such classes according to the semi-perimeter, thus giving a natural explanation of the fact that the generating functions of both the classes are algebraic.
Keywords: enumeration, column-convex polyominoes

References:

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

2. R. Brak, A.J. Guttmann, and I.G. Enting, Exact solution of the row-convex polygon perimeter generating function, J. Phys. A 23 (1990) 2319–2326.

3. M. Delest, Generating functions for column-convex polyominoes, J. Combin. Theory, Ser. A 48 (1) (1988) 12–31.

4. M. Delest and S. Dulucq, Enumeration of directed column-convex animals with a given perimeter and area, Croat. Chem. Acta. 66 (1993) 59–80.

5. I. Dutour, Grammaires d'objets: énumération, bijections et génération aléatoire, Thèse de l'Université de Bordeaux I, 1996.

6. I. Dutour and J.M. Fédou, Object grammars and bijections, Theoret. Comput. Sci. 290 (2003) 1915–1929.

7. I. Dutour and J.M. Fédou, Object grammars and random generation, Discrete Math. Theoret. Comput. Sci. 2 (1998) 47–61.

8. S. Feretic, A new way of counting the column-convex polyominoes by perimeter, Discrete Math. 180 (1998) 173–184.

9. S. Feretić and D. Svrtan, On the number of column-convex polyominoes with given perimeter and number of columns, Proceedings of the 5-th Conference Formal Power Series and Algebraic Combinatorics, Florence, 1993, pp. 201–214.

10. K.Y. Lin and S.J. Chang, Rigorous results for the number of convex polygons on the square and honeycomb lattices, J. Phys. A 21 (1988) 2635–2642.

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