The number of $k$-parallelogram polyominoes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2013

The number of $k$-parallelogram polyominoes

Résumé

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
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

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

Identifiants

Citer

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⟩
87 Consultations
645 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More