Question

We want to tile an n x1 strip with 1 x 1 tiles of the following colors: green, red, light-blue, dark-blue, and sky-blue.

a) Let Pn denote the number of different tilings that can be formed of these tiles. Set up and justify the recurrence for Pn. (Do not forget about the initial conditions.) You do not need to solve the recurrence.
b) Let To be the number of such tilings, in which no blue tiles are next to each other. Derive a recurrence relation for the numbers Tn. Give a justification. (Do not forget about the initial conditions.) You do not need to solve the recurrence.

Answer 1

a) The recurrence for Pn is Pn = 5Pn-1. b) The recurrence for Tn is Tn = 2Tn-1 + 2Tn-2.

Step-by-step explanation:

a) To set up the recurrence for Pn, we need to consider the number of ways to tile an n x 1 strip using the given colors. Let's first focus on the last tile in the strip. It can either be green, red, light-blue, dark-blue, or sky-blue. If it is green, the remaining n-1 tiles can be tiled in Pn-1 ways. If it is red, the remaining n-1 tiles can be tiled in Pn-1 ways. If it is light-blue, dark-blue, or sky-blue, the remaining n-1 tiles can be tiled in Pn-1 ways as well.

Therefore, the recurrence for Pn is Pn = Pn-1 + Pn-1 + Pn-1 + Pn-1 + Pn-1 = 5Pn-1.

b) To derive a recurrence relation for Tn, we need to consider the number of ways to tile an n x 1 strip with the condition that no blue tiles are next to each other. Let's again focus on the last tile in the strip. If it is green, the remaining n-1 tiles can be tiled in Tn-1 ways (since no blue tiles are next to each other). If it is red, the remaining n-1 tiles can be tiled in Tn-1 ways. If it is blue, the second last tile must be green or red to satisfy the condition. If the second last tile is green, the remaining n-2 tiles can be tiled in Tn-2 ways. If the second last tile is red, the remaining n-2 tiles can be tiled in Tn-2 ways. Therefore, the recurrence for Tn is Tn = Tn-1 + Tn-1 + Tn-2 + Tn-2 = 2Tn-1 + 2Tn-2.