Combinatorial aspects of L-convex polyominoes

Antonio Restivo, Giuseppa Castiglione, Munarini, Frosini, Rinaldi

Risultato della ricerca: Article

22 Citazioni (Scopus)

Abstract

We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can beconnected with an “L” shaped path in one of its four cyclic orientations. The paper proves bijectively thatthe number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the linear recurrence relationfn+2 = 4 fn+1 - 2 fn, 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 fourletters which is in turn bijectively related to L-convex polyominoes. In the last section we give a solution tothe open problem of determining the generating function of the area of L-convex polyominoes.
Lingua originaleEnglish
pagine (da-a)1724-1741
Numero di pagine18
RivistaEuropean Journal of Combinatorics
Volume28
Stato di pubblicazionePublished - 2007

Fingerprint

Polyominoes
Linear Recurrence
Regular Languages
Perimeter
Natural number
Recurrence
Generating Function
Cardinality
Open Problems
Path
Cell

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Cita questo

Combinatorial aspects of L-convex polyominoes. / Restivo, Antonio; Castiglione, Giuseppa; Munarini; Frosini; Rinaldi.

In: European Journal of Combinatorics, Vol. 28, 2007, pag. 1724-1741.

Risultato della ricerca: Article

@article{cb1f92c841894bfd8eb1b0ad6a9a6532,
title = "Combinatorial aspects of L-convex polyominoes",
abstract = "We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can beconnected with an “L” shaped path in one of its four cyclic orientations. The paper proves bijectively thatthe number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the linear recurrence relationfn+2 = 4 fn+1 - 2 fn, 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 fourletters which is in turn bijectively related to L-convex polyominoes. In the last section we give a solution tothe open problem of determining the generating function of the area of L-convex polyominoes.",
author = "Antonio Restivo and Giuseppa Castiglione and Munarini and Frosini and Rinaldi",
year = "2007",
language = "English",
volume = "28",
pages = "1724--1741",
journal = "European Journal of Combinatorics",
issn = "0195-6698",
publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Combinatorial aspects of L-convex polyominoes

AU - Restivo, Antonio

AU - Castiglione, Giuseppa

AU - Munarini, null

AU - Frosini, null

AU - Rinaldi, null

PY - 2007

Y1 - 2007

N2 - We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can beconnected with an “L” shaped path in one of its four cyclic orientations. The paper proves bijectively thatthe number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the linear recurrence relationfn+2 = 4 fn+1 - 2 fn, 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 fourletters which is in turn bijectively related to L-convex polyominoes. In the last section we give a solution tothe open problem of determining the generating function of the area of L-convex polyominoes.

AB - We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can beconnected with an “L” shaped path in one of its four cyclic orientations. The paper proves bijectively thatthe number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the linear recurrence relationfn+2 = 4 fn+1 - 2 fn, 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 fourletters which is in turn bijectively related to L-convex polyominoes. In the last section we give a solution tothe open problem of determining the generating function of the area of L-convex polyominoes.

UR - http://hdl.handle.net/10447/17789

M3 - Article

VL - 28

SP - 1724

EP - 1741

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -