The number of k-parallelogram polyominoes

A convex polyomino is k-convex if every pair of its cells can be connected by means of a monotone path, internal to the polyomino, and having at most k changes of direction. The number k-convex polyominoes of given semi-perimeter has been determined only for small values of k, precisely k = 1; 2. In this paper we consider the problem of enumerating a subclass of k-convex polyominoes, precisely the k-convex parallelogram polyominoes (briefly, k-parallelogram polyominoes). For each k ≥ 1, we give a recursive decomposition for the class of k- parallelogram polyominoes, and then use it to obtain the generating function of the class, which turns out to be a rational function. We are then able to express such a generating function in terms of the Fibonacci polynomials. © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS).