Build a recursive function for the number of ways to place n tiles of colors grey, black, green or red if no 3 red tiles occur consecutively.

Question

Build a recursive function for the number of ways to place n tiles of colors grey, black, green or red if no 3 red tiles occur consecutively. Do not solve the recursion but give adequate initial conditions.

So I got out my combinatorics exam and this problem really messed me up.

This was my approach:

The total number of ways to place n tiles from these 4 colors is:

$\ 4^n$

If you start with the grey, green or black, you can place them any way which is:

$\ 3a_{n-1}$

And if you start with reds then except $\ a_{n-3}$, they should all be fine.

SO the overall formula I came up with was:

$\ 3a_{n-1} + 4^{n-1} - a_{n-3}$

With initial conditions:

$\ a_0=1, a_1 = 4, a_2 = 16, a_3=63 $

But i'm almost certain that isn't correct. What is the correct way of doing this?

Thanks for all the help.

Answer 1

Hint: Let $a(n)$ be the number of ways that do not end in a red tile, $b(n)$ the number of these ways ending in exactly one red tile, $c(n)$ the number of these ways ending in two red tiles. Find expressions for $a(n+1)$, $b(n+1)$, $c(n+1)$ in terms of $a(n), b(n), c(n)$.