The number of $k$-parallelogram polyominoes

Résumé : 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}$.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.1113-1124, 2013, DMTCS Proceedings
Liste complète des métadonnées

https://hal.inria.fr/hal-01229685
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:19:55
Dernière modification le : mardi 7 mars 2017 - 15:23:34
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:38:08

Fichier

dmAS0194.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229685, version 1

Collections

Citation

Daniela Battaglino, Jean-Marc Fédou, Simone Rinaldi, Samanta Socci. The number of $k$-parallelogram polyominoes. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.1113-1124, 2013, DMTCS Proceedings. 〈hal-01229685〉

Partager

Métriques

Consultations de la notice

66

Téléchargements de fichiers

67