# Calculate number of sequences in frequency matrix

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

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?

-
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

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.

-
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.

-