Domino tilings
The question
A 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?
Count the tilings by the last column
tall:2 long:8
T(n) =T(n-1)+T(n-2)
2+1=3
3+2=5
5+3=8
8+5=13
13+8=21
21+13=34
34
- 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 — not 128. It is not doubling, because a flat domino uses two columns at once.
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 — not 128. It is not doubling, because a flat domino uses two columns at once.