ABSTRACT

The problem of tiling rectangles by polyominoes generated large interest. A related one is the problem of tiling parallelograms by twisted polyominoes. Both problems are related with tilings of (skewed) quadrants by polyominoes. Indeed, if all tilings of a (skewed) quadrant by a tile set can be reduced to a tiling by congruent rectangles (parallelograms), this provides information about tilings of rectangles (parallelograms). We consider a class of tile sets in a square lattice appearing from arbitrary dissections of rectangles in two L-shaped polyominoes and from symmetries of these tiles about the first bisector. Only translations of the tiles are allowed in a tiling. If the sides of the dissected rectangle are coprime, we show the existence of tilings of all (skewed) quadrants that do not follow the rectangular (parallelogram) pattern. If one of the sides of the dissected rectangle is 2 and the other is odd, we also show tilings of rectangles by the tile set that do not follow the rectangular pattern. If one of the sides of the dissected rectangle is 2 and the other side is even, we show a new infinite family of tile sets that follows the rectangular pattern when tiling one of the quadrants. For this type of dissection, we also show a new infinite family that does not follow the rectangular pattern when tiling rectangles. Finally, we investigate more general dissections of rectangles, with. Here we show infinite families of tile sets that follow the rectangular pattern for a quadrant and infinite families that do not follow the rectangular pattern for any quadrant. We also show, for infinite families of tile sets of this type, tilings of rectangles that do not follow the rectangular pattern.

Keywords:

Polyomino, L-Shaped Polyomino, Skewed L-Shaped Polyomino, Tiling Rectangles, Tiling Quadrants, Tiling Parallelograms, Rectangular Pattern for Tiling Quadrants/Rectangles

1. Introduction

In this article, we study tiling problems for regions in a square lattice by polyominoes. Polyominoes were introduced by Golomb in [1] and the standard reference about this subject is the book Polyominoes [2] . The polyominoes are made out of unit squares, or cells. In a rectangle, a is the height and b is the base.

Understanding tilings of rectangles by particular polyominoes, even of simple shape, is a difficult combinatorial problem with a long history. See for example the paper of Golomb [3] . Among the pioneering contributions, we mention those of Klarner [4] . On page 113 of [4] , Klarner emphasizes the difficulty of classifying rectangles tileable by L-shaped n-ominoes for which two copies can be assembled in a rectangle: It seems impossibly difficult to characterize the rectangles which can be packed with an n-omino of order 2. A theorem of this kind restricted to the L-shaped n-ominoes of order 2 would probably still be too difficult to formulate. A partial result in this direction appears in Reid [5] , where it is shown that any L-shaped polyomino of order 2 for which the basic rectangle has coprime sides has odd order. We recall that the order of a polyomino is the minimal number of tiles that can be assembled into a rectangle.

A similar problem can be investigated for parallelograms in a skewed lattice by using instead of polyominoes skewed tiles that have all sides parallel to the sides of the parallelogram. The problems are independent and probably of the same level of difficulty. A first observation is that the problem of tiling a parallelogram is equivalent to that of tiling a rectangle by polyominoes (the straightened tiles), allowing only a reduced set of orientations for those polyominoes. Some progress was done in the case of L-shaped n-ominoes of order two in several recent papers of the author and collaborators [6] [7] [8] [9] [10] . The results are consequences of more general tiling results for quadrants, showing that for many tiling sets there exists at least a quadrant for which all tilings can be reduced to tilings by congruent rectangles built out of two tiles from the tiling set. If this is the case, we say that the tile set and the corresponding tilings follow the rectangular pattern. Some caution is needed, as some pairs of tiles of order 2 can be assembled in two different rectangles. To eliminate the ambiguity, the class of tile sets that follow the rectangular pattern is restricted to those that have a single basic rectangle. Another motivation for the study of tile sets with a reduced set of orientations comes from the study of skewed replicating tiles [11] [12] .

The result in [5] shows that, if the full set of orientations of an order 2 L-shaped tile is allowed, there exist plenty of tile sets that do not follow the rectangular pattern. We show, in Theorem 1, a related result when only a reduced set of orientations is allowed. The tile sets appear from arbitrary dissections of rectangles in two L-shaped polyominoes and from symmetries of these tiles about the first bisector. Only translations of the tiles are allowed in a tiling. In Theorem 2, we show the existence of tilings for certain half-infinite strips. Theorems 1 and 2 leave open the question of tiling rectangles without following the rectangular pattern by our tile sets. We answer this question if the dissected rectangle has base 2 and odd height, improving in Theorem 3 some results obtained in [7] .

If the dissected rectangle has base 2 and even height, we show in Theorem 4 new examples of tile sets that follow the rectangular pattern for tilings of a quadrant, complementing the results in [7] . They are given by an infinite subfamily of tile sets, introduced in [7] , namely for even. The first tile set in the series is consisting of a tromino and two pentominoes. See Figure 1. An immediate consequence of this result is that a rectangle can be tiled by if and only if it has one side even and the other divisible by 4. If a square is added to even, the new tile set is called. Similar to what happens in [6] and [7] , the new tile set preserves the rectangular pattern. A rectangle can be tiled by if and only if it has both sides even. Neither of these results follows from coloring invariants. In Theorem 6 we show that the tile sets do not follow the rectangular pattern for rectangles. In particular, a rectangle has an irregular tiling by. These results partially answer some questions left open in [6] after the statement of Theorem 1. We show in Theorem 7 that the 2 × horizontal inflation of the family of tile sets does not follow the rectangular pattern for rectangles. We show in Theorem 8, among other results, new tile sets generated by a dissection of a rectangle that follows the rectangular pattern. These results give a better under- standing of the problem studied in [10] . They show that the dissection of a rectangle with can generate tile sets that follow the rectangular pattern and tile sets that do not. In the examples from [7] and [10] , one has or.

The paper ends with several open questions and a conclusive summary.

2. Main Results

Our argument can be applied to a larger class of tile sets then those generated by L-shaped n-ominoes of order 2. We start with a rectangle in the square lattice and dissect it in two L-shaped polyominoes, not necessarily congruent, by a vertical cut. Due to symmetry, the case of a horizontal cut is also covered by our argument. For a given rectangle with integer sides, there are two possible shapes for the vertical cuts. They are shown in Figure 2. The cuts are parameterized by the positive integers. Note that one has. Each tile set we consider consists of four tiles. Two of them are generated by the cut and two appears by taking a reflection in the first bisector of the tiles given by the cut. We call the

tile sets appearing from a dissection as in Figure 2(a) of type 1, and respectively as in Figure 2(b), of type 2. A tile set of type 1 is shown in Figure 3. To establish some terminology, we refer to tile sets of type 1 or 2 as 2-dissection tile sets, or simply by dissection tile sets. We call the dissected rectangle the basic rectangle of the dissected tile set. Theorem 1 is a corollary of Theorem 2.

Theorem 1. If are coprime, all dissection tile sets have tilings of all quadrants that do not follow the rectangular pattern. We can arrange for a single tile to be out of the rectangular pattern.

Theorem 2. If are coprime, all dissection tile sets have tilings of half-infinite strips that do not follow the rectangular pattern. We can arrange for a single tile to be out of the rectangular pattern.

Proof. Due to symmetries, it is enough to show the proof for a tile set of type 1. The tile set is symmetric about the first bisector, so it is enough to show the proof only for a half-strip opening to the right and for one opening to the left. The tilings are shown in Figure 4. As m,n are coprime, there exists positive integers such that. For the half-strip opening to the right, region I is a rectangle of base and height, region II is a rectangle of base qyn and height sxm, region IV is a half-infinite strip of width n, region V is a half-infinite strip of width twm, and region III is a half-infinite strip of width yns. For the half-strip

opening to the left, region I is a rectangle of height and base . Then region II is a rectangle of base qwm and height tzn, region IV is a half-infinite strip of width n, region V is a half-infinite strip of width syn, and region III is a half-infinite strip of width twm.

Problem 1. Decide if all dissection tile sets have a tiling of a torus (or/and of a cylinder) that does not follow the rectangular pattern and in which not all tiles are in an irregular position.

The problem can be solved for torus if we allow all tiles to be in an irregular position. Indeed, any notched rectangle in the square lattice has a doubly periodic tiling of the plane that does not follow the rectangular pattern. An instance is shown in Figure 5. Other natural problem is:

Problem 2. Determine which of the dissection tile sets tile rectangles without following the rectangular pattern.

The case when the base of the dissected rectangle has length 2 and is solved in Theorem 3. This complements Theorem 1 in [7] . The general problem of tiling some rectangle by a tile set is undecidable [13] .

Figure 6 shows a family of dissected tile sets studied in [7] . It is indexed by positive integers, and denoted. The rectangles I are, the rectangles II are and the rectangles III are. We denote the tiles by. The pairs and consist of congruent tiles. The elements in each pair are symmetric about the first diagonal. A tiling by follows the rectangular pattern if it reduces to a tiling by rectangles, each tiled by.

Theorem 3. Assume m,n,p are positive integers with.

1) If m odd, n even, p odd, any tiling of the first quadrant by follows the rectangular pattern. In this case there exist irregular tilings of tori.

In Cases 2. through 6. there exist tilings of rectangles by that do not follow the rectangular pattern.

2) m even, n even, p even;

3) m even, n odd, p even;

4) m odd, n even, p even;

5) m even, n even, p odd;

6) m odd, n odd, p odd.

In Cases 7., 8. there exist irregular tilings of tori by.

7) m odd, n odd, p even;

8) m even, n odd, p odd.

In particular, if is odd, has tilings of rectangles that do not follow the rectangular pattern.

Proof. First part of Case 1 and Case 6 are proved in Theorem 8, [7] . For Cases 2 - 5 Theorem 8, [7] shows only tilings of the first quadrant that do not follow the rectangular pattern. For Cases 7 - 8 Theorem 8, [7] shows tilings of the first quadrant if (the pictures a), b) in Figure 18 in [7] should be interchanged and assume) and shows two cases of irregular tilings of rectangles, for and.

We prove the second part of Case 1 and Cases 2 - 6 below (correcting some misprints from [7] in Case 6). During the proof we use that multiples of rectangles are tiled by.

Case 2. The tiling is shown in Figure 7. Region I is a rectangle. Region II is a rectangle. Region III is a rectangle.

Case 3. Figure 8 shows a tiling of a rectangle. We place two copies of and two copies of inside the rectangle as in Figure 8. Rectangles I and VIII are, with even, rectangles II and VI are, with even, rectangles III and VII are, and rectangles IV and V are.

Case 4. We tile as in Figure 9. Region I is a rectangle. Region II is a rectangle. Region III is a rectangle. Region VI is a rectangle.

Case 5. Use Figure 10. Region I is a rectangle. Region II is a rectangle. Region III is a rectangle. Region IV is a rectangle.

Case 6. The proof is verbatim identical with the proof in Case 3. One uses again

Figure 8.

Case 7. The tiling is shown in Figure 11. Region I is a rectangle

. Region II is a rectangle. Region III is a rectangle. Regions IV and V are rectangles . Region VI is a rectangle. Region VII is a rectangle. Region VIII is a rectangle .

Case 8. The proof is identical verbatim with the proof in Case 7. One uses again Figure 11.

Case 1, second part. The tiling is shown in Figure 12. Region I is a rectangle. Region II is a rectangle. Region III is a rectangle. Regions IV and V are rectangles.

Region VI is a rectangle. Region VII is a rectangle . Region VIII is a rectangle.

Theorem 3 shows that an irregular tiling with few tiles in an irregular position of a torus by is always possible. The analog problem for cylinder is open in Cases 7, 8. Theorem 3 also shows an irregular tiling of a rectangle by if the dissected rectangle has one side 2 and the side of length odd. The case when is even is more complicated, with Cases 7, 8 left open in general. We show in what follows that in these cases both tile sets that follow the rectangular pattern for a quadrant and tile sets that have irregular tilings of a rectangle may appear, for infinite families of tile sets.

Theorem 4. The tile sets, p even, follow the rectangular pattern for the first quadrant and there are tilings of the other three quadrants that do not follow the rectangular pattern.

Proof. The tile set consists of three tiles: a tromino and two other tiles which we call horizontal/vertical.

We show the proof for the first quadrant. A square with all vertices of even coordinates is called a 2-square. We show that every 2-square is covered by a rectangle with even vertices that is covered by two tiles from. If this is the case, we say that the 2-square follows the rectangular pattern. We proceed by induction on a diagonal staircase shown in Figure 13. We assume that every 2-square below the staircase satisfies the hypothesis and show that every 2-square above the staircase also satisfies it. It is easily checked that the corner of the first quadrant can be tiled only following the rectangular pattern. We show now the induction step. Choose the rightmost square, that does not follow the rectangular pattern. The lower left cell in that square can be covered only by the tromino. The cell in not covered by the tromino can be covered by either one of the tiles in an irregular way. If covered by the tromino or the horizontal tile, this leads to a cell that cannot be covered further. See Figure 14.

If covered by a vertical tile, we look at the 2-square. If already covered regularly, this leads to a cell above that cannot be covered. Otherwise, the lower left cell in can be covered only by the tromino. A repeat of the argument leads either to a contradiction as before, or to the appearance of a staircase that propagated towards to y-axis, finally leading to a cell adjacent to the y-axis that cannot be covered. See Figure 15.

For the negative results, due to symmetry, it is enough to show examples of tilings only for the second and third quadrant. See Figure 16. In the second quadrant, regions I, II, III, IV, V, VII, VIII are half infinite strips of even width, region VI is a copy of the second quadrant and region IX is a rectangle. In the third quadrant, regions I, II, III, V, VI, VII are half infinite strips of even width, region IV is a copy of the third quadrant and region VIII is a rectangle.

If a square is added to even, the new tiling set is called. As it was the case in [6] and [7] , the new tiling set preserves the rectangular pattern. The proof of next theorem is similar to that of Theorem 4.

Theorem 5. The tile sets, p even, follows the rectangular pattern for the first quadrant and there are tilings of the other three quadrants that do not follow the rectangular pattern.

Theorems 4 and 5 imply local move property for the tiling sets even, and rectangular regions, see [6] [7] . It is natural to ask if same property holds for more general regions.The family corresponds to a single type of (horizontal) cut. The results for the other type can be obtained via a symmetry about the y-axis.

The positive results in Theorem 4 and Theorem 5 cannot be found using coloring invariants. We refer to [9] for a discussion of this topic and relevant examples. We leave the formal proof as an exercise for the reader.

Theorem 6. The tile sets do not follow the rectangular pattern for rectangles. In particular, a rectangle has an irregular tiling by.

Proof. The case is shown in [7] . The pattern of the general construction follows easily from Figures 17-19, showing the cases. All regions labeled by roman numerals follow the rectangular pattern.

The rectangles in Theorem 6 have the feature that admit a unique irregular tiling. They also are of minimal height with the property that allow an irregular tiling. We

observe that the number of rectangles in irregular position in the examples increases with n. It would be interesting to find irregular tilings of rectangles by for which the number of tiles in an irregular position is bounded with respect to n.

Next theorem shows that a 2 × horizontal inflation of produces a family of tile sets that have irregular tilings. A 2 × horizontal inflation of is shown in Figure 20. The theorem clarifies questions open in [10] by showing an infinite family of tile sets appearing from dissections of rectangles with that do not follow the rectangular pattern.

Theorem 7. A 2 × horizontal inflation of the family of tile sets produces a family of dissection tile sets that allows for irregular tilings.

Proof. The tilings are shown in Figure 21, if n is even, and in Figure 22, if n is odd. The gray regions are covered by tiles in irregular positions. The number of such tiles is always 8, independent of n. All regions marked by Roman numerals are rectangles that can be tiles by or rectangles. In Figure 21, I is , II is, III is, IV is, V is , VI is, VII is, VIII is , IX is and X is. In Figure 22, I is , II is, III is, IV is, V is, VI is, VII is, VIII is, IX is, X is.

We consider now four possible dissections of a rectangle, , into an L-shaped polyomino of width 1 that extends along the height of the dissected rectangle

and a remaining notched rectangle. The missing part from the notched rectangle is always a cell, as shown in Figure 23. We denote the dissections. They define dissection tile sets denoted. The L-shaped polyominoes are denoted and their reflections, while the notched rectangles are denoted and their reflections. A tile set is shown in Figure 23. If, we call foundational square a square. If an extra foundational square, denoted S, is added to the tile set, we denote the tile set. A tile set is shown in Figure 24. A tiling by, , of a region in the plane is said to follow the rectangular pattern if it reduces to a tiling by and rectangles, each tiled in turn by two pieces from the tile set. A tiling by, , of a region in the plane is said to follow the rectangular pattern if it reduces to a tiling by squares and by and rectangles. The tile sets are studied in detail in [10] . We show that for each of these tile sets, with the possible exception of, for which we could not decide, there exists at least a quadrant for which any tiling has to follow the rectangular pattern. In particular, any tiling of a rectangle by the tile sets or follows the rectangular pattern. It is also shown in [10] that if then the tile sets do not follow the rectangular pattern, a particular case of Theorem 1 in this paper. The case when is left completely open, including the particular case.

The next theorem gives some partial results for tile sets generated by this type of dissections in the simplest case when. While these results are not final, they illustrate some differences between the tile sets considered here and those corresponding to dissections discussed in Theorem 1 and in [10] . Heuristically, the existence of a smaller foundational square, as compared to the size of the other tiles in the tile set, allows for more freedom in the tiling, therefore to the existence of more tilings that do not follow the rectangular pattern. Nevertheless, as we see from the next theorem, the rigid behaviour is still possible, even if we include the foundational square

in the tile set.

Theorem 8. Assume and.

1) The tile set has tilings of rectangles that do not folow the rectangular pattern, therefore does not follow the rectangular pattern for any quadrant.

2) The tile set has tilings of rectangles that do not folow the rectangular pattern, therefore does not follow the rectangular pattern for any quadrant.

3) The tile set has tilings of first, second and fourth quadrants that do not follow the rectangular pattern.

4) The tile set has tilings of first, second and fourth quadrants that do not follow the rectangular pattern.

5) Assume in addition that. Then any tiling of the third quadrant by follows the rectangular pattern.

6) Assume in addition that. Then any tiling of the third quadrant by follows the rectangular pattern.

Proof. Due to symmetries, it is enough to prove 1), 3) and 5). The foundational square is a square.

1)The tiling of a rectangle by is shown in Figure 25. Regions I through V can be tiles by squares. Region I is a rectangle, region II is a rectangle, region III is a rectangle, region IV is a rectangle, and region V is a rectangle.

3) Tilings of first and fourth quadrant by are shown in Figure 26. All regions that appear not covered by tiles from are either copies of quadrants of half infinite strips of even width that can be covered by squares. A tiling for the second quadrant follows by symmetry.

5) As before, a square with with all vertices of even coordinates is called a 2-square. We show that every 2-square is covered by a rectangle with even vertices that is tiled by tiles from. If this is the case, we say that the 2-square follows the rectangular pattern. We proceed by induction on a diagonal staircase shown in Figure 27. We assume that every 2-square below the staircase satisfies the hypothesis and show that every 2-square above the staircase also satisfies it. It is easily checked that the corner of the first quadrant can be tiled only following the rectangular pattern. We show now the induction step.

Let X be the first 2-square that does not follow the rectangular pattern. Let * be the upper right cell in X. See left picture in Figure 28. If covers cell *, then the cell below cell * cannot be tiled. If covers cell *, then the cell to the left of * cannot be covered. If covers cell *, then the notch of can be tiled only by, which is contradictory with our assumption about X. It follows that * can be covered only by. We look now at the right picture in Figure 28 and try to cover cell &. If covers cell &, then the square X is regularly tiled, in contradiction to our assumption. There is not enough room for to cover cell &. If or cover cell &, then cell # from Figure 28(b) cannot be covered. We conclude that the tiling of the square X has to follow the rectangular pattern, which gives a contradiction and ends the proof.

3. Open Problems

We mention here additonal problems left open by our study. Similar to what we did for tile sets of type one may define a foundational square for a dissection tile set. We use the notion from Figure 1. To make the notion not trivial and independent of the cases studied before, we need to assume that and that. We use the notation form Figure 2. We call enriched dissection tile set a dissection tile set with a foundational square added to the tile set. If d divides

or then the enhanced tile set tiles rectangles.Pictures of the tilings are in Figure 29. The gray regions in the figure are tiled by foundational squares.A large family of enhanced dissection tile sets that tile cylinders appears when d divides and. The tilings are shown in Figure 30. The gray regions are tiled by foundational squares. The left figure shows the tiling if and the right figure shows the tiling if.

Problem 3. Decide if all enhanced dissection tile sets have a tiling of a torus (or/and of a cylinder) that does not follow the rectangular pattern and in which not all tiles are in an irregular position. Also decide which enhanced dissection tile sets have a tiling of a rectangle that does not follow the rectangular pattern.

Problem 4. Decide if a double infinite strip of odd width can be tiled by or by, p even.

Problem 5. Find a tile set that follows the rectangular pattern when tiling a rectangle, but does not follow the rectangular pattern for tilings of quadrants.

Problem 5 is a particular instance of more general problem for dissection tile sets.

Problem 6. Find a dissection tile set that follows the rectangular pattern for any tiling of a rectangle, but does not follow the rectangular pattern for tilings of quadrants.

The following problem aims to improve the result in Theorem 8.

Problem 7. Prove the results in Theorem 8, 1), 3) for, respectively.

It is clear that if the tile set follows the rectangular pattern for a region, the corresponding tile set does this as well. But we do not know any example where the converse is not valid.

Problem 8. Find a tile set for which there exists a quadrant with all tilings following the rectangular pattern, but has a tiling of the same quadrant that does not follow the rectangular pattern.

We recall [10] that the tile set, follows the rectangular pattern with respect to all quadrants.

Problem 9. Find a dissection tile set generated by the dissection of a rectangle, , which follows the rectangular pattern with respect to all four quadrants.

4. Conclusion

The goal of the paper is to study tiling problems in a square lattice by specific tile sets. The tile sets appear from dissections of rectangles in two L-shaped polyominoes and from symmetries of these tiles about the first bisector. Only translations of the tiles are allowed in a tiling. We investigate mostly tilings of the quadrants and of rectangles. Our results have applications to tilings of paralelograms in a skewed lattice and to the study of replicating figures in a skewed lattice. These problems were mostly overlooked in the literature, which concentrated on tiling rectangles using all symmetries of a single polyomino. A crucial observation made in [6] [7] and [10] is that many of tile sets of type studied here follow the rectangular pattern, that is, any tiling reduces to one by rectangles, each rectangle is tiled by two pieces from the tile set. As observed in [8] and [9] these results do not follow from coloring invariants. We show in the paper that if the sides of the dissected rectangle are coprime, then the tile set allows for tilings of all quadrants that do not follow the rectangular pattern. If the sides of the dissected rectangle satisfy, then both tile sets that follow the rectangular pattern and tile sets that do not follow the rectangular pattern are possible. These results complement those in [10] , where we study tile sets appearing from dissection of rectangles with k multiple of. We also complement the results in [7] , where we study tile sets appearing from dissection of rectangles. If one of the sides of the dissected rectangle is 2 and the other side is even, we show in the paper a new infinite family of tile sets that follows the rectangular pattern when tiling one of the quadrants. For this type of dissection, we also show a new infinite family that does not follow the rectangular pattern when tiling rectangles. Our results answer some questions left open in [7] and [10] . Several new open problems are listed in the Open Problems section.

Acknowledgements

V. Nitica was partially supported by Simons Foundation Grant 208729.

Cite this paper

Nitica, V. (2016) On Tilings of Quadrants and Rectangles and Rectangular Pattern. Open Journal of Discrete Mathematics, 6, 351-371. http://dx.doi.org/10.4236/ojdm.2016.64028

References