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

This may be a very simple question. This relates to a stackoverflow question.

enter image description here

So my question is, we have a coin toss frequency matrix, showing all the possible combinations of Heads coming up in 36 throws:

On the first occasion A [Heads] can occur only 'never' (0) or 'always' (1). On the second occasion the frequencies are 0,1/2, or 1; on the third 0, 1/3, 2/3, or 1 etc, etc.

In the posted graph that number is 68,719,476,736. I am reproducing the plot but ending at 25 rather than 36, so I would like to calculate the appropriate figure for my situation.

(I have tried 36^36 and 36choose36, but those are just my stabs in the dark.) Update: Perhaps Stirling's approximation has something to do with it?

share|cite|improve this question
I'm not clear on what number you are trying to compute; if you've made $n$ tosses, then the possible number of heads in those $n$ tosses are $0$, $\frac{1}{n}$, $\frac{2}{n},\ldots,\frac{n-1}{n}$, or $\frac{n}{n}$. Are you asking how to compute how often each of those occurs, e.g., in how many of the $2^{36}$ possible sequences of coin tosses you have that exactly $\frac{17}{36}$ of the entries are heads? – Arturo Magidin May 7 '11 at 21:10
Perhaps somebody with more points can uncomment the plot that I wanted to include, as it explains the situation. – Frank_Zafka May 7 '11 at 21:53
I'm still having a hard time, but it seems like you are interested only in the total number; in that case, the point $\frac{k}{n}$, corresponding to $k$ heads in a set of $n$ tosses, will have two of what you term "children", namely $\frac{k}{n+1}$ and $\frac{k+1}{n+1}$. For $n$ tosses, you have $n+1$ possible outcomes, as described above. – Arturo Magidin May 7 '11 at 22:08
@arturo-magidin If you look at the plot (it is in the post, commented out because I don't have enough mod points to post it), it should be very easy to see what I want. I am not a mathematician, so I will have to think about it, but essentially, Prof. Boring gives a figure for 36 trials, and I want the number for 25 trials. – Frank_Zafka May 7 '11 at 22:12
@RSould: If the figure for 36 trials is 68,719,476,736 (which is $2^{36}$, the number of sequences of heads and tails, where order matters), then the number of 25 trials is $2^{25}=33,554,432$, and in general, the number for $n$ trials ($n$ tosses) is $2^n$. – Arturo Magidin May 8 '11 at 2:01
up vote 1 down vote accepted

The number $68,719,476,736=2^{36}$ is the number of strings of length 36 made up of T and H. This contradicts your listing of four results (0,1/3,2/3,1) for three tosses as this ignores different orders and just counts the total number of H's. Under this count, there are only 37 results for 36 tosses.

share|cite|improve this answer
Well the numbers match, so I can progress with my work. I will have to think about it all though. Many thanks for the help. – Frank_Zafka May 7 '11 at 22:48

There are $2^n$ possible sequences of heads and tails (where order matters). Of these, in exactly $\binom{n}{k}$ of them you have $k$ heads (pick in which positions you have heads, the remaining positions will be tails).

There are, however, only $n+1$ possible total outcomes with $n$ coin tosses, if all you care about is how many heads and how many tails you got; namely, you can have $0$ heads, $1$ head, $2$ heads, $3$ heads, and so on until you get to $n$ heads.

If you don't care about order and are only interested in the possible ratio of heads to tosses, the possibilities are $0$, $\frac{1}{n}$, $\frac{2}{n}$, $\frac{3}{n},\ldots,\frac{n-1}{n}$, and $1$.

If you are interested in order, and want to know the probability that a sequence of $n$ tosses will result in exactly $k$ heads, that number is $$\frac{\binom{n}{k}}{2^n}.$$ So the probabilities would be:

  • Of getting no heads, $\displaystyle\frac{1}{2^n}$.
  • Of getting exactly one head, $\displaystyle \frac{\binom{n}{1}}{2^n} = \frac{n}{2^n}$.
  • Of getting exactly two heads $\displaystyle\frac{\binom{n}{2}}{2^n} = \frac{n(n-1)}{2^{n+1}}$.
  • Of getting exactly three heads, $\displaystyle\frac{\binom{n}{3}}{2^n} = \frac{n(n-1)(n-2)}{2^n 3!}$.

etc. The odds of getting exactly $k$ heads are the same as the odds of getting exactly $n-k$ heads.

It is the latter that I would consider a "frequency", as $\binom{n}{k}/2^n$ is how frequently you would expect to get a set of $n$ tosses that have exactly $k$ heads in it.

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.