Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: On the generation and enumeration of some classes of convex polyominoes. | On the generation and enumeration of some classes of convex polyominoes A. Del Lungo E. Duchi École des Hautes Etudes en Sciences Sociales 54 Boulevard Raspail 75006 Paris France duchi@ A. Frosini and S. Rinaldi Dipartimento di Scienze Matematiche e Informatiche Pian dei Mantellini 44 Siena Italy frosini rinaldi @ Submitted Jul 29 2003 Accepted Jul 5 2004 Published Sep 13 2004 Mathematics Subject Classifications 05A15 Abstract ECO is a method for the recursive generation and thereby also the enumeration of classes of combinatorial objects. It has already found successful application in recent literature both to the exhaustive generation and to the uniform random generation of various objects classified according to several parameters of interest as well as to their enumeration. In this paper we extend this approach to the generation and enumeration of some classes of convex polyominoes. We begin with a review of the ÉCO method and of the closely related notion of a succession rule. From this background we develop the following principal findings i ÉCO constructions for both column-convex and convex polyominoes ii translations of these constructions into succession rules iii the consequent deduction of the generating functions of column-convex and of convex polyominoes according to their semi-perimeter first of all analytically by means of the so-called kernel method and then in a more novel manner by drawing on some ideas of Fedou and Garcia iv algorithms for the exhaustive generation of column convex and of convex poly-ominoes which are based on the ÉCO constructions of these object and which are shown to run in constant amortized time. died 1st June 2003 THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R60 1 1 Introduction A polyomino is a finite union of cells of the square lattice Z X Z with simply connected interior. In the half century since Solomon Golomb used the term in his seminal article 22 the study of polyominoes has proved a fertile .
