The number of $k$-parallelogram polyominoes - Archive ouverte HAL Access content directly
Conference Papers Discrete Mathematics and Theoretical Computer Science Year : 2013

The number of $k$-parallelogram polyominoes

(1, 2) , (1) , (2) , (2)
1
2

Abstract

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}$.
Un polyomino convexe est dit $k$-$\textit{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-classe des polyominos $k$-convexes qui sont également parallélogramme, que nous appelons $k$-$\textit{parallélogrammes}$. 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 termes des $\textit{polynômes de Fibonacci}$.
Fichier principal
Vignette du fichier
dmAS0194.pdf (375.9 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

hal-01229685 , version 1 (17-11-2015)

Identifiers

Cite

Daniela Battaglino, Jean-Marc Fédou, Simone Rinaldi, Samanta Socci. The number of $k$-parallelogram polyominoes. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.1113-1124, ⟨10.46298/dmtcs.2370⟩. ⟨hal-01229685⟩
67 View
508 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More