Authors: Daniela Battaglino ^1,2; Jean-Marc Fédou ¹; Simone Rinaldi ²; Samanta Socci ²

• 1 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe MC3
• 2 Dipartimento di Matematica e Informatica [Siena]

A convex polyomino is $k$-$\textit{convex}$ if every pair of its cells can be connected by means of a $\textit{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$-$\textit{convex parallelogram polyominoes}$ (briefly, $k$-$\textit{parallelogram polyominoes}$). For each $k \geq 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 $\textit{Fibonacci polynomials}$.