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

CASTIGLIONE G, FROSINI A, RESTIVO A, RINALDI S (2005). Enumeration of L-convex polyominoes by rows and columns. THEORETICAL COMPUTER SCIENCE, 347(1-2), 336-352 [10.1016/j.tcs.2005.06.031].

Enumeration of L-convex polyominoes by rows and columns

CASTIGLIONE, Giuseppa;RESTIVO, Antonio;
2005-01-01

Abstract

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
2005
CASTIGLIONE G, FROSINI A, RESTIVO A, RINALDI S (2005). Enumeration of L-convex polyominoes by rows and columns. THEORETICAL COMPUTER SCIENCE, 347(1-2), 336-352 [10.1016/j.tcs.2005.06.031].
File in questo prodotto:
File Dimensione Formato  
restivo.pdf

accesso aperto

Dimensione 323.45 kB
Formato Adobe PDF
323.45 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/25320
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? 23
social impact