Tile a 3×n grid with 1×2 dominoes. The width is fixed and small (3 cells). Profile has 3 bits. Only 8 possible masks. Enumerate transitions by hand or compute programmatically.
Key: many masks are unreachable. For 3×n, only certain patterns work. The recurrence simplifies. Find: f[n]=4f[n−2]−f[n−4] (or similar). Small width allows closed-form recurrences. Width 3 is small enough that transitions can be enumerated by hand. Find the pattern in the recurrence.