Combinatorial aspects of L-convex polyominoes

Antonio Restivo, Giuseppa Castiglione, Munarini, Frosini, Rinaldi

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)1724-1741
Number of pages18
JournalEuropean Journal of Combinatorics
Publication statusPublished - 2007

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Combinatorial aspects of L-convex polyominoes'. Together they form a unique fingerprint.

Cite this