THE NUMBER OF Z CONVEX POLYOMINOES

Description

Niveau: Supérieur
ar X iv :m at h. CO /0 60 21 24 v 1 7 F eb 2 00 6 THE NUMBER OF Z-CONVEX POLYOMINOES ENRICA DUCHI, SIMONE RINALDI, AND GILLES SCHAEFFER Abstract. In this paper we consider a restricted class of polyominoes that we call Z-convex polyominoes. Z-convex polyominoes are polyominoes such that any two pairs of cells can be connected by a monotone path making at most two turns (like the letter Z). In particular they are convex polyominoes, but they appear to resist standard decompositions. We propose a construction by “inflation” that allows to write a system of functional equations for their generating functions. The generating function P (t) of Z-convex polyominoes with respect to the semi-perimeter turns out to be algebraic all the same and surprisingly, like the generating function of convex polyominoes, it can be expressed as a rational function of t and the generating function of Catalan numbers. 1. Introduction 1.1. Convex polyominoes. In the plane Z ? Z a cell is a unit square, and a polyomino is a finite connected union of cells having no cut point. Polyominoes are defined up to translations. A column (row) of a polyomino is the intersection between the polyomino and an infinite strip of cells lying on a vertical (horizontal) line.

• centered convex


• cells can


• t2 ?


• row touching


• rational power series


• n≥0 gntn


• catalan generating


• convex polyominoes


• highlighted cells

Informations

• Publié par: chaeh
• Nombre de lectures: 8
• Langue: English

Extrait

THENUMBEROFZ-CONVEXPOLYOMINOES ENRICADUCHI,SIMONERINALDI,ANDGILLESSCHAEFFER Abstract.Inthispaperweconsiderarestrictedclassofpolyominoesthatwecall Z -convex polyominoes. Z -convexpolyominoesarepolyominoessuchthatanytwopairsofcellscanbe connectedbyamonotonepathmakingatmosttwoturns(liketheletterZ).Inparticular theyareconvexpolyominoes,buttheyappeartoresiststandarddecompositions.Wepropose aconstructionby“inflation”thatallowstowriteasystemoffunctionalequationsfortheir generatingfunctions.Thegeneratingfunction P ( t )of Z -convexpolyominoeswithrespectto thesemi-perimeterturnsouttobealgebraicallthesameandsurprisingly,likethegenerating functionofconvexpolyominoes,itcanbeexpressedasarationalfunctionof t andthegenerating functionofCatalannumbers. 1. Introduction 1.1. Convexpolyominoes. Intheplane Z × Z a cell isaunitsquare,anda polyomino isa finiteconnectedunionofcellshavingnocutpoint.Polyominoesaredefineduptotranslations.A column ( row )ofapolyominoistheintersectionbetweenthepolyominoandaninfinitestripofcells lyingonavertical(horizontal)line.Forthemaindefinitionsandresultsconcerningpolyominoes wereferto[S]and,forfrenchawarereaders,to[BM].InventedbyGolomb[G2]whocoinedthe termpolyomino,thesecombinatorialobjectsarerelatedtomanymathematicalproblems,such astilings[BN,G1],orgames[Ga]amongmanyothers.Theenumerationproblemforgeneral polyominoesisdifficulttosolveandstillopen.Thenumbera n ofpolyominoeswithncellsis knownupton=56[JG]andasymptotically,thesenumberssatisfytherelationlim n (a n ) 1/n =µ, 3.96<µ<4.64,wherethelowerboundisarecentimprovementof[BMRR]. (a)(b) Figure1.(a)acolumn-convex(butnotconvex)polyomino;(b)aconvexpolyomino. Inordertoprobefurther,severalsubclassesofpolyominoeshavebeenintroducedonwhichto honeenumerationtechniques.Onenaturalsubclassisthatof convex polyominoes.Apolyomino issaidtobe column-convex [ row-convex ]whenitsintersectionwithanyvertical[horizontal]line ofcellsinthesquarelatticeisconnected(seeFig.1(a)),and convex whenitisbothcolumnand row-convex(seeFig.1(b)).Theareaofapolyominoisjustthenumberofcellsitcontains,while itssemi-perimeterishalfthelengthoftheboundary.Thus,inaconvexpolyominothesemi- perimeteristhesumofthenumbersofitsrowsandcolumns.Moreover,anyconvexpolyomino 2000MathematicsSubjectClassification.Primary05A15;Secondary82B41. Keywordsandphrases.Enumeration,algebraicgeneratingfunctions,recursivedecomposition. TheauthorsacknowledgesupportfromthefrenchANRundertheSADAproject. 1