We are placing tiles of colors red,blue and green in a row. Find a recurrence for number of tile sequences of length n (assuming unlimited supply is given) if
a) No further conditions
b) red tiles cannot be adjacent
c) after 2 adjacent red tiles there has to be a blue tile
d) red and green tiles cannot be adjacent
e) the row must contain a blue or a red tile.
Try: I got a) and b)
Need help on c,d and e
For part e , we have to consider only one case when there is no blue or green tile that is when all the tiles are red and that would be $3^{n}-1$. So, we can assume $a(n) = 3^{n}-1$ and we can continue to find $a(n-1)$ to find the relation between $a(n)$ and $a(n-1) $.
For part c,We have three different cases, the first slide can be $G , B$ or $R$.
First case:Consider the first tile as $Green$. Therefore we have $a(n-1)$ ways for the required condition.
Second case:Consider the first tile as $Blue$. Therefore we have $a(n-1)$ ways for the required condition.
Third case: Consider the first tile as $Red$. We now have three choices for the second tile, Therefore we have 3 sub-cases. a) When second tile is $Green$ we have $RG$ and have $a(n-2)$ ways.
b) When second tile is $Blue$ we have $RB$ and have $a(n-2)$ ways.
c) When second tile is $RED$ we have $RR$ and we have to put a $Blue$ tile as the third tile because it is the required condition. So , we now have $RRB$ and $a(n-3)$ ways.
Therefore, the required relation will be :
$$a(n)= 2*a(n-1) + 2*a(n-2) + a(n-3) $$
We can similarly approach part d)