Tiling with Polyominoes
Square tiles can be readily fitted together to cover the rectangular floor of a bathroom. If the floor happens to have dimensions that are whole-number multiples of a tile’s width, you don’t even have to trim any tiles to complete the pattern.
If each tile consists not of a single square but of a certain number of squares joined together along their edges to form a unit of a certain shape, the problem of determining whether you can use such tiles to cover a rectangular floor flawlessly gets more complicated.
Indeed, mathematicians have proved that the general question of whether it’s possible to cover the plane (or even a smaller region, such as a rectangle) with identical copies of a given finite set of tiles (or even a single geometric figure) is, in principle, computationally undecidable. In other words, there’s no cookbook recipe or handbook procedure that you can routinely apply to indicate whether you can fit together copies of an arbitrary shape to form a rectangle.
Mathematicians, however, have solved a variety of special cases of the tiling problem in two dimensions, particularly those that involve shapes known as polyominoes—forms that cover adjoining squares on a checkerboard. The term polyomino was coined in 1953 by mathematician Solomon W. Golomb, now at the University of Southern California in Los Angeles.
There is only one type of monomino (the unit square by itself) and one domino (two squares stuck together along one edge). There are two distinct trominoes (three squares) and five different tetrominoes (four squares). As the number of connected squares increases, the number of different possible configurations grows rapidly.
Polyominoes are the basis of thousands of mathematical puzzles. Cristopher Moore of the Santa Fe Institute in New Mexico has focused on the problem of determining how many different tilings of rectangles of various widths are possible using a given type of polyomino. In a recent preprint (http://xxx.lanl.gov/abs/math.CO/9905012), he calculates the number of ways a rectangle 4 units wide and n units long can be tiled with right trominoes.
Suppose you have a 4 x n rectangle, where n is a multiple of 3. It turns out that you need to consider only three types of interfaces when fitting right trominoes together into a strip of the required width and length. For example, two trominoes fit together to form a 2 x 3 rectangle, and two such rectangles stacked one on top of the other produce a 4 x 3 rectangle. There are four ways to do the stacking. These configurations all result from what Moore describes as a "straight" interface for building rectangular strips.
Two other interfaces are also possible: deep jog and shallow jog.
Because the number of possible interfaces is limited to three, Moore could derive a formula that gives the number of different ways to tile rectangles of different sizes. There are four ways to produce a 4 x 3 rectangle (see above), 18 ways to produce a 4 x 6 rectangle, 88 ways to produce a 4 x 9 rectangle, and 468 ways to produce a 4 x 12 rectangle. By definition, there is only one way to build a 4 x 0 rectangle.
[Technical details: The number of ways of tiling a m x n rectangle with any finite collection of shapes, where m is fixed, can be found by calculating the nth power of a matrix whose rows and columns correspond to the various interface shapes a partial tiling may have, Moore says. For the three interfaces possible for right trominoes, he solves a system of linear equations to obtain the formula, or generating function, G(z) = (1 – 6z)/(1 – 10z + 22z2 + 4z3). The terms of the Taylor expansion of G give the number of ways to tile rectangles of size 4 x 0, 4 x 3, 4 x 6, and so on: 1, 4, 18, 88, 468, 2672, 16072, . . ..]
Moore also worked out formulas giving the number of different ways to tile rectangles of width 5 with right trominoes and rectangles of width 4 with L tetrominoes and T tetrominoes.
You can prove that T tetrominoes cannot tile any rectangles of width 5, 6, or 7. Indeed, a rectangle can be tiled with T tetrominoes only if its length and width are both multiples of 4.
Nonetheless, that still leaves a lot of different patterns you can try out when tiling your bathroom floor with polyominoes.
Comments are welcome. Please send messages to Ivars Peterson at email@example.com.
Ivars Peterson is the mathematics/computer writer and online editor at Science News (http://www.sciencenews.org). He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, Fatal Defect, and The Jungles of Randomness. He and his wife, Nancy Henderson, have just completed Math Trek: Adventures in the MathZone, a book for children of middle-school age to be published in the fall by Wiley.MATHEMUSEMENTS: Look for math-related articles by Ivars Peterson every month in the children's general-interest magazine Muse (http://www.musemag.com) from the publishers of Cricket and Smithsonian magazine.