# Number of ways to tile a room with $I$-Shaped and $L$-Shaped Tiles

There is a room of dimensions $$2\times n$$. You have to tile it using $$2$$ types of tiles:

• I-Shaped Tile ($$2\times1$$)
• L-Shaped Tile ($$2\times1 + 1$$)

However, you are forbidden to use any tiling where any four corners of the tiles meet.

For example for a $$2\times4$$ room, the first three will be counted and the last one will not be counted.

My Attempt

If the condition that four corners cannot meet wasn't given, a pretty neat recurrence can be formed.

$$f(n) = f(n-1) + f(n-2) + 2g(n-1)$$ $$g(n) = f(n-2) + g(n-1)$$

with $$g(0) = g(1) = 0$$ and $$f(0) = f(1) = 1$$ where $$f(n) =$$ number of ways of tiling a $$2\times n$$ rectangle and $$g(n)=$$ number of ways of tiling a $$2\times n$$ rectangle with a square missing on top.

Hence, we multiply $$g(n-1)$$ by $$2$$ when calculating $$f(n)$$ because the missing square can be at the top or the bottom.

I am unable to find such a recurrence with the extra given condition.

• Doron Zeilberger's student Paul Raff implies in his dissertation that this indeed has a linear recurrence. – Peter Kagey Nov 7 at 19:39
• Can someone confirm the first few values? I get $1,2,5,10,22,49,105 \dots$ – Michael Biro Nov 7 at 21:07
• @MichaelBiro that matches what I get. – Misha Lavrov Nov 7 at 21:20

The variant can be settled by splitting up into three cases:

• $$f_1(n)$$, the number of ways to tile a rectangle ending with a flat line,
• $$f_2(n)$$, the number of ways to tile a rectangle where two corners meet in the middle,
• $$g(n)$$, the number of ways to tile a rectangle where the top right square is missing.

We have $$f_1(n) = f_1(n-1) + f_2(n-1) + 2 g(n-1)$$ because the last tile of a rectangle ending in a flat line can either be an I tile or an L tile oriented in two ways. We just have $$f_2(n) = f_1(n-2)$$ since the only way to create an $$f_2$$-type rectangle is to put down two horizontal dominoes at the end, and just as before, we have $$g(n) = f_1(n-2) + f_2(n-2) + g(n-1).$$

From here, it's also possible to write down a linear recurrence for just the total $$f(n) = f_1(n) + f_2(n)$$ in terms of $$f(n-1), f(n-2), \dots$$. We have $$f(n) = f_1(n) + f_2(n) = f_1(n) + f_1(n-2)$$, so it's enough to solve for $$f_1(n)$$. In fact, as a linear combination of $$f_1$$ and its translate, $$f$$ will satisfy the same recurrence relation as $$f_1$$ with different initial conditions.

From $$g(n) = f_1(n-2) + f_1(n-4) + g(n-1)$$, we get the infinite series $$g(n) = f_1(n-2) + f_1(n-3) + 2f_1(n-4) + 2f_1(n-5) + \dotsb$$, and this gives us a recurrence \begin{align} f_1(n) &= f_1(n-1) + f_2(n-1) + 2g(n-1) \\ &= f_1(n-1) + f_1(n-3) + 2g(n-1) \\ &= f_1(n-1) + 3f_1(n-3) + 2f_1(n-4) + 4f_1(n-5) + 4f_1(n-6) + \dotsb \\ \end{align} Subtracting $$f_1(n-1)$$ from $$f_1(n)$$, we get $$f_1(n) - f_1(n-1) = \color{red}{(f_1(n-1) + 3f_1(n-3) + 2f_1(n-4) + 4f_1(n-5) + 4f_1(n-6) + \dotsb )} - \color{blue}{(f_1(n-2) + 3f_1(n-4) + 2f_1(n-5) + 4f_1(n-6) + 4f_1(n-7) + \dotsb )}$$ and most of the red terms cancel with blue terms, leaving us with $$f_1(n) - f_1(n-1) = f_1(n-1) - f_1(n-2) + 3f_1(n-3) - f_1(n-4) + 2f_1(n-5)$$ or $$f_1(n) = 2f_1(n-1) - f_1(n-2) + 3f_1(n-3) - f_1(n-4) + 2f_1(n-5)$$. As observed earlier, this also means that the recurrence $$f(n) = 2f(n-1) - f(n-2) + 3f(n-3) - f(n-4) + 2f(n-5)$$ holds.

The first few nonzero terms of the sequence are $$1, 1, 2, 5, 10, 22, 49, 105, 227, 494, 1071, \dots$$, as computed by @PeterKagey in the comments and in the upcoming OEIS listing.

• I submitted this sequence as a draft to the OEIS. Once approved, it will be here. – Peter Kagey Nov 7 at 21:05
• It's worth pointing out that the initial conditions for this recurrence are $f(0) = f(1) = 1, f(2) = 2, f(3) = 5$, and $f(4) = 10$. The sequence begins $1, 1, 2, 5, 10, 22, 49, 105, 227, 494, 1071, 2322, 5038, 10927, 23699, 51405, \dots$ – Peter Kagey Nov 7 at 21:26
• I have some general questions on what happens after you find $k$ "inter-related" recurrences, like the $k=3$ here inter-relating $f_1, f_2, g$. (1) Is it always possible to turn the system into $k$ separate recurrences? I.e. write $f_1(n)$ only in terms of a finite number of $f_1(n-t)$ and no $f_2$ etc. (2) Is it always possible to write a recurrence on $f(n)$ using only a finite number of $f(n-t)$, where $f$ is the sum (or any linear combo?) of the $f_i$? I know the matrix way of writing the $k$ interrelated recurrences, but I can't quite see how to "decouple" and then "sum" ... – antkam Nov 8 at 5:38
• @antkam It's always possible just by the general argument of "a system of $k$ linear recurrences leads to $k$ rational generating functions, which have their own decoupled linear recurrences", but I'm not sure that I have a general method to point to. – Misha Lavrov Nov 8 at 5:42
• Sorry, I don't understand enough about generating functions to understand your argument. :) Anyway, are you saying there is not a method like take inter-related recurrences in matrix form, then row-reduce it or diagonalize it etc and it will always work? So what happened here, when you found the finite recurrences for $f_1$ and $f$, that was art instead of procedural? Also, even if you can decouple the $k$ recurrences, does that also imply you can write a recurrence on the sum $f$? Here you relied on $f$ being a lin comb of $f_1$ and its translates, but that doesn't always happen, right? – antkam Nov 8 at 5:57