Of all possible combinations of x coin flips, how many combinations have two heads in a row? How many have exactly a head then tails in a row?

Question

I have this question for a practice problem set and I am trying to figure out a way to solve this logically. It is simple to solve iteratively through code, but I am having trouble deriving a formula to solve this.

I know that there are $2^x$ possible combinations based on x coin flips, but I can't figure out a method to extract all combinations that contain either an HH or HT.

Any thoughts? Appreciate the help.

Answer 1

Applying stars and bars it can be found that:

$$2^x-\sum_{0\leq k\leq\frac12x+\frac12}\binom{x+1-k}k$$combinations will contain substring "HH".

Unfortunately I cannot find a closed form for $\sum_{0\leq k\leq\frac12x+\frac12}\binom{x+1-k}k$ which of course is the number of combinations that do not contain substring "HH".

---

The case of finding the same for substring "HT" is less difficult.

If e.g. $x=4$ then the following $4+1=5$ combinations do not contain substring "HT":

• HHHH
• THHH
• TTHH
• TTTH
• TTTT

If writing from left to right the first "H" has been placed then only other "H"-s can follow.

This gives $$2^x-x-1$$possible combinations that contain substring "HT".

Answer 2

drhab has already given you good answers to both questions, but here is an alternate approach for the HH case.

Consider the complementary question: How many sequences of $x$ coin flips do not contain HH? Let's say that number is $a_x$. It's easy to see by trying all the possible cases that $a_1 = 2$ and $a_2 = 3$. Now suppose $x> 2$, and suppose we have a sequence of $x+1$ flips with no HH. Consider the final flip in the sequence; it might be either H or T. If the final flip is a T, then the first $x$ flips can be any sequence not containing HH, which can be done in $a_x$ ways. If the final flip is H, then the first $x$ flips must end in T, preceded by any $x-1$ flips without an HH, so this can be done in $a_{x-1}$ ways. Therefore $$a_{x+1} = a_x + a_{x-1}$$ for $x > 2$. This is exactly the recurrence defining the Fibonacci Numbers, but with the initial conditions shifted by two; so $a_x = F_{x+2}$, where $F_x$ is the x-th Fibonacci number.

The answer to the original problem, how many sequences contain at least one HH, is then $$2^x - F_{x+2}$$ If you need a quick way to calculate $F_x$, it is known that $F_x$ is the nearest integer to $\phi^x/\sqrt{5}$, where $\phi = (1+\sqrt{5})/2$.