1
$\begingroup$

I figured out that for any given $n$ the number of sequences of heads and tails that satisfy the condition that HH wasn't flipped consecutively until flips $n-1$ and $n$ is equal to the $(n-1)$th Fibonacci number. I found this by making a tree whose root was T on the $(n-2)$ flip and then I branched to each possible way to fill the $(n-3)$ slot and from those branches I branched to the possibilities for the $(n-4)$ slot, etc. It was neat to see the Fibonacci sequence pop up here, but I want to know how to find the result efficiently using a method from combinatorics.

$\endgroup$
2
$\begingroup$

Count the sequences that have no $HH$ at all in them. Such sequences of length $n+2$ are either of the form $\alpha T$ where $\alpha$ is an arbitrary such sequence of length $n+1$ or of the form $\beta TH$ where $\beta$ is an arbitrary such sequence of length $n$. Finally the sequences ending in a first occurance of $HH$ are (if $n\ge 3$) of the form $\gamma THH$ where $\gamma$ is of the form just described.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If I want flips n-1 and n to be H,H respectively, why would I consider sequences of lengths greater than n? Why wouldn't we only consider sequences of length n-2? $\endgroup$ – Acemanhattan Jan 15 '15 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.