Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


$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!

share|cite|improve this question
You're double counting. TTH, for example, gets counted under in $i=1$, and under $i=2$. – ronno Oct 27 '12 at 18:56
up vote 2 down vote accepted

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


To finish simplifying the result, just use the formula for the sum of a finite geometric series.

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$?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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