Tiling a 2×12 Strip

Question

How many ways are there to tile a 2 times 12 strip with 1 times 2 dominoes (horizontal or vertical)?

Accepted Answer

Let f(n) count tilings of 2 times n. The rightmost column is covered either by one vertical domino (leaving 2 times (n-1)) or by two stacked horizontal dominoes occupying the last two columns (leaving 2 times (n-2)), a single horizontal can't cover the last column alone. Disjoint, exhaustive: f(n) = f(n-1) + f(n-2), qquad f(1) = 1, f(2) = 2. Forward: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, mathbf233. So f(12) = 233 (the 13th Fibonacci number). Indexing trap: "it's Fibonacci" is only half an answer, interviewers watch whether you anchor the small cases rather than guess the offset. f(1) = 1 and f(2) = 2 pin it; recomputing beats recalling. This recurrence is the same one behind stair-climbing and no-adjacent-1s strings; the bijection (vertical ↔ take 1 step, horizontal pair ↔ take 2) is worth stating, because "I've seen this graph before" is exactly the pattern-matching the algorithmic shops are screening for.

Tiling a 2×12 Strip

Problem

Your answer

Hints

More Combinatorics to train on