Flipping a coin until 4 heads occur, or until flipped 7 times. How many combinations are possible?

Question: A coin is tossed until either 4 heads occur or until the coin has been tossed 7 times. How many heads/tails sequence are possible? For example, HTHTTHT, HHHH, THHTHH, and TTTTTTT are all sequences in the list of possible outcomes.

I think the answer will be 276, but am not sure if it's remotely close to being right. Thanks for any and all help!

A relatively short solution is the following: take all $2^7=128$ possible combinations obtainable with $7$ throws, and subtract all those containing $>4$ heads. In fact:

• no sequence containing $>4$ heads is possible based on the given rules;

• all sequences containing $< 4$ heads are valid;

• all sequences containing exactly $4$ heads are also valid (note that these have to be considered "truncated" if $4$ heads occur before the seventh throw, but this does not alter the number of possible sequences since we truncate only a final sequence of tails).

Therefore, the solution is given by $128- {7 \choose 5}-{7 \choose 6}-{7 \choose 7}$ $=128-21-7-1=99$ combinations.

Another solution, a bit longer, is the following. If no heads occur, we have ${7 \choose 0}=1$ combination. If one head occurs, we have ${7 \choose 1}=7$ combinations. If two or three heads occur, we have ${7 \choose 2}=21$ and ${7 \choose 3}=35$ combinations, respectively.

If four heads occur, we have:

• ${4 \choose 0}=1$ combination if no tails occur;

• ${4 \choose 1}=4$ combinations if one tail occurs (if four heads and one tail occur, necessarily the last of the five throw has to be a head: so we can focus on the first four throws);

• ${5 \choose 2}=10$ combinations if two tails occur (as above, if four heads and two tails occur, necessarily the last throw has to be a head: so we can focus on the first five throws);

• similarly, we get that there are ${6 \choose 3}=20$ combinations if three tails occur.

Summing all combinations, we get again

$$1+7+21+35 \\ +1+4+10+20=99$$

$$\sum_{k=4}^7 \binom{k-1}{3} + \sum_{k=0}^3 \binom{7}{k} = 99.$$ The first sum counts the cases where the fourth head occurs on the $k^{\rm th}$ toss, for $k = 4, 5, 6, 7$, and the second sum counts the cases where $k$ heads are obtained in $7$ coin tosses, for $k = 0, 1, 2, 3$. Since these are all mutually exclusive outcomes (no double-counting), the enumeration is complete.