On the shape of permutomino tiles

Abstract : In this paper we explore the connections between two classes of polyominoes, namely the permu- tominoes and the pseudo-square polyominoes. A permutomino is a polyomino uniquely determined by a pair of permutations. Permutominoes, and in particular convex permutominoes, have been considered in various kinds of problems such as: enumeration, tomographical reconstruction, and algebraic characterization. On the other hand, pseudo-square polyominoes are a class of polyominoes tiling the the plane by translation. The characterization of such objects has been given by Beauquier and Nivat, who proved that a polyomino tiles the plane by translation if and only if it is a pseudo-square or a pseudo- hexagon. In particular, a polyomino is pseudo-square if its boundary word may be factorized as XY Xﰅ Yﰅ, where Xﰅ denotes the path X traveled in the opposite direction. In this paper we relate the two concepts by considering the pseudo-square polyominoes which are also convex permutominoes. By using the Beauquier-Nivat characterization we provide some geometrical and combinatorial properties of such objects, and we show for any fixed X, each word Y such that XYXﰅYﰅ is pseudo-square is prefix of an infinite word Y∞ with period 4|X|N |X|E. Also, we show that XY XﰅYﰅ are centrosymmetric, i.e. they are fixed by rotation of angle π. The proof of this fact is based on the concept of pseudoperiods, a natural generalization of periods.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2013, pp.2316-2327
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

http://hal.univ-grenoble-alpes.fr/hal-00944063
Contributeur : Laurent Vuillon <>
Soumis le : lundi 10 février 2014 - 10:04:38
Dernière modification le : jeudi 11 janvier 2018 - 06:12:26
Document(s) archivé(s) le : dimanche 11 mai 2014 - 01:00:10

Fichier

pspermu_3_2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00944063, version 1

Collections

Citation

Alexandre Blondin Masse, Andrea Frosini, Simone Rinaldi, Laurent Vuillon. On the shape of permutomino tiles. Discrete Applied Mathematics, Elsevier, 2013, pp.2316-2327. 〈hal-00944063〉

Partager

Métriques

Consultations de la notice

490

Téléchargements de fichiers

1043