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: 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$$
A: $$\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.
