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?
 A: Consider the case where there are exactly $5$ consecutive A's. The possible arranegments are
\begin{align}
&AAAAABCCCC\\
&BAAAAABCCC\\
&CBAAAAABCC\\
&CCBAAAAABC\\
&CCCBAAAAAB\\
&CCCCBAAAAA
\end{align}
where the character $C$ can be either an $A$ or a $B$. Thus there are $2(2^4 + 2^3 + 2^3) = 64$ possible strings with $5$ consecutive A's. You can repeat the same procedure for $6,7,8,9$ and $10$ consecutive A's to get a count for the total number of strings with at least $5$ consecutive A's. Naturally, this is also the total number of strings with at least $5$ consecutive B's. Adding these together and subtracting $2$ will give the final answer. It is necessary to subtract $2$ since we have counted the arrangements $AAAAABBBBB$ and $BBBBBAAAAA$ each twice and thus have overcounted by $2$. The total after subtracting $2$ is $222$.
A: Limit yourself to $AAAAA$.
Either the sequence starts with $AAAAA$, and we have 32 more options.
Or the sequence is preceeded by a $B$. Then we have 4 positions left, that can be filled randomly $2^4$, and both to the left and right (5).
Add: $32+5*16$, multiply by two: $224$
Only case I'm not sure of is $BBBBBAAAAA$, I may have double counting there.
** indeed, double counted both $BBBBBAAAAA$ and $AAAAABBBBB$, subtract 2.
Validated with a small computer program: result 222 is correct
A: 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.
