Puzzle:
Including reflections as unique solutions, how many ways can you tile a 2×N rectangle with dominoes?
Choose your adventure:
If you’d like to find joy in exploring for yourself, you can stop reading here; enjoy!
If you’d like to see the answer, along with a rough proof, click below.
show solution
Let’s have Fn represent the number of tilings of a 2×N rectangle. We can see that F0 and F1 are both 1 — there’s only one way to tile a zero-width rectangle (with zero tiles), and only one way to tile a 2×1 rectangle (with one tile).For larger rectangles, consider the following:
The end of a 2×N rectangle can be filled with dominoes in two ways — a vertically-oriented domino, or two horizontally-oriented dominoes.
If we place a domino vertically at the end of our 2×N rectangle, we’re left with a 2×(N-1) space, which can be filled Fn-1 ways.
Similarly, if we place a pair of dominoes horizontally at the end of our 2×N rectangle, we’re left with a 2×(N-2) space, which can be filled Fn-2 ways.
From this, we can conclude that Fn = Fn-1 + Fn-2, and with initial conditions of F0 = 1 and F1 = 1, this gives us the Fibonacci sequence!