Decision Tree Coin Toss

Large decision tree problem.

I have a problem where I think I need to use a decision tree. A coin is being flipped. How many ways can a coin be tossed 1010 times without having 55 heads in a row?

We know 210=10242^{10} = 1024. So there will be total possibilities of coin tosses. Is there a way to do this problem without relying on a decision tree?




“…tossed 10 times without having 5 heads in a row” Exact five heads in a row or can it be even more ?
– callculus
Oct 20 at 20:23



Can’t be more than that.
– brrnrr_47
Oct 20 at 20:26



Can it be HHHHHTTTTHHHHHHTTTTH ? I mean the 5 heads in a row.
– callculus
Oct 20 at 20:27



Yeah, assuming we’re given the problem exactly as it was originally worded, I would assume that we are not to count HHHHHHTTHH, since it does in fact include five heads in a row. Conventionally, the sixth consecutive head doesn’t put it back into consideration.
– Brian Tung
Oct 20 at 20:43


1 Answer


We will try to find how many way that have at least 5 consecutive heads.

We’ll first decide where the sequence begin (6 possibilities). The toss immediatly before need, if any, to be tail the rest can be anyting.

If the sequence start with the first toss
(1)5×25=32\left(1\right)^5 \times 2^5 = 32
If the sequence start at the nthn^{th} toss (1