# Ways of filling a 2xN board with tetris pieces

How many ways are there of filling a 2xN board with tetris pieces. I stumbled upon a similar problem and this seemed interesting to solve.

This is my progress: Let S(n) be the number of ways of filling a 2xn board. Evidently, S(2)= 1 and S(4)=4. For n congruent to 2 mod 4, S(n)=2S(n-2)-1 as you can add 2x2 squares to any combination that fills a 2x4 board to either side but you have to subtract one as you would be counting twice to the one composed completely of 2x2 squares. I have been trying to determine S(n) for multiples of 4 but have been unsuccessful. I know I can fill it with ones that can fill 2x4 squares n times, but then for large numbers you can move the 2x2 squares around and these combinations make it hard to determine.

• You can't fill a $2 \times 1$ board with Tetris pieces because they all have four squares. – Ross Millikan Apr 5 at 21:48

## 1 Answer

If I recall the Tetris pieces correctly, the only ones you can use here are the $$2 \times 2$$ square, the two $$L$$ pieces, one of each handedness and the straight. If you use an L or a straight you have to fill out a $$2 \times 4$$ rectangle with another of the same. Let $$A(n)$$ be the number of ways to fill a $$2 \times n$$ board. $$A(n)$$ is only defined for even $$n$$. You can fill a $$2 \times n$$ board by making a $$2 \times (n-2)$$ and appending a square or by making a $$2 \times (n-4)$$ and appending one of the two configurations of $$L$$ pieces or a pair of straights. The recurrence is then $$A(n)=A(n-2)+3A(n-4)$$ with starting conditions $$A(0)=1\\A(2)=1$$ The characteristic polynomial is $$r^4=r^2+3$$ with roots $$r^2=\frac 12(1+\sqrt {13}),\frac 12(1-\sqrt {13})$$ so the generic solution is $$A(n)=a(\frac 12(1+\sqrt {13}))^{n/2}+b(\frac 12(1-\sqrt {13}))^{n/2}$$ which give $$a=\frac {1+2\sqrt{13}}4,b=\frac {3-2\sqrt{13}}4$$ and the result is $$A(n)=\frac {1+2\sqrt{13}}4(\frac 12(1+\sqrt {13}))^{n/2}+\frac {3-2\sqrt{13}}4(\frac 12(1+\sqrt {13}))^{n/2}$$

• How is A(0)=1 if it doesn't exist? Additionally, this does not work as A(6)=7. – GuauGuau754 Apr 5 at 21:59
• Your edit still doesn't provide the correct answer for A(6) – GuauGuau754 Apr 5 at 22:04
• Yes, $A(0)=1$ because there is one way to make a $2 \times 0$ rectangle-don't use any pieces. I had forgotten the straight piece, so the $2$ should be a $3$ as there are $3$ ways to make a $2 \times 4$ besides squares. I will update. – Ross Millikan Apr 5 at 22:05
• can you explain how you went from the recursion to the polynomial? – GuauGuau754 Apr 5 at 22:24
• It is the standard technique. You imagine a solution of the form r^n and plug it into the recursion. Each root of the polynomial gives a solution. In this case the polynomial is quadratic in $r^2$ because we are only concerned with even $n$. It would have been cleaner to solve the problem for $2 \times 2n$ rectangles. – Ross Millikan Apr 5 at 22:38