4
$\begingroup$

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$)

image

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.

Example

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.

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

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.

$\endgroup$
  • 2
    $\begingroup$ I submitted this sequence as a draft to the OEIS. Once approved, it will be here. $\endgroup$ – Peter Kagey Nov 7 at 21:05
  • 1
    $\begingroup$ 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$ $\endgroup$ – Peter Kagey Nov 7 at 21:26
  • $\begingroup$ 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" ... $\endgroup$ – antkam Nov 8 at 5:38
  • $\begingroup$ @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. $\endgroup$ – Misha Lavrov Nov 8 at 5:42
  • $\begingroup$ 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? $\endgroup$ – antkam Nov 8 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.