Question

g Consider a 1 × n floor to be covered by 1 × 1 tiles that come in three different colors(Blue, Red, Green) and 1 × 2 tiles that come in 2 different colors (orange, white). Find a recurrence relation for the number of the ways the floor can be tiled. (Just find the recurrence relation together with an appropriate number of initial terms. Do not solve the recurrence)

Answer 1

`f(n) = 3f(n - 1) + 2f(n - 2)`, if
`n \geq 2`.

`f(0) := 1`,
`f(1) := 3`

Explanation:

Let
`f(n)` be the number of different tiling of
`1 * n` floor. We can divide all possible tiling of floor
`1 * n` into five not overlapping groups by color of last cell in the row (Blue, Red, Green, Orange, White).

The number of tiling
`1* n` floor such that last cell in row is Blue is exactly f(n - 1) because we can throw away last
`1* 1` tile and cover the rest
`1* (n - 1)` cells in f(n - 1) ways. Similarly for Red and Green.

The number of tiling
`1* n` floor such that last cell in row is Orange is exactly f(n - 2) because we can throw away last
`1* 2` tile and cover the rest
`1* (n - 2)` cells in f(n - 2) ways. Similarly for White.

So we get recurrent relation:

`f(n) = 3f(n - 1) + 2f(n - 2)`, if
`n \geq 2`.

Now we should define the initial conditions.

`f(0) := 1` because there is only one empty tiling.

`f(1) := 3` because we can place Blue, Red or Green tile.

This completely define our recurent sequence because the depth of reccurence is 2.