Polyomino Tiling Recurrences
One of the struggles at JRMF has been finding arithmetic activities that are as popular as our logical and geometric activities in a festival setting. Kids see an activity table with numbers and tend to want to flock to the other tables. I don't think the activity I'll present today is a great festival activity as-is, but I like it because it deals with recurrence relations disguised as a geometric problem. I've run it over the years and my colleague Steve Heller has a well-loved version he has dressed as brick-laying on the Yellow Brick Road. Math circle kids love it, but our goal with math festivals is to give kids that don't normally end up at math circles a bite-sized version that invites -- but doesn't demand -- a ton of careful handwritten work. The reasons I'm hesitant to think of this activity as a great festival activity are (1) there's a some book-keeping required to arrive at the arithmetic content, which younger students don't often think or want to do on their own and (2) the manipulatives then to be required in greater numbers if one wants to keep one's work on display in the absence of book-keeping, but maybe there are some tweaks that could make it work about as well at math festivals as it works at math circles.
Setup
For the beginning portion of this, face-down dominoes and appropriately sized grids are perfect manipulatives. As you move into the portions that require trominoes and larger shapes, grids and markers work. I have also printed out tromino sets and laminated them in the past if I want manipulatives that will outlast a single session. Here are some griddings to accommodate polyominoes with 1" x 1" unit squares. If doing the activity virtually, Mathigon's Polypad is a great tool for exploring this problem -- and what I've used to make my graphics here!
The first problem we will take up is as follows:
Given a \(2 \times n\) board, how many ways are there to tile it with dominoes?
This is usually best introduced by working through an example and then focusing on specific cases.
Example
How many ways are there to tile a \( 2 \times 4 \) board with dominoes?
If all dominoes are identical (i.e., all blank \( 2 \times 1 \) rectangles), then there are five distinct tilings. Here they are:
Have the students explore other \( 2 \times n \) rectangles. \( 2 \times 5 \) is a nice next challenge, if you want to pose something concrete. Making a table and filling it out for the values they've found should hopefully be enough to prompt them to explore \( 2 \times n \) boards for \( n = 1, 2, 3, 4, 5, 6 \) or more.
Initial Questions
- Is there a pattern to the number of ways to tile a \( 2 \times n \) board with dominoes? Why should these numbers come up?
- Can you use your findings to predict how many dominoes it would take to tile a \( 2 \times 20 \) board? A \( 2 \times 30 \) board?
- If the pattern is a familiar one, can you explain why it's the pattern you're seeing here? (Is it a coincidence or is there a good reason for it?)
- How do things change if we look at different board sizes?
- How do things change if we use shapes other than dominoes?
Explorations
If \( f(n) \) is the number of ways to tile a \( 2 \times n \) board with dominoes, then the pattern is as follows:
| \( n \) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| \( f(n) \) | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
While some might recognize this as the Fibonacci sequence, others might notice that each number is the sum of the two before it: \[ f(n) = f(n-1) + f(n-2) \] It's a little harder to see why this pattern holds, but the key is to notice that there are two types of tilings: tilings that start with a vertical domino and tilings that start with two horizontal dominoes. Here is a visual proof for \( f(6) = f(5) + f(4) \) that gives the gist of the general argument:
Exploring these configurations and explaining why the Fibonacci numbers tie in is often the bulk of a session on its own. After this, there are a couple natural directions to head:
-
How many ways are there to tile a \( 3 \times n \) board with \( 3 \times 1 \) trominoes?
While the manipulatives are a little harder to organize for this generalization, the recurrence relation is almost as nice as in the domino case:
\[ f(n) = f(n-1) + f(n-3) \]After the domino and tromino cases, students can pretty quickly find the recurrence relations for tiling a \( k \times n \) board with \( k \times 1 \) tiles.
How many ways are there to tile a \( 3 \times n \) board with \( 2 \times 1 \) dominoes?
While you can simply reuse your dominoes for this problem, it is far thornier. A basic observation is that a tiling is impossible when \( n \) is odd, so we can actually consider only boards of shape \( 3 \times 2m \). The recurrence relation is then
\[ f(m) = 4f(m-1) - f(m-2) \]and ferreting it out is much less intuitive.
This problem gets thornier still for larger boards. Are there nice formulas to be had for the number of ways to tile a \( 4 \times n \) board with dominoes? Square \( 2m \times 2m \) boards? \( 2m \times n \) boards, in general?
Wrap-Up Questions
- What patterns have you found in the numbers of tilings of these boards?
- What are good strategies for finding recurrence relations for tilings?
- What other families of tilings might give rise to nice number sequences?
Extensions
- The problem of tiling a \( 2 \times n \) board with dominoes is equivalent to tiling a \( 1 \times n \) strip with a combination of \( 1 \times 1 \) and \( 2 \times 1 \) tiles. (To see why, note that a tile \( 2 \times n \) rectangle is always symmetric about its long axis and looking only at one half gives the tiling of the \( 1 \times n \) strip with \( 1 \times 1 \) and \( 2 \times 1 \) tiles.) More arithmetically, the number of ways to do this is the number of ways to write \( n \) as an ordered sum of 1's and 2's. How many ways are there to write \( n \) as an ordered sum of 1's and 3's? 2's and 3's? 1's, 2's, and 3's? (These are questions about restricted compositions.)
What if we allow for polyominoes other than \( k \times 1 \)? A nice family to explore are the L-shapes trominoes. Any rectangle these tile must have a multiple of 3 squares, so how many ways are there to tile a \( 3m \times n \) board with them? The families of \( 3m \times 2 \) and \( 3 \times n \) boards are gentle introductions. Here are the \(3 \times 4 \) boards:
What about \( 3m \times 4 \) boards? \( 3m \times 5 \) boards?
If we wanted to move away from squares and rectangles, we could ask the number of ways to make a regular hexagon with side length \( n \) using only \( 60^\circ-120^\circ \) rhombi with side length 1. (These rhombi are sometimes called lozenges.) Wide (typically blue) rhombi from a standard set of pattern blocks are great manipulatives for this. Here are all tilings of a hexagon with side length 2 with suggestively colored lozenges:
(The fact that each color is used the same number of times and the interesting 3D interpretations of these patterns turn out to not be coincidental!)
There are many other tiling arrangements of families of figures that can be investigated using pattern blocks.
Comments
Post a Comment