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 fn+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 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
CASTIGLIONE, Giuseppa;RESTIVO, Antonio;
2007-01-01
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 fn+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 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.File | Dimensione | Formato | |
---|---|---|---|
castiglione.pdf
accesso aperto
Dimensione
572.21 kB
Formato
Adobe PDF
|
572.21 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.