Question

Problem 5. Let t, denote the number of wayş to tile a 2 x n rectangle using1×1 tiles and L-tiles. L tiles are 2 x 2 tiles with one of the squares missing. Figure 1 shows the L tiles in all possible rotations. 1. Find a recursive formula for tn, including the appropriate initial conditions. Hint: there are 7 cases you need to consider to reduce a 2 x n rectangle to a smaller rectangle, and 3 initial conditions. 2. Find a closed formula for t,.

Answer 1

The two squares at the end could be filled with two 1×1 tiles. The rest can be done in t(n−1) ways.

There could be one 1×1 tile at the left end, on the top or on the bottom. The remaining square can be filled by an L in 1 way, and the rest of the 2×n in t(n−2) ways, for a total of 2t(n−2)

Or else the there could be an L filling both squares on the left (2 ways), with the remaining square filled by a 1×1. That again gives 2t(n−2).

Or else we can have an L on the left filling both squares, and an interlocking L. That gives 2t(n−3) ways of filling the rest.

therefore the formula will be

t(n)=t(n−1)+4t(n−2)+2t(n−3)