Calculate the number of different ways of tiling 'special' rooms [Read Full Que. Below]

Question

It's a really long question so please bear with me. I will write my approach in the comments since the question is already so big.

You have to tile a room that is two units wide and N units long. You have with you two types of tiles: a rectangle that is one unit wide and two units long, and an L-shaped tile covering three square units. Here are pictures of the two types of tiles.

You are allowed to rotate the tiles when you lay them. You have an infinite supplyof both types of tiles. However, your architect is from Nauru and is a believer in thePolynesian system of tiling calledBatlar Guntuwhich forbids any corner where fourtiles meet.For instance, here are some ways to tile a 2×4 room. The first three are consistentwith theBatlar Guntusystem while the fourth tiling is not

Your task is to calculate the number of different ways a room can be tiled withoutviolating the principles ofBatlar Guntu. For instance, a 2×3 room can be tiled in 5different ways, as follows:

Calculate the number of different ways of tiling rooms of the following sizes:

• a) 2 x 8
• b) 2 x 10
• c) 2 x 12

Answer 1

Any such tiling will be built out of these block patterns:

with the rules

• There are no adjacent $B$ blocks (the only way to have 4 corners together)
• $E$ can only be followed by $F$ or $G$
• $F$ can only follow $E$ or $F$ and only be followed by $F$ or $G$
• $G$ can only follow $E$ or $F$
• $H$ can only be followed by $I$ or $J$
• $I$ can only follow $H$ or $I$ and only be followed by $I$ or $J$
• $J$ can only follow $H$ or $I$

From this you can build some recursion formulas:. Let $a_n$ be the number of tilings for a $2\times n$ room, and let $b_n$ be the number of tilings that do not end with a $B$ block. Setting $a_n =b_n = 0$ for $n < 0$, and $a_0 = b_0 = 1$, for each $n$ there will be

• $a_{n-1}$ tilings ending in an $A$ block.
• $b_{n-2}$ tilings ending in a $B$ block.
• $a_{n-3}$ tilings ending in a $C$ block, and similarly for $D$.
• $a_{n-4}$ tilings ending in $EG$, and similarly for $HJ$.
• $a_{n-4-2k}$ tilings ending in $EF^kG$, and similarly for $HI^kJ$.

So $$a_n = a_{n-1} + b_{n-2} + 2a_{n-3} + 2\sum_{k \le (n-4)/2} a_{n-4-2k}\\b_n = a_n - b_{n-2}$$

The $b_{n-2}$ term can be replaced by a sum of $a_k$ values to get a recursion in one dimension. Taking the difference between $a_n$ and $a_{n-2}$ results in a simpler recursion formula, having only a summation for the replaced $b_{n-2}$ term. The same trick can be applied a second time to remove this remaining sum, leaving a linear recursion formula in $a_n$ of fixed length. I'll leave the details of it to you.