<s>[INST] Generalized repetitions of letters with limited amount of adjacent letters Say I have the first $x$ letters of the alphabet, and I want to generate a sequence of length $y$, such that there are no more than $z$ adjacent repeated letters. For example, if $x = 2$, $y = 3$ and $z = 2$, here are all the valid sequences:
AAB ABA ABB BAA BAB BBA
How many total possible sequences are there?
Without the restriction of z, the question devolves to $x^y$, but I am stuck as to how to proceed further.
The case I have described earlier is also not too hard, I think it is $x^y-x$ since $z = y-1$.
Would it be better to count all cases and subtract (like I did for the $z = y-1$ case) or should I try and count upwards?
To be clear, you are allowed to repeat letters as many times as you want so long as they never lie next to each other more than $z$ times.
Thanks for the help!
 [/INST] 
The following answer is based upon the Goulden-Jackson Cluster Method which provides a convenient technique to solve problems of this kind. We consider the set of words of length $y\geq 0$ built from an alphabet $$\mathcal{V}=\{A_1,A_2,\ldots A_x\}$$ and the set $B=\{A_1^{z+1},A_2^{z+1},\ldots,A_x^{z+1}\}$ of bad words each of length $z+1$, which are not allowed to be part of the words we are looking for. We derive a generating function $f(t)$ with the coefficient of $t^y$ being  the number of wanted words of length $y$.

According to the paper (p.7) the generating function $f(t)$  is
\begin{align*}
f(t)=\frac{1}{1-xt-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
with $x=|\mathcal{V}|$ the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[A_1^{z+1}])+\text{weight}(\mathcal{C}[A_2^{z+1}])
+\cdots+\text{weight}(\mathcal{C}[A_x^{z+1}])\tag{2}
\end{align*}

We calculate according to the paper for $1\leq j\leq x$:
\begin{align*}
\text{weight}(\mathcal{C}[A_j^{z+1}])&=-t^{z+1}-(t+t^2+\cdots+t^{z})\text{weight}(\mathcal{C}[A_j^{z+1}])\tag{3}\\
\end{align*}
where the long expression at the right-hand side of (3) accounts for overlappings of $A_{j}^{z+1}$ with itself. We obtain from (3):
\begin{align*}
\text{weight}(\mathcal{C}[A_j^{z+1}])&=-\frac{t^{z+1}}{1+t+\cdots t^{z}}\\
&=-\frac{t^{z+1}(1-t)}{1-t^{z+1}}\qquad\qquad 1\leq j \leq x\\
\end{align*}
It    follows from (1) - (3):
\begin{align*}
\color{blue}{f(t)}&=\frac{1}{1-xt-\text{weight}(\mathcal{C})}\\
&=\frac{1}{1-xt+x\frac{t^{z+1}(1-t)}{1-t^{z+1}}}\\
&\,\,\color{blue}{=\frac{1-t^{z+1}}{1-xt-(1-x)t^{z+1}}}\tag{4}
\end{align*}
and conclude the number of valid words of length $y\geq 0$ is the coefficient of $t^y$ in (4). We use the coefficient of operator $[t^y]$ to denote the coefficient of $y^n$ of a series. Applying standard techniques to extract the coefficient $[t^y]$ from $f(t)$ we obtain
\begin{align*}
[y^t]f(t)&=\sum_{k=0}^{\left\lfloor\frac{y}{z}\right\rfloor}\binom{y-zk}{k}(1-x)^kx^{y-(z+1)k}\\
&\qquad- \sum_{k=0}^{\left\lfloor\frac{y-z-1}{z}\right\rfloor}\binom{y-z-1-zk}{k}(1-x)^kx^{y-z-1-(z+1)k}\tag{5}
\end{align*}

Example: $x=2,y=3,z=2$
We look at OPs example where the alphabet $\mathcal{V}=\{A,B\}$ consists of two characters. Invalid words are those containing substrings which are elements from the set of $\{AAA,BBB\}$ of bad words. According to (4) the generating function is given as
\begin{align*}
f(t)&=\left.\frac{1-t^{z+1}}{1-xt-(1-x)t^{z+1}}\right|_{x=2,z=2}\\
&=\frac{1-t^3}{1-2t+t^3}\\
&=1 + 2 t + 4 t^2 + 6t^3 + \color{blue}{10} t^4 + 16 t^5\\
&\qquad + 26 t^6 + 42t^7 + 68 t^8 +\cdots\\
\end{align*}
The last line was calculated with some help of Wolfram Alpha.  Note, the coefficient $6$ of $t^{3}$ according to the six valid words stated by OP. The blue marked coefficient of  $t^4$ is $10$ and the $2^4-10=6$ invalid words are
\begin{align*}
&\rm{\color{blue}{aaa}a}&\rm{a\color{blue}{bbb}}\\
&\rm{\color{blue}{aaa}b}&\rm{b\color{blue}{bbb}}\\
&\rm{b\color{blue}{aaa}}&\rm{\color{blue}{bbb}a}\\
\end{align*}
Applying (5) we find
\begin{align*}
\color{blue}{[t^3]f(t)}&=\sum_{k=0}^1\binom{3-2k}{k}(-1)^k2^{3-3k}-\sum_{k=0}^0\binom{0-2k}{k}(-1)^k2^{0-3k}\\
&=\binom{3}{0}(-1)^02^3+\binom{1}{1}(-1)^12^0-\binom{0}{0}(-1)^02^0\\
&=8-1+1\\
&\,\,\color{blue}{=6}\\
\\
\color{blue}{[t^4]f(t)}&=\sum_{k=0}^2\binom{4-2k}{k}(-1)^k2^{4-3k}-\sum_{k=0}^0\binom{0-2k}{k}(-1)^k2^{1-2k}\\
&=\binom{4}{0}(-1)^02^4+\binom{2}{1}(-1)^12^1+\binom{0}{2}(-1)^22^{-2}-\binom{0}{0}(-1)^02^1\\
&=16-4+0-2\\
&\,\,\color{blue}{=10}
\end{align*}
in accordance with the results above.
</s>