کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419137 681745 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the shape of permutomino tiles
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the shape of permutomino tiles
چکیده انگلیسی

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̂Ŷ, where X̂ denotes the path XX 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 XX, each word YY such that XYX̂Ŷ is pseudo-square is prefix of a unique infinite word Y∞Y∞ with period 4|X|N|X|E. Also, we show that XYX̂Ŷ 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issue 15, October 2013, Pages 2316–2327
نویسندگان
, , , ,