6533b7d4fe1ef96bd1263330

RESEARCH PRODUCT

Enumeration of L-convex polyominoes by rows and columns

Antonio RestivoSimone RinaldiGiusi CastiglioneAndrea Frosini

subject

Discrete mathematicsRecurrence relationECO methodGeneral Computer SciencePolyominoGenerating functionRegular polygonRow and column spacesTheoretical Computer ScienceInterpretation (model theory)Generating functionsCombinatoricsSection (fiber bundle)Path (graph theory)Convex polyominoesComputer Science(all)Mathematics

description

In this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once.Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the rational recurrence relation fn = 4fn-1 - 2fn-2, with f0 = 1, f1 = 2, f2 = 7. Moreover, we give a combinatorial interpretation of this statement. In the last section, we present some open problems.

yearjournalcountryeditionlanguage
2005-11-01Theoretical Computer Science
https://doi.org/10.1016/j.tcs.2005.06.031