Solution
Straight Trominoes on a 3 × 12 Board
Show the problem again
In how many ways can a 3 × 12 rectangle (3 rows, 12 columns) be tiled exactly by twelve 1 × 3 straight trominoes, each placed horizontally or vertically? Tilings related by a symmetry of the rectangle count as different. Give an integer.
Worked solution
**Answer: 60.** Look at the top-left cell. If it is covered by a vertical bar, that bar fills the entire first column, leaving a 3 × 11 board. Otherwise it is covered by a horizontal bar; then the middle-left cell cannot be vertical (the top cell of column 1 is taken), so it is also horizontal, and likewise the bottom-left cell. Three stacked horizontal bars fill a 3 × 3 block, leaving a 3 × 9 board. So a(n) = a(n − 1) + a(n − 3) with a(0) = a(1) = a(2) = 1. The sequence continues 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, so a(12) = 60.
Source: Original problem written for AxiomIQ.