Number of $6$-digit numbers made up of the digits $1$, $2$, and $3$ with no digit occurring $3$ or more times consecutively? Find the number of 6-digit numbers made up of the digits $1$, $2$, and $3$ that have no digit occur three or more times consecutively. (For example, $123123$ would count, but $123111$ would not.)
We know the total number of possibilities without the occurrence restriction is $3^6 = 729$. 
In order to eliminate the possibilities that can't be used, I set a block of 3 numbers as my 3 consecutive digits block. This block would have 3 different combinations. I then split the number of eliminations into 2 cases: one where the block of 3 is in the front, and one where the block of 3 is in the middle. 
For case 1: I computed $3\cdot 24$, with $3$ being the ways to change the block of 3, and $24$ being the number of ways to change the other 3 numbers while not having another block of 3 consecutive. 
For case 2: I computed $3^4$, ignoring the restriction of case 1. 
Summing the 2 cases, I got $72+ 3\cdot 81 = 315$, I then subtracted from $729$ and got $414$, which turns out to be incorrect. What am I doing wrong?
 A: There are $3^6 = 729$ possible sequences.  From these, we must subtract those in which three consecutive digits are the same.
Observe that a prohibited sequence must begin in one of the first four positions.  Let $A_1, A_2, A_3, A_4$ be the set of outcomes in which three consecutive digits beginning in the first, second, third, and fourth positions, respectively, are the same.
The set of outcomes that violate the restriction is $A_1 \cup A_2 \cup A_3 \cup A_4$.  By the Inclusion-Exclusion Principle, 
\begin{align*}
|A_1 \cup A_2 \cup A_3 \cup A_4| & = |A_1| + |A_2| + |A_3| + |A_4|\\
                                 & \quad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_1 \cap A_4| - |A_2 \cap A_4| - |A_3 \cap A_4|\\ 
                                 & \quad + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4|\\
                                 & \quad - |A_1 \cap A_2 \cap A_3 \cap A_4|
\end{align*}
$|A_1|$:  There are three ways of selecting the number that occupies the first three positions and three ways of selecting the number that occupy each of the last three positions.  Hence, $|A_1| = 3^4$.  By symmetry,
$$|A_1| = |A_2| = |A_3| = |A_4| = 3^4$$
$|A_1 \cap A_2|$:  Since the first three and the second three positions overlap, the first four positions must be filled with the same number.  There are three ways to select this number and three ways to fill each of the remaining two positions.  Hence, $|A_1 \cap A_2| = 3^3$.  By symmetry,
$$|A_1 \cap A_2| = |A_2 \cap A_3| = |A_3 \cap A_4| = 3^3$$
$|A_1 \cap A_3|$:  Since the first three and the third three positions overlap, the first five positions must be filled with the same number.  There are three ways to select this number and three ways to fill the remaining position.  Hence, $|A_1 \cap A_3| = 3^2$.  By symmetry,
$$|A_1 \cap A_3| = |A_2 \cap A_4| = 3^2$$
$|A_1 \cap A_4|$:  Since the first three and last three positions do not overlap, the first three positions can be filled in three ways, as can the last three.  Hence, 
$$|A_1 \cap A_4| = 3^2$$
$|A_1 \cap A_2 \cap A_3|$:  Since these sets overlap, the first five positions must be filled with the same number.  There are three ways to choose this number and three ways to fill the remaining position.  Thus, $|A_1 \cap A_3 \cap A_3| = 3^2$.  By symmetry,
$$|A_1 \cap A_2 \cap A_3| = |A_2 \cap A_3 \cap A_4| = 3^2$$
$|A_1 \cap A_2 \cap A_4|$:  Since the first three positions overlap with the second three and the second three positions overlap with the last three positions, all six positions must be the same.  There are three ways to select the number that fills all six positions.  Hence, $|A_1 \cap A_2 \cap A_4| = 3$. By symmetry,
$$|A_1 \cap A_2 \cap A_4| = |A_1 \cap A_3 \cap A_4| = 3$$
$|A_1 \cap A_2 \cap A_3 \cap A_4|$:  All six positions must be filled with the same number.  Since there are three ways to select the number,
$$|A_1 \cap A_2 \cap A_3 \cap A_4| = 3$$
By the Inclusion-Exclusion Principle,
\begin{align*}
|A_1 \cup A_2 \cup A_3 \cup A_4| & = 3^4 + 3^4 + 3^4 + 3^4\\
                                 & \quad - 3^3 - 3^2 - 3^2 - 3^3 - 3^2 - 3^3\\
                                 & \quad + 3^2 + 3 + 3 + 3^2\\
                                 & \quad - 3\\ 
                                 & = 237
\end{align*}
Hence, there are $729 - 237 = 492$ admissible sequences.
A: Denote by $a_n$ the number of admissible words of length $n\geq1$. Then $a_1=3$, $a_2=9$. Furthermore we have the recursion
$$a_n=2a_{n-1}+2a_{n-2}\qquad(n\geq3)\ .\tag{1}$$
Proof. The last two letters of an admissible word $w$ of length $n$ are either different or equal. In the first case the word $w$ results from appending a letter to an admissible word $w'$ of length $n-1$ which is different from the last letter of $w'$. In the second case the word $w$ results from appending two equal letters to an admissible word $w''$ of length $n-2$ which are different from the last letter of $w''$. $\quad\square$
Given the initial conditions one can solve $(1)$ using the "Master Theorem". As only $a_6$ is required we can do the necessary steps by hand and arrive at $a_6=492$.
A: Discussion of what's missing in your answer
There are four places a block of three can start in the number.
$$\begin{matrix}
(1): && d & d & d & \cdot & \cdot & \cdot  \\
(2): && \cdot & d & d & d & \cdot & \cdot  \\
(3): && \cdot & \cdot & d & d & d & \cdot  \\
(4): && \cdot & \cdot & \cdot & d & d & d  \\
\end{matrix}$$
You have only discussed the first two.  Additionally, if we just count these four configurations, we overcount configurations where there are four, five, or six consecutive digits.  For instance, $111111$ can only be generated one way, but it has been included in the counts for configurations (1), (2), (3), and (4), so has been quadruple-counted.
Corrected version of your answer
There are ten ways to have three (or more) consecutive digits: 
$$\begin{matrix}
(1): && d & d & d & \cdot & \cdot & \cdot  \\
(2): && \cdot & d & d & d & \cdot & \cdot  \\
(3): && \cdot & \cdot & d & d & d & \cdot  \\
(4): && \cdot & \cdot & \cdot & d & d & d  \\
(5): && d & d & d & d & \cdot & \cdot  \\
(6): && \cdot & d & d & d & d & \cdot  \\
(7): && \cdot & \cdot & d & d & d & d  \\
(8): && d & d & d & d & d & \cdot  \\
(9): && \cdot & d & d & d & d & d  \\
(10): && d & d & d & d & d & d
\end{matrix} $$
We will proceed by inclusion-exclusion.
And then proceed as shown by N.F.Taussig's answer.  (I was about half way through when he saved me having to finish it.)
A solution that avoids explicit inclusion-exclusion
From each string of six digits, $d_1 d_2 d_3 d_4 d_5 d_6$, let us construct a new string of length $5$ having an "s" in position $i$ if $d_i = d_{i+1}$ and an "n" if $d_i \neq d_{i+1}$, as $i$ ranges from $1$ to $5$.  A digit occurring three or more times consecutively corresponds to two or more consecutive "s"s.  There are only $3$ choices of first pairs of digits which produce an "s" in the first position and $6$ choices of pairs of digits which produce an "n" in the first position.  Following an "s" only one choice of digit can produce an "s" (which corresponds to disallowed three consecutive digits) and two choices of digit produce an "n".  Following an "n" one choice of digit produces an "s" and two choices of digit produce an "n".
The acceptable 5 letter strings, with their counts and a running sum, are \begin{align*}
snsns  &&  3 \cdot 2 \cdot 1 \cdot 2 \cdot 1 = 12  && 12  \\
snsnn  &&  3 \cdot 2 \cdot 1 \cdot 2 \cdot 2 = 24  && 36  \\
snnsn  &&  3 \cdot 2 \cdot 2 \cdot 1 \cdot 2 = 24  && 60  \\
snnns  &&  3 \cdot 2 \cdot 2 \cdot 2 \cdot 1 = 24  && 84  \\
snnnn  &&  3 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 48  && 132  \\
nsnsn  &&  6 \cdot 1 \cdot 2 \cdot 1 \cdot 2 = 24  && 156  \\
nsnns  &&  6 \cdot 1 \cdot 2 \cdot 2 \cdot 1 = 24  && 180  \\
nsnnn  &&  6 \cdot 1 \cdot 2 \cdot 2 \cdot 2 = 48  && 228  \\
nnsns  &&  6 \cdot 2 \cdot 1 \cdot 2 \cdot 1 = 24  && 252  \\
nnsnn  &&  6 \cdot 2 \cdot 1 \cdot 2 \cdot 2 = 48  && 300  \\
nnnsn  &&  6 \cdot 2 \cdot 2 \cdot 1 \cdot 2 = 48  && 348  \\
nnnns  &&  6 \cdot 2 \cdot 2 \cdot 2 \cdot 1 = 48  && 396  \\
nnnnn  &&  6 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 96  && 492  \\
\end{align*}
So there are $492$ allowed configurations.
I generally prefer this method because it more directly corresponds to the tree of consecutive digit choices.
