Domino tilings, step by step
Cover a strip two squares wide and n long with dominoes, and count the ways.
In how many different ways can it be covered?
Count the tilings by the last column
- One strip to start from: 2 squares tall and 8 long, to be covered by dominoes with none overlapping or sticking out.
- Look at the LAST column. Either one domino stands upright and fills it, leaving a strip 7 long, or two lie flat across the last two columns, leaving a strip 6 long. So the ways for 8 are the ways for 7 plus the ways for 6.
- Count up from the start: a strip 1 long has 1 way, a strip 2 long has 2 ways, and each length after that is the two before it added.
- So 34 ways. It is not 128 — the counts start 1, 2 and look like they double, but a flat domino uses two columns, so the last column is never a free choice.
How it works.
- 01
One strip to start from: 2 squares tall and 8 long, to be covered by dominoes with none overlapping or sticking out.
- 02
Look at the LAST column. Either one domino stands upright and fills it, leaving a strip 7 long, or two lie flat across the last two columns, leaving a strip 6 long. So the ways for 8 are the ways for 7 plus the ways for 6.
- 03
Count up from the start: a strip 1 long has 1 way, a strip 2 long has 2 ways, and each length after that is the two before it added.
- 04
So 34 ways. It is not 128 — the counts start 1, 2 and look like they double, but a flat domino uses two columns, so the last column is never a free choice.