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 p...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 dis-section, 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.展开更多
Let T<sub>n </sub>be the set of ribbon L-shaped n-ominoes for some n≥4 even, and let T<sup>+</sup><sub>n</sub> be T<sub>n</sub> with an extra 2 x 2 square. We investiga...Let T<sub>n </sub>be the set of ribbon L-shaped n-ominoes for some n≥4 even, and let T<sup>+</sup><sub>n</sub> be T<sub>n</sub> with an extra 2 x 2 square. We investigate signed tilings of rectangles by T<sub>n</sub> and T<sup>+</sup><sub>n</sub> . We show that a rectangle has a signed tiling by T<sub>n</sub> if and only if both sides of the rectangle are even and one of them is divisible by n, or if one of the sides is odd and the other side is divisible by . We also show that a rectangle has a signed tiling by T<sup>+</sup><sub>n, </sub> n≥6 even, if and only if both sides of the rectangle are even, or if one of the sides is odd and the other side is divisible by . Our proofs are based on the exhibition of explicit GrÖbner bases for the ideals generated by polynomials associated to the tiling sets. In particular, we show that some of the regular tiling results in 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, cannot be obtained from coloring invariants.展开更多
We consider tilings of deficient rectangles by the set T4 of ribbon L-tetro-minoes. A tiling exists if and only if the rectangle is a square of odd side. The missing cell has to be on the main NW-SE diagonal, in an od...We consider tilings of deficient rectangles by the set T4 of ribbon L-tetro-minoes. A tiling exists if and only if the rectangle is a square of odd side. The missing cell has to be on the main NW-SE diagonal, in an odd position if the square is (4m+1)×(4m+1) and in an even position if the square is (4m+3)×(4m+3). The majority of the tiles in a tiling follow the rectangular pattern, that is, are paired and each pair tiles a 2×4 rectangle. The tiles in an irregular position together with the missing cell form a NW-SE diagonal crack. The crack is located in a thin region symmetric about the diagonal, made out of a sequence of 3×3 squares that overlap over one of the corner cells. The crack divides the square in two parts of equal area. The number of tilings of a (4m+1)×(4m+1) deficient square by T4? is equal to the number of tilings by dominoes of a 2m×2m square. The number of tilings of a (4m+3)×(4m+3) deficient square by T4? is twice the number of tilings by dominoes of a (2m+1)×(2m+1)?deficient square, with the missing cell placed on the main diagonal. In both cases the counting is realized by an explicit function which is a bijection in the first case and a double cover in the second. If an extra 2×2 tile is added to T4 , we call the new tile set?T+<sub style="margin-left:-6px;">4. A tiling of a deficient rectangle by T+4 exists if and only if the rectangle is a square of odd side. The missing cell has to be on the main NW-SE diagonal, in an odd position if the square is (4m+1)×(4m+1) and in an even position if the square is (4m+3)×(4m+3). The majority of the tiles in a tiling follow the rectangular pattern, that is, are either paired tetrominoes and each pair tiles a 2×4 rectangle, or are 2×2 squares. The tiles in an irregular position together with the missing cell form a NW-SE diagonal crack. The crack is located in a thin region symmetric about the diagonal, made out of a sequence of 3×3 squares that overlap over one of the corner cells. The number of tilings of a (4m+1)×(4m+1) deficient squar展开更多
We show that the least number of cells (the gap number) one needs to take out from a rectangle with integer sides of length at least 2 in order to be tiled by ribbon right trominoes is less than or equal to 4. If the ...We show that the least number of cells (the gap number) one needs to take out from a rectangle with integer sides of length at least 2 in order to be tiled by ribbon right trominoes is less than or equal to 4. If the sides of the rectangle are of length at least 5, then the gap number is less than or equal to 3. We also show that for the family of rectangles that have nontrivial minimal number of gaps, with probability 1, the only obstructions to tiling appear from coloring invariants. This is in contrast to what happens for simply connected regions. For that class of regions Conway and Lagarias found a tiling invariant that does not follow from coloring.展开更多
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 quadran...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 k2 for any odd k.展开更多
In this paper,we present an algorithm to simulate a Brownian motion by coupling two numerical schemes:the Euler scheme with the random walk on the hyper-rectangles.This coupling algorithm has the advantage to be able ...In this paper,we present an algorithm to simulate a Brownian motion by coupling two numerical schemes:the Euler scheme with the random walk on the hyper-rectangles.This coupling algorithm has the advantage to be able to compute the exit time and the exit position of a Brownian motion from an irregular bounded domain(with corners at the boundary),and being of order one with respect to the time step of the Euler scheme.The efficiency of the algorithm is studied through some numerical examples by comparing the analytical solution with the Monte Carlo solution of some Poisson problems.The Monte Carlo solution of these PDEs requires simulating Brownian motions of different types(natural,reflected or drifted)over an irregular domain.展开更多
文摘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 dis-section, 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.
文摘Let T<sub>n </sub>be the set of ribbon L-shaped n-ominoes for some n≥4 even, and let T<sup>+</sup><sub>n</sub> be T<sub>n</sub> with an extra 2 x 2 square. We investigate signed tilings of rectangles by T<sub>n</sub> and T<sup>+</sup><sub>n</sub> . We show that a rectangle has a signed tiling by T<sub>n</sub> if and only if both sides of the rectangle are even and one of them is divisible by n, or if one of the sides is odd and the other side is divisible by . We also show that a rectangle has a signed tiling by T<sup>+</sup><sub>n, </sub> n≥6 even, if and only if both sides of the rectangle are even, or if one of the sides is odd and the other side is divisible by . Our proofs are based on the exhibition of explicit GrÖbner bases for the ideals generated by polynomials associated to the tiling sets. In particular, we show that some of the regular tiling results in 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, cannot be obtained from coloring invariants.
文摘We consider tilings of deficient rectangles by the set T4 of ribbon L-tetro-minoes. A tiling exists if and only if the rectangle is a square of odd side. The missing cell has to be on the main NW-SE diagonal, in an odd position if the square is (4m+1)×(4m+1) and in an even position if the square is (4m+3)×(4m+3). The majority of the tiles in a tiling follow the rectangular pattern, that is, are paired and each pair tiles a 2×4 rectangle. The tiles in an irregular position together with the missing cell form a NW-SE diagonal crack. The crack is located in a thin region symmetric about the diagonal, made out of a sequence of 3×3 squares that overlap over one of the corner cells. The crack divides the square in two parts of equal area. The number of tilings of a (4m+1)×(4m+1) deficient square by T4? is equal to the number of tilings by dominoes of a 2m×2m square. The number of tilings of a (4m+3)×(4m+3) deficient square by T4? is twice the number of tilings by dominoes of a (2m+1)×(2m+1)?deficient square, with the missing cell placed on the main diagonal. In both cases the counting is realized by an explicit function which is a bijection in the first case and a double cover in the second. If an extra 2×2 tile is added to T4 , we call the new tile set?T+<sub style="margin-left:-6px;">4. A tiling of a deficient rectangle by T+4 exists if and only if the rectangle is a square of odd side. The missing cell has to be on the main NW-SE diagonal, in an odd position if the square is (4m+1)×(4m+1) and in an even position if the square is (4m+3)×(4m+3). The majority of the tiles in a tiling follow the rectangular pattern, that is, are either paired tetrominoes and each pair tiles a 2×4 rectangle, or are 2×2 squares. The tiles in an irregular position together with the missing cell form a NW-SE diagonal crack. The crack is located in a thin region symmetric about the diagonal, made out of a sequence of 3×3 squares that overlap over one of the corner cells. The number of tilings of a (4m+1)×(4m+1) deficient squar
文摘We show that the least number of cells (the gap number) one needs to take out from a rectangle with integer sides of length at least 2 in order to be tiled by ribbon right trominoes is less than or equal to 4. If the sides of the rectangle are of length at least 5, then the gap number is less than or equal to 3. We also show that for the family of rectangles that have nontrivial minimal number of gaps, with probability 1, the only obstructions to tiling appear from coloring invariants. This is in contrast to what happens for simply connected regions. For that class of regions Conway and Lagarias found a tiling invariant that does not follow from coloring.
文摘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 k2 for any odd k.
文摘In this paper,we present an algorithm to simulate a Brownian motion by coupling two numerical schemes:the Euler scheme with the random walk on the hyper-rectangles.This coupling algorithm has the advantage to be able to compute the exit time and the exit position of a Brownian motion from an irregular bounded domain(with corners at the boundary),and being of order one with respect to the time step of the Euler scheme.The efficiency of the algorithm is studied through some numerical examples by comparing the analytical solution with the Monte Carlo solution of some Poisson problems.The Monte Carlo solution of these PDEs requires simulating Brownian motions of different types(natural,reflected or drifted)over an irregular domain.
