Enumeration of L-convex polyominoes by rows and columns
- Autori: Castiglione, G.; Frosini, A.; Restivo, A.; Rinaldi, S.
- Anno di pubblicazione: 2005
- Tipologia: Articolo in rivista (Articolo in rivista)
- OA Link: http://hdl.handle.net/10447/25320
In this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once. Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter 2(n+2) satisfies the rational recurrence relation fn =4fn-1 -2fn-2, with f0 =1, f1 =2, f2 =7. Moreover, we give a combinatorial interpretation of this statement. In the last section, we present some open problems