Tiling a $2\times3n$ floor with trominoes

Question

Consider a floor of size $2\times3n$ to be tiled with trominoes of which there are two kinds: three blocks connected vertically, and 3 blocks connected in an 'L' shape.

If $x_n$:= the number of possible tilings of a floor of size $2\times3n$, show that $x_n$ satisfies the recurrence relation: $$x_n =3x_{n−1} +2x_{n−2} +2x_{n−3} +\cdots+2x_1. $$

I can show that the relation is true for $x_1$ and $x_2$, I tried to use induction to show for $x_k$ and $x_{k+1}$ but to no avail. How should I go about this?

Answer 1

The claimed recursion immediately implies the simpler recursion $$x_n=4x_{n-1}-x_{n-2}\quad(n\geq2)\ ,\tag{1}$$ and is easy to check the initial values $x_0=1$, $\>x_1=3$.

In order to prove $(1)$ we also consider the tilings of $2\times3n$ having an overlap. These are tilings where $3$ additional squares to the right of the vertical right border are tiled as well. These $3$ squares are forming an L, and are tiled by two different $1\times3$-sticks. Other overlaps can not occur because of the modularity. Let $y_n$ be the number of these fillings with overlap. Checking what can happen between $2\times3(n-1)$ and $2\times3n$ it is now easy to verify that $$x_n=3x_{n-1}+y_{n-1},\qquad y_n=2x_{n-1}+y_{n-1}\ .\tag{2}$$ Replace here $n$ by $n-1$ and subtract the resulting equations. This gives $$x_{n-1}-y_{n-1}=x_{n-2}\ ,\tag{3}$$ and eliminating $y_{n-1}$ from $(2)\wedge(3)$ leads to $(1)$.

Answer 2

You said you were going to edit to make it $2\times3n$ but then didn’t. It should definitely be $2\times3n$; the numbers are way too low for $2\times3^n$.

Divide the floor of size $2\times3n$ into $(2\times3(n-1))+(2\times3)$. There are $x_{n-1}$ ways to tile the first part and $3$ ways to tile the second part, so that makes $3x_{n-1}$ ways to tile them separately.

If a tromino crosses the border, it can’t be an $L$-shaped one, since the remaining separate free areas would not be divisible by $3$. So it must be an $I$-shaped one, and then the other border must also be crossed, by a second $I$ that’s shifted with respect to the first one (again, to retain divisibility by $3$). There are $2$ ways to place these two $I$s and then $1$ way to complete the $2\times3$ part with an $L$-shaped tromino. You can extend the pattern of pairs of shifted $I$-shaped trominos any number of times before topping it off with an $L$, at which point you can tile the remaining $2\times3k$ area in $x_k$ ways. Here $0\le k\le n-2$, so you're missing a term $2x_0=2$ at the end.