Combinatorial aspects of LL-convex polyominoes

We consider the class of LL-convex polyominoes, i.e. those polyominoes in which any two cells can be connected with an “LL” shaped path in one of its four cyclic orientations. The paper proves bijectively that the number fnfn of LL-convex polyominoes with perimeter 2(n+2)2(n+2) satisfies the linear recurrence relation fn+2=4fn+1−2fnfn+2=4fn+1−2fn, by first establishing a recurrence of the same form for the cardinality of the “2-compositions” of a natural number nn, a simple generalization of the ordinary compositions of nn. 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 LL-convex polyominoes. In the last section we give a solution to the open problem of determining the generating function of the area of LL-convex polyominoes.