How many strings of $8$ Hs and $8$ Ts are there such that there are at most $2$ consecutive Hs? How many strings of 8 Hs and 8 Ts are there such that there are at most 2 consecutive Hs?
I don't really understand how to approach this question. What would be the quickest way to solve it?
Thanks in advance.
EDIT: An example of one such sequence would be (because of confusion) $$\text{HHTHHTHHTHHTTTTT}$$
 A: This answer is under the interpretation that we want to count sequences avoiding the pattern HHH.
Hint: Every such arrangement corresponds to an equation $a_0 + \cdots + a_8 = 8$ in which $a_i \in \{0,1,2\}$. So you are looking for the coefficient of $x^8$ in $(1+x+x^2)^9$, which is 2907. Without using a computer, We know that the solutions are of the forms
$$(2^0,1^8,0^1),(2^1,1^6,0^2),(2^2,1^4,0^3),(2^3,1^2,0^4),(2^4,1^0,0^5), $$
and so the total number is
$$
\binom{9}{0,8,1} + \binom{9}{1,6,2} + \binom{9}{2,4,3} + \binom{9}{3,2,4} + \binom{9}{4,0,5} = \\
9 + 252 + 1260 + 1260 + 126 = 2907.
$$
A: If we want to count the number of sequences that do not contain HHH,
we can arrange the T's in a row and let $x_i$ be the number of H's in gap i for $1\le i\le 9$.
Then $x_1+\cdots+x_9=8$ with $0\le x_i\le2$ for each i,
so if we let $A_i$ be the set of solutions with $x_i\ge3$ for $1\le i\le9$ and let S be the set of all solutions,
using Inclusion-Exclusion we get that
the number of integral solutions is given by 
$\displaystyle\left|A_1^{c}\cap\cdots\cap A_9^{c}\right|=|S|-\sum_{i}|A_{i}|+\sum_{i<j}|A_i\cap A_j|-\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots$
${\hspace .75 in}=\displaystyle\binom{16}{8}-\binom{9}{1}\binom{13}{8}+\binom{9}{2}\binom{10}{8}=2907$.
A: I hate to add a third answer, but since the other two disagree, I guess I will.
Step 1:  Say you have $h$ "heads-clumps" and $t$ tails; how many sequences can you form with no two head-clumps contiguous?  Let's call this $H(h,t)$.  We can evaluate that by breaking it into two cases:  A tail at the last spot, or a head-clump at the last spot.  
If a tail is in the last spot, then we can tie one tail at the end of  each head-clump  and this will give $t-h$ remaining tails, so the number of arrangements is $\binom{t-h+h}{h}=\binom{t}{h}$.
If a head-clump is in the last spot, then we can look at the rest, and say that we have $h-1$ head-clumps and $t$ tails with the last spot forced to be a tail.  The  number of such arrangements is $\binom{t}{h-1}$.
Thus 
$$ H(t,h) = \binom{t}{h}+\binom{t}{h-1} = \binom{t+1}{h}$$
Step 2:  If we allow up to 2 consecutive heads in a head-clump, then we will have $t=8$ and either 4, 5, 6, 7, or 8 head-clumps.  But if we have $c$ head-clumps of length 2,, we will also have $8-2c$ single heads, or a total of $8-c$ head-clumps.
An here is a key point:  We can distinguish between placements of those $c$ length 2 clumps among those $8-c$ spots in $\binom{8-c}{c}$ ways.  So for example, the number of arrangements with 2 head-clumps of length 2 (thus 6 total head-clumps) will be 
$$
\binom{6}{2} \binom{9}{6}
$$
Step 3: add them up.  The answer will be
$$
\sum_{c=0}^{4} \binom{8-c}{c}\binom{9}{8-c}
$$
This sort of sum canbe done using techniques in Concrete Mathematics by Knuth et. al., but in this specific case we have
$$
\begin{array}{c}
\binom{8}{0}\binom{9}{8} + \binom{7}{1}\binom{9}{7} +
\binom{6}{2}\binom{9}{6} + \binom{5}{3}\binom{9}{5} +
\binom{4}{4}\binom{9}{4} \\
= 1\cdot 9 + 7\cdot 36 + 15\cdot 84 + 10 \cdot 126 + 1\cdot 126 = 2907
\end{array}
$$
