Every Tiling of the First Quadrant by Ribbon *L n*-Ominoes Follows the Rectangular Pattern

ABSTRACT

Let and let be the set of four ribbon*L*-shaped *n*-ominoes. We
study tiling problems for regions in a square lattice by . Our main result
shows a remarkable property of this set of tiles: any tiling of the first
quadrant by , *n* even, reduces to a tiling by and rectangles, each rectangle being covered by
two ribbon *L*-shaped *n*-ominoes. An application of our result
is the characterization of all rectangles that can be tiled by , *n* even: a rectangle can be tiled by , *n* even, if and only if both of its sides
are even and at least one side is divisible by *n*. Another application is the existence of the local move property
for an infinite family of sets of tiles: , *n* even, has the local move property for
the class of rectangular regions with respect to the local moves that
interchange a tiling of an square by *n*/2
vertical rectangles, with a tiling by *n*/2
horizontal rectangles, each vertical/horizontal rectangle being covered by two
ribbon *L*-shaped *n*-ominoes. We show that none of these results are valid for any
odd *n*. The rectangular pattern of a
tiling of the first quadrant persists if we add an extra tile to , *n* even. A rectangle can be tiled by the
larger set of tiles if and only if it has both sides even. We also show that
our main result implies that a skewed *L*-shaped *n*-omino, *n* even, is not a replicating tile of order *k*^{2} for any odd *k*.

Let and let be the set of four ribbon

KEYWORDS

Polyomino, Replicating Tile,*L*-Shaped Polyomino,
Skewed *L*-Shaped Polyomino,
Local Move Property,
Tiling Rectangles,
Rectangular Pattern,
Tiling First Quadrant

Polyomino, Replicating Tile,

Cite this paper

Nitica, V. (2015) Every Tiling of the First Quadrant by Ribbon*L n*-Ominoes Follows the Rectangular Pattern. *Open Journal of Discrete Mathematics*, **5**, 11-25. doi: 10.4236/ojdm.2015.52002.

Nitica, V. (2015) Every Tiling of the First Quadrant by Ribbon

References

[1] Golomb, S.W. (1954) Checker Boards and Polyominoes. The American Mathematical Monthly, 61, 675-682.

http://dx.doi.org/10.2307/2307321

[2] Golomb, S.W. (1994) Polyominoes, Puzzles, Patterns, Problems, and Packings. 2nd Edition, Princeton University Press, Princeton.

[3] Pak, I. (2000) Ribbon Tile Invariants. Transactions of the American Mathematical Society, 352, 5525-5561.

http://dx.doi.org/10.1090/S0002-9947-00-02666-0

[4] Chao, M., Levenstein, D., Nitica, V. and Sharp, R. (2013) A Coloring Invariant for Ribbon L-Tetrominoes. Discrete Mathematics, 313, 611-621.

http://dx.doi.org/10.1016/j.disc.2012.12.007

[5] Golomb, S.W. (1964) Replicating Figures in the Plane. The Mathematical Gazette, 48, 403-412.

http://dx.doi.org/10.2307/3611700

[6] Gardner, M. (1963) On “Rep-Tiles”, Polygons That Can Make Larger and Smaller Copies of Themselves. Scientific American, 208, 154-157.

http://dx.doi.org/10.1038/scientificamerican0563-154

[7] Nitica, V. (2003) Rep-Tiles Revisited, in the Volume MASS Selecta: Teaching and Learning Advanced Undergraduate Mathematics, American Mathematical Society, Providence.

[8] de Brujin, N.G. (1969) Filling Boxes with Bricks. The American Mathematical Monthly, 76, 37-40.

http://dx.doi.org/10.2307/2316785

[9] Nitica, V. (2004-2005) Tiling a Deficient Rectangle by L-Tetrominoes. Journal of Recreational Mathematics, 33, 259-271.

[10] Reid, M. (2014) Many L-Shaped Polyominoes Have Odd Rectangular Packings. Annals of Combinatorics, 18, 341-357.

http://dx.doi.org/10.1007/s00026-014-0226-9

[11] Thurston, W. (1990) Conway’s Tiling Groups. The American Mathematical Monthly, 97, 757-773.

http://dx.doi.org/10.2307/2324578

[12] Conway, J.H. and Lagarias, J.C. (1990) Tilings with Polyominoes and Combinatorial Group Theory. Journal Combinatorial Theory, Series A, 53, 183-208.

http://dx.doi.org/10.1016/0097-3165(90)90057-4

[13] Kenyon, C. and Kenyon, R. (1992) Tiling a Polygon with Rectangles. Proceedings of 33rd Annual Symposium on Foundations of Computer Science (FOCS), Pittsburgh, 24-27 October 1992, 610-619.

[14] Calderon, A., Fairchild, S., Nitica, V. and Simon, S. (2015) Tilings of Quadrants by L-Ominoes and Notched Rectangles. Topics in Recreational Mathematics, 5.

[1] Golomb, S.W. (1954) Checker Boards and Polyominoes. The American Mathematical Monthly, 61, 675-682.

http://dx.doi.org/10.2307/2307321

[2] Golomb, S.W. (1994) Polyominoes, Puzzles, Patterns, Problems, and Packings. 2nd Edition, Princeton University Press, Princeton.

[3] Pak, I. (2000) Ribbon Tile Invariants. Transactions of the American Mathematical Society, 352, 5525-5561.

http://dx.doi.org/10.1090/S0002-9947-00-02666-0

[4] Chao, M., Levenstein, D., Nitica, V. and Sharp, R. (2013) A Coloring Invariant for Ribbon L-Tetrominoes. Discrete Mathematics, 313, 611-621.

http://dx.doi.org/10.1016/j.disc.2012.12.007

[5] Golomb, S.W. (1964) Replicating Figures in the Plane. The Mathematical Gazette, 48, 403-412.

http://dx.doi.org/10.2307/3611700

[6] Gardner, M. (1963) On “Rep-Tiles”, Polygons That Can Make Larger and Smaller Copies of Themselves. Scientific American, 208, 154-157.

http://dx.doi.org/10.1038/scientificamerican0563-154

[7] Nitica, V. (2003) Rep-Tiles Revisited, in the Volume MASS Selecta: Teaching and Learning Advanced Undergraduate Mathematics, American Mathematical Society, Providence.

[8] de Brujin, N.G. (1969) Filling Boxes with Bricks. The American Mathematical Monthly, 76, 37-40.

http://dx.doi.org/10.2307/2316785

[9] Nitica, V. (2004-2005) Tiling a Deficient Rectangle by L-Tetrominoes. Journal of Recreational Mathematics, 33, 259-271.

[10] Reid, M. (2014) Many L-Shaped Polyominoes Have Odd Rectangular Packings. Annals of Combinatorics, 18, 341-357.

http://dx.doi.org/10.1007/s00026-014-0226-9

[11] Thurston, W. (1990) Conway’s Tiling Groups. The American Mathematical Monthly, 97, 757-773.

http://dx.doi.org/10.2307/2324578

[12] Conway, J.H. and Lagarias, J.C. (1990) Tilings with Polyominoes and Combinatorial Group Theory. Journal Combinatorial Theory, Series A, 53, 183-208.

http://dx.doi.org/10.1016/0097-3165(90)90057-4

[13] Kenyon, C. and Kenyon, R. (1992) Tiling a Polygon with Rectangles. Proceedings of 33rd Annual Symposium on Foundations of Computer Science (FOCS), Pittsburgh, 24-27 October 1992, 610-619.

[14] Calderon, A., Fairchild, S., Nitica, V. and Simon, S. (2015) Tilings of Quadrants by L-Ominoes and Notched Rectangles. Topics in Recreational Mathematics, 5.