You need to tile a n times 1 hallway with unlimited supply o

You need to tile a n times 1 hallway with unlimited supply of 1 times 1 red tiles, 2 times 1 red tiles, and 2 times 1 blue tiles. Write down the recurrence formula and initial conditions for the number of ways to tile: A n times 1 hallway for which you are allowed to use all types of tiles. A n times 1 hallway for which you are allowed to use all types of tiles, but no two red tiles are consecutive.

Solution

Hi buddy,

Let\'s simplify the problem. Since we are dealing with 2d array where the second dimension is always 1, we will cut this problem to 1dimension. So, problem can be stated as counting number of ways of placing 3 different types of tiles. i.e Red of size 1, Red of size 2 and blue of size 2.

1. Number of way of placing tiles where we are allowed to use all types of tiles.

Let\'s define a function called ways, where ways(n) calculates number of ways of placing the tiles. Let\'s do some initializations. If n=1, Then there is only one way to arrange. i.e placing red tile of size 1. If n=2, there are 3 ways. i.e 2 consecutive red tiles of size 1, or either of the red or blue tile of size 2.

So, ways(1) = 1; ways(2) = 3. Now let\'s try to construct the recursive formula.

ways(n) = ways(n-1) (when a red tile of size 1 is placed)+ ways(n-2) (when a red tile of size 2 is placed)+ ways(n-2) (when a blue tile of size 2 is placed);

So, ways(n) = ways(n-1) + 2*ways(n-2);

2. Number of ways of arranging tiles such that no two consecutive red tiles are allowed.

Let\'s again define a function ways such that ways(n,COLOR) calculates the number of ways of arranging n tiles and the color of the last arranged tile is given by COLOR.

Let\'s do some initializations. if n = 1? Then there is only one way i.e placing a red tile of size 1.

If n = 2? Then thre are only 2 ways. i.e placing a red or blue tile of size 2.

So, ways(1,RED) = 1, ways(1,BLUE) = 1. That means if n = 1, number of ways will be 1.

similarily ways(2,RED) = 2, ways(2,BLUE) = 2. That means if n=2, number of ways will alway be 2.

Let\'s form a recursive formula.

ways(n,COLOR) = if(COLOR!=RED)(ways(n-1,RED)+ways(n-2,RED)) + ways(n-2,BLUE)