<s>[INST] Number of distinct sequences of length 10, containing at least 5 consecutive As or at least 5 consecutive Bs Im stuck on this question, asking for the number of distinct sequences of length 10, which contain at least 5 consecutive As or 5 consecutive Bs (for example ABABBBBBBA should be counted, as should ABBBBAAAAA). I know there's 1024 possible strings, but I'm unsure how to do the calculation without explicitly writing code to sum all the posibilites. How do I go about approaching this question without writing down every possibility?
 [/INST] The generating function for the number of strings with at most $4$ As in a row and $4$ Bs in a row is
$$
\begin{align}
g(x)
&=\overbrace{\ \frac{1-x^5}{1-x}\ }^\text{$0$-$4$ A}\overbrace{\frac{1\vphantom{x^5}}{1-\underbrace{\frac{x-x^5}{1-x}}_\text{$1$-$4$ B}\underbrace{\frac{x-x^5}{1-x}}_\text{$1$-$4$ A}}}^\text{$0$+}\overbrace{\ \frac{1-x^5}{1-x}\ }^\text{$0$-$4$ B}\\
&=\frac{1-x^5}{1-2x+x^5}\\
&=1+2x+4x^2+8x^3+16x^4+30x^5+\sum_{n=6}^\infty a_nx^n
\end{align}
$$
where $a_n=2a_{n-1}-a_{n-5}$ for $n\ge6$. This recurrence follows from the $1-2x+x^5$ in the denominator. Computing several more terms, we get
$$
\sum_{n=6}^{10} a_nx^n=58x^6+112x^7+216x^8+416x^9+802x^{10}
$$
Since there are a total of $2^{10}=1024$ strings of $10$ As or Bs, we get that there are $1024-802=\bbox[5px,border:2px solid #C0A000]{222}$ strings of $10$ As or Bs with at least $5$ As in a row or $5$ Bs in a row.
</s>