Cover a strip two squares wide and n long with dominoes, and count the ways. It starts 1, then 2 — so three columns give 4, surely? Three give 3. The counts are the Fibonacci numbers, and the reason is one look at the last column.
Look at the last column of the strip. Either a single domino stands upright and fills it, leaving a strip one shorter, or two dominoes lie flat across the last two columns, leaving a strip two shorter. Every tiling is exactly one of those, so the number of ways for length n is the ways for n−1 plus the ways for n−2 — the Fibonacci recurrence. The counts run 1, 2, 3, 5, 8, 13, and being wrong first is the lesson: 1, 2 looks like the start of doubling, and it is not.
Why this sheet works
The tempting answer is 2 to a power, as if each column were an independent choice. It is not, and the case-split shows exactly why: a flat domino spends two columns at once, so choosing what happens at the last column already decides part of the column before it. That single dependency is what turns doubling into the slower Fibonacci climb, and seeing it is worth more than the sequence.
Count the ways to tile a 2-by-n strip with dominoes, and show why it is not a power of two.
1A hallway floor is 2 tiles wide and 4 tiles long, and it is covered exactly by 2-by-1 tiles with none overlapping or sticking out.In how many different ways can it be covered?Why
2A patio is 2 slabs wide and 8 slabs long, and it is paved with 1-by-2 paving stones laid flat.In how many different ways can it be covered?Why
Domino tilingsStrips up to 8 long
Name: Date:
Count the ways to tile a 2-by-n strip with dominoes, and show why it is not a power of two.
3A board is 2 squares tall and 6 squares wide, and it is covered completely by 1-by-2 dominoes.In how many different ways can it be covered?Why
4A patio is 2 slabs wide and 3 slabs long, and it is paved with 1-by-2 paving stones laid flat.In how many different ways can it be covered?Why
Domino tilings · Strips up to 8 longAnswer key
1. Look at the LAST column of the 2-by-4 hall. Either one domino stands upright and fills it, leaving a strip 3 long, or two dominoes lie flat across the last two columns, leaving a strip 2 long. So the ways for length 4 are the ways for 3 plus the ways for 2. Counting up: there is 1 way to tile a strip 1 long and 2 ways for one 2 long, and then each length adds the two before it: 2 + 1 = 3, 3 + 2 = 5. So 5 ways. It is not 8 — the last column is not a free choice, because a flat domino uses two columns at once.2. Look at the LAST column of the 2-by-8 patio. Either one domino stands upright and fills it, leaving a strip 7 long, or two dominoes lie flat across the last two columns, leaving a strip 6 long. So the ways for length 8 are the ways for 7 plus the ways for 6. Counting up: there is 1 way to tile a strip 1 long and 2 ways for one 2 long, and then each length adds the two before it: 2 + 1 = 3, 3 + 2 = 5, 5 + 3 = 8, 8 + 5 = 13, 13 + 8 = 21, 21 + 13 = 34. So 34 ways. It is not 128 — the last column is not a free choice, because a flat domino uses two columns at once.3. Look at the LAST column of the 2-by-6 board. Either one domino stands upright and fills it, leaving a strip 5 long, or two dominoes lie flat across the last two columns, leaving a strip 4 long. So the ways for length 6 are the ways for 5 plus the ways for 4. Counting up: there is 1 way to tile a strip 1 long and 2 ways for one 2 long, and then each length adds the two before it: 2 + 1 = 3, 3 + 2 = 5, 5 + 3 = 8, 8 + 5 = 13. So 13 ways. It is not 32 — the last column is not a free choice, because a flat domino uses two columns at once.4. Look at the LAST column of the 2-by-3 patio. Either one domino stands upright and fills it, leaving a strip 2 long, or two dominoes lie flat across the last two columns, leaving a strip 1 long. So the ways for length 3 are the ways for 2 plus the ways for 1. Counting up: there is 1 way to tile a strip 1 long and 2 ways for one 2 long, and then each length adds the two before it: 2 + 1 = 3. So 3 ways. It is not 4 — the last column is not a free choice, because a flat domino uses two columns at once.
