Combinatorial aspects of -convex polyominoes

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 f n 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.