This is an interesting problem that I remembered today:
If a billboard can be painted either red, orange, or yellow, and it is never painted red for 3 days in a row, then how many paint-sequences could possibly show up in the duration of one week?
My first thought was to just list all the possibilities, as I believed there wouldn't be many, but I felt that this was probably not the solution that was intended to solve this problem.
Then, I thought that perhaps I could use casework with complementary counting (so I would try counting possibilities where there are 3 days in a row where the board is painted red, and I would do casework over which of the 7 days in the week is the first day within the 3 days in a row). However, I found a problem with this method, which is that when doing two different cases, say, some of the possibilities may overlap, and I don't know how to account for this overcounting.
So, can someone confirm if my general thinking here is correct at all? Or is there another solution besides casework that can be used to solve this problem?
Added an Addendum which highjacks the idea in lulu's comment.
As others have discussed, the problem reduces to enumerating how many ways there are of having at least one occurrence of 3 consecutive red days in the week.
David's answer discusses the direct approach; the alternative approach is Inclusion-Exclusion.
It is not uncommon in problems like this, that involve a small number (i.e. only $7$ days in the week), for the direct approach to be easier than Inclusion-Exclusion. However, the alternative consideration is that Inclusion-Exclusion generalizes well.
Using Inclusion-Exclusion:
Let a sequence like r-x-r-r-r-x-x represent that days 1, 3, 4, and 5, were red, and the other days were unknown.
Let :
$A_1$ represent r-r-r-x-x-x-x.
$A_2$ represent x-r-r-r-x-x-x.
$A_3$ represent x-x-r-r-r-x-x.
$A_4$ represent x-x-x-r-r-r-x.
$A_5$ represent x-x-x-x-r-r-r.
I will let $T_k ~k: ~k \in \{1,2,3,4,5\}$ represent the number of ways that there are at least $k$ occurrences of 3 consecutive red days, in the 7 day week. Then, the final computation will be:
$$T_1 - T_2 + T_3 - T_4 + T_5$$.
The number of ways of sequence $A_1$ occurring is $3^4$. Since the same enumeration holds for $A_2, A_3, A_4,$ and $A_5$:
$T_1 = 5 \times 3^4 = 405.$
So, $T_1$ represents the enumeration where there is at least one sequence of 3 consecutive red days.
Then, in order to enumerate $T_2$, you have to enumerate $A_r \cap A_s ~: ~1 \leq r < s \leq 5.$
$A_1 \cap A_2 ~: ~ 3^3.$
$A_1 \cap A_3 ~: ~ 3^2.$
$A_1 \cap A_4 ~: ~ 3^1.$
$A_1 \cap A_5 ~: ~ 3^1.$
$A_2 \cap A_3 ~: ~ 3^3.$
$A_2 \cap A_4 ~: ~ 3^2.$
$A_2 \cap A_5 ~: ~ 3^1.$
$A_3 \cap A_4 ~: ~ 3^3.$
$A_3 \cap A_5 ~: ~ 3^2.$
$A_4 \cap A_5 ~: ~ 3^3.$
Therefore,
$T_2 = (4 \times 3^3) + (3 \times 3^2) + (3 \times 3^1) = 144.$
Now, to compute $T_3$, you have to enumerate $A_r \cap A_s \cap A_t ~: ~1 \leq r < s < t \leq 5.$
$A_1 \cap A_2 \cap A_3 ~: ~ 3^2.$
$A_1 \cap A_2 \cap A_4 ~: ~ 3^1.$
$A_1 \cap A_2 \cap A_5 ~: ~ 3^0.$
$A_1 \cap A_3 \cap A_4 ~: ~ 3^1.$
$A_1 \cap A_3 \cap A_5 ~: ~ 3^0.$
$A_1 \cap A_4 \cap A_5 ~: ~ 3^0.$
$A_2 \cap A_3 \cap A_4 ~: ~ 3^2.$
$A_2 \cap A_3 \cap A_5 ~: ~ 3^1.$
$A_2 \cap A_4 \cap A_5 ~: ~ 3^1.$
$A_3 \cap A_4 \cap A_5 ~: ~ 3^2.$
Therefore,
$T_3 = (3 \times 3^2) + (4 \times 3^1) + (3 \times 3^0) = 42.$
Now, to compute $T_4$, you have to enumerate $A_r \cap A_s \cap A_t \cap A_u ~: ~1 \leq r < s < t < u \leq 5.$
$A_1 \cap A_2 \cap A_3 \cap A_4 ~: ~ 3^1.$
$A_1 \cap A_2 \cap A_3 \cap A_5 ~: ~ 3^0.$
$A_1 \cap A_2 \cap A_4 \cap A_5 ~: ~ 3^0.$
$A_1 \cap A_3 \cap A_4 \cap A_5 ~: ~ 3^0.$
$A_2 \cap A_3 \cap A_4 \cap A_5 ~: ~ 3^1.$
Therefore,
$T_4 = (2 \times 3^1) + (3 \times 3^0) = 9.$
Now, to compute $T_5$, you have to enumerate $A_r \cap A_s \cap A_t \cap A_u \cap A_v ~: ~1 \leq r < s < t < u < v \leq 5.$
$A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5 ~: ~ 3^0.$
Therefore,
$T_5 = 1.$
Final answer:
$$T_1 - T_2 + T_3 - T_4 + T_5 = 405 - 144 + 42 - 9 + 1 = 295.$$
Therefore, there are $295$ distinct paint sequences that violate the constraint of not having 3 consecutive red days.
Therefore, there are $3^7 - (295) = 2187 - 295 = 1892$
paint sequences that do not violate the constraint.
Confession : I did Java-sanity-check.
Addendum
Hijacking the idea in lulu's comment.
Let $f(k,n) ~: ~n \in \Bbb{Z^+}, ~k \in \{0,1,2\}~$ denote the number of $n$ character sequences that end with $k$ "R"-s. Here, it is assumed that no sequence can have 3 consecutive "R"-s, and that each character is "R", "O", or "Y".
Let "p" denote any character other than "R".
Let "q" denote any of the three characters.
Then,
$f(0,3)$, which is represented by qqp, $~= 3^2 \times 2 = 18.$
$f(1,3)$, which is represented by qpR, $~= 3 \times 2 = 6.$
$f(2,3)$, which is represented by pRR, $~= 2.$
The easiest way to develop the recursion formulas is to manually compute $f(0,4), f(1,4),$ and $f(2,4)$. Then, check whether the transition from $(n=3)$ to $(n=4)$ will hold for $n \to (n+1).$
To compute $f(0,4)$, note that any of the sequences represented by $f(0,3), f(1,3),$ or $f(2,3)$ can be continued by either an "O" or a "Y".
Therefore,
$f(0,4) = 2 \times [f(0,3) + f(1,3) + f(2,3)].$
To compute $f(1,4)$, you must start with a sequence represented by $f(0,3)$ and then add an "R" to the end of it.
Therefore,
$f(1,4) = f(0,3)$.
Similarly, to compute $f(2,4)$, you must start with a sequence represented by $f(1,3)$ and then add an "R" to the end of it.
Therefore,
$f(2,4) = f(1,3)$.
In considering the transition from $n \to (n+1)$, the analysis of the transition from $(3) \to (4)$ holds.
Therefore
$f(0,n+1) = 2 \times [f(0,n) + f(1,n) + f(2,n)].$
$f(1,n+1) = f(0,n)$.
$f(2,n+1) = f(1,n)$.
This leads to the following table:
\begin{array}{| r | r | r | r |} \hline n & f(0,n) & f(1,n) & f(2,n) \\ \hline 3 & 18 & 6 & 2 \\ \hline 4 & 52 & 18 & 6 \\ \hline 5 & 152 & 52 & 18 \\ \hline 6 & 444 & 152 & 52 \\ \hline 7 & 1296 & 444 & 152 \\ \hline \end{array}
$1296 + 444 + 152 = 1892.$