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