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?
 A: 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.
A: 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. 
