How many sequences of coin flips of length \(n\) do not contain \(HH\)? E.g. there are 5 for \(n = 3: TTT, TTH, THT, HTT, HTH\).

· · Web · 3 · 2 · 0

@alexdbolton this is one of those problems that seem much easier to brute force with a computer than to figure out by hand.

Spoilers for maths problem 

@alexdbolton just playing around with this, and I think the answer is: fibonacci sequence! There are 2 1-flip sequences, 3 2-flip sequences, 5 3-flip sequences and so on...

Spoilers for maths problem 

@alexdbolton quick proof: if there are t (n-1) filp sequences that end in a T and h (n-1) flip sequences that end H, then there are h+t n-flip sequences that end in a T and there are t n-flip sequences that end in a H. (since the only way to end in an H is to have a T in the penultimate slot.)

@alexdbolton Nice! I wasn't expecting that when I started off.

Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!