Solution
Dominoes on a 3 × 10 Board
Show the problem again
In how many ways can a 3 × 10 rectangle be tiled completely by fifteen 1 × 2 dominoes (each placed horizontally or vertically)? Tilings related by a symmetry of the rectangle count as different. Give an integer.
Worked solution
**Answer: 571.** Let f(n) count tilings of a 3 × n board and g(n) count tilings of a 3 × n board with one corner cell removed (by symmetry it does not matter which). Examining the left edge of a full board: either the first two columns are closed off by three stacked horizontal dominoes (f(n − 2)), or a vertical domino covers two cells of column 1 together with a horizontal domino in the remaining cell, leaving a board with a missing corner (2 g(n − 1), one for each choice of which pair is vertical). For the notched board, the remaining two cells of the first column are either a vertical domino (f(n − 1)) or two horizontal dominoes that create another notch (g(n − 2)). So f(n) = f(n − 2) + 2g(n − 1) and g(n) = f(n − 1) + g(n − 2). Eliminating g gives f(n) = 4f(n − 2) − f(n − 4), with f(0) = 1, f(2) = 3. Hence f(4) = 11, f(6) = 41, f(8) = 153, f(10) = 4·153 − 41 = 571.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.