Solution
Dominoes and L-Trominoes
Show the problem again
You may use any number of 1 × 2 dominoes (horizontal or vertical) and any number of L-trominoes (three cells forming a 2 × 2 square with one cell missing, in any of its four orientations). In how many ways can a 2 × 8 rectangle be tiled exactly by these pieces? Give an integer.
Worked solution
**Answer: 258.** Cut each tiling at every vertical line that no piece crosses. The pieces between consecutive cuts form an "unbreakable" block. The unbreakable blocks are: a vertical domino (length 1), two stacked horizontal dominoes (length 2), and for each length k ≥ 3 exactly two blocks, made of an L-tromino at each end with k − 3 horizontal dominoes staggered between them (one for each way to choose which row the left tromino sticks out on). So with a(0) = 1, a(n) = a(n − 1) + a(n − 2) + 2[a(n − 3) + a(n − 4) + ... + a(0)]. Subtracting the same identity for a(n − 1) collapses this to a(n) = 2a(n − 1) + a(n − 3). Starting from a(0), a(1), a(2) = 1, 1, 2 we get 5, 11, 24, 53, 117, 258, so a(8) = 258.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.