# Counting coin tosses

Here's a question I got as a homework assignment:

A coin is tossed $k$ times. At some point the result was $T$, and then later on it was $H$. What are the number of possible permutations?

So, this is what I came up with:

$$\sum_{i=1}^{k-1}(i-1)(k-i-1)$$

$i$ represents the point where before it there was at least one $T$, and after it there was at least one $H$. $i$ can be in $k-1$ different index points, and then once we determine $i$ the are $i-1$ unknown elements to the left of it, and $k-i-1$ unknown elements to the right of it.

Am I right? Thanks!

-
You're double counting. TTH, for example, gets counted under in $i=1$, and under $i=2$. – ronno Oct 27 '12 at 18:56

You’re thinking in a productive direction, but your counting is way off. First, you have to be a bit more careful in picking $i$; you should specify that it’s the number of the first T. The $i-1$ tosses before the first T must all be H, so there’s only one way that they can turn out. The $k-i$ tosses after the first T are another story: they can be anything except all T’s. There are $2^{k-i}$ possible strings of $k-i$ heads or tails, and only one of them is ruled out, so there are $2^{k-i}-1$ possibilities for the $k-i$ tosses after the first T. That is, there are $2^{k-i}-1$ sequences of $k$ coin tosses that have their first T’s on the $i$-th toss and have at least one H after that. The correct answer is therefore $$\sum_{i=1}^{k-1}\left(2^{k-i}-1\right)\;.$$
This can be simplified if you substitute $j=k-i$: then $j$ runs between $1$ (when $i=k-1$) and $k-1$ (when $i=1$), so
$$\sum_{i=1}^{k-1}\left(2^{k-i}-1\right)=\sum_{j=1}^{k-1}\left(2^j-1\right)=\sum_{j=1}^{k-1}2^j-\sum_{j=1}^{k-1}1=\sum_{j=1}^{k-1}2^j-(k-1)\;.$$
By the way, there is a completely different way of analyzing the problem that leads to the final result a bit faster. There are $2^k$ possible outcomes when you toss a coin $k$ times. Which of them do not have the property that there is at least one T and at least one H after the first T? Obviously a string of $k$ heads, but there are others. In fact, these ‘bad’ strings are precisely the strings that consisting of $i$ heads followed by $k-i$ tails for $i=0,\dots,k$; how many bad strings are there, then, to be subtracted from $2^k$?