HMMT November

We tile a $1 \times 12$ board with red $1 \times 1$ pieces, blue $1 \times 2$ pieces, and green $1 \times 2$ pieces. Suppose we use $a$ total pieces, $b$ blue pieces, and $c$ green pieces. Then we must have $a+b+c=12$, and the number of ways to order the pieces is $$\binom{a}{b, c, a-b-c}$$ Thus, the desired sum is the number of ways to do this. Let $a_{n}$ be the number of ways to do this on a $1 \times n$ board. Then we have the recursion $a_{n}=a_{n-1}+2 a_{n-2}$ by casework on the first piece: if it is $1 \times 1$, we are left with a $1 \times n-1$ board, and otherwise we are left with a $1 \times n-2$ board. We also know $a_{1}=1$ and $a_{2}=3$, so the characteristic polynomial for this recursion is $t^{2}-t-2=0$, which has roots 2 and -1 . Thus, $$a_{n}=A \cdot(-1)^{n}+B \cdot 2^{n}$$ Then plugging in $n=1$ and $n=2$ gives $A=-\frac{1}{3}$ and $B=\frac{2}{3}$, so $$a_{n}=\frac{2^{n+1}+(-1)^{n}}{3}$$ With $n=12$, this evaluates to our answer of 2731 .