Tri Tiling - Walkthrough

Tile a $3 \times n$ grid with $1 \times 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.

Many masks are unreachable. For $3 \times 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.