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

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Hedge Fund Quant

Domino tilings of a 3×8 grid

Answer

Related questions