Name
Abstract | ||
|---|---|---|
In this paper we explore the connections between two classes of polyominoes, namely the permutominoes 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 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 XYX@^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 a unique infinite word Y"~ with period 4|X|"N|X|"E. Also, we show that XYX@^Y@^ are centrosymmetric, i.e. they are fixed by rotation of angle @p. The proof of this fact is based on the concept of pseudoperiods, a natural generalization of periods. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.dam.2012.08.034 | Discrete Applied Mathematics |
Keywords | Field | DocType |
polyomino tile,beauquier-nivat characterization,boundary word,permutomino tile,convex permutominoes,pseudo-square polyominoes,unique infinite word y,particular convex permutominoes,path x,fixed x,algebraic characterization,palindromes,polyominoes | Discrete mathematics,Combinatorics,Algebraic number,Permutation,Enumeration,Polyomino,Palindrome,Regular polygon,Prefix,If and only if,Mathematics | Journal |
Volume | Issue | ISSN |
161 | 15 | 0166-218X |
Citations | PageRank | References |
1 | 0.37 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Blondin Massé | 1 | 30 | 4.09 |
| A. Frosini | 2 | 19 | 3.03 |
| Simone Rinaldi | 3 | 174 | 24.93 |
| L. Vuillon | 4 | 17 | 2.71 |