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.
Résumé. Un polyomino convexe est dit k-convexe lorsqu'on peut relier tout couple de cellules par un chemin monotone ayant au plus k changements de direction. Le nombre de polyominos k-convexes n'est connu que pour les petites valeurs de k=1,2. Dans cet article, nous énumérons la sous classes des polyominos k-convexes qui sont également parallélogramme, que nous appelons k-parallelogrammes. Nous donnons une décomposition récursive de la classe des polyominos k-parallélogrammes pour chaque k, et en déduisons la fonction génératrice, rationnelle, selon le demi-périmètre. Nous donnons enfin une expression de cette fonction génératrice en terme des polynômes de Fibonacci.