We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can be connected with an “L” shaped path in one of its four cyclic orientations. The paper proves bijectively that the number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the linear recurrence relation f(n+2) = 4 f(n+1) − 2 f(n), by first establishing a recurrence of the same form for the cardinality of the “2-compositions” of a natural number n, a simple generalization of the ordinary compositions of n. Then, such 2-compositions are studied and bijectively related to certain words of a regular language over four letters which is in turn bijectively related to L-convex polyominoes. In the last section we give a solution to the open problem of determining the generating function of the area of L-convex polyominoes.

Castiglione, G., Frosini, A., Munarini, E., Restivo, A., & Rinaldi, S. (2007). Combinatorial aspects of L-convex polyominoes. EUROPEAN JOURNAL OF COMBINATORICS, 28(6), 1724-1741 [10.1016/j.ejc.2006.06.020].

Combinatorial aspects of L-convex polyominoes

RINALDI, SIMONE
2007

Abstract

We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can be connected with an “L” shaped path in one of its four cyclic orientations. The paper proves bijectively that the number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the linear recurrence relation f(n+2) = 4 f(n+1) − 2 f(n), by first establishing a recurrence of the same form for the cardinality of the “2-compositions” of a natural number n, a simple generalization of the ordinary compositions of n. Then, such 2-compositions are studied and bijectively related to certain words of a regular language over four letters which is in turn bijectively related to L-convex polyominoes. In the last section we give a solution to the open problem of determining the generating function of the area of L-convex polyominoes.
Castiglione, G., Frosini, A., Munarini, E., Restivo, A., & Rinaldi, S. (2007). Combinatorial aspects of L-convex polyominoes. EUROPEAN JOURNAL OF COMBINATORICS, 28(6), 1724-1741 [10.1016/j.ejc.2006.06.020].
File in questo prodotto:
File Dimensione Formato  
lconv2.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 609.09 kB
Formato Adobe PDF
609.09 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/35953
 Attenzione

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