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. THEORETICAL COMPUTER SCIENCE, 347(1-2), 336-352 [10.1016/j.tcs.2005.06.031].

Enumeration of L-convex polyominoes

RINALDI, SIMONE
2005

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.
Castiglione, G., Frosini, A., Restivo, A., & Rinaldi, S. (2005). Enumeration of L-convex polyominoes. THEORETICAL COMPUTER SCIENCE, 347(1-2), 336-352 [10.1016/j.tcs.2005.06.031].
File in questo prodotto:
File Dimensione Formato  
lconvex.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 364.37 kB
Formato Adobe PDF
364.37 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/11365/3968
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo