Domino tilings of a 3×8 grid

HardCombinatorics~9m

In how many ways can a $3 \times 8$ grid be tiled completely by $1 \times 2$ dominoes (each domino placed either horizontally or vertically, no overlaps, no gaps)?

Show hints (2)+

Let $a_n$ tile a $3\times n$ board; $a_n=0$ for odd $n$ . Find the even-width recurrence.
It is $a_n = 4a_{n-2} - a_{n-4}$ with $a_0=1, a_2=3$ . Iterate to $a_8$ .

Answer

Reveal answer →

153

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Jane Street, Citadel

Domino tilings of a 3×8 grid

Answer

Related questions