# Expression for the size of type class, or multinomial coefficient.

The notations follow those in Cover&Thomas, "Elements of Information Theory", 2ed.

I saw from a paper that the size of type class $T(P)$ can be expressed as $|T(P)|=2^{nH(P)-\frac{|\mathcal{X}|-1}{2}\log n+O(1)}$. I could not understand how this equation comes out. Could you please help me with it? Thanks a lot.

For those not familiar with information theory or method of types, the above equation can be formulated as:

Assume $(x_1,x_2,...,x_m)$ conforms to multinomial distribution. Conduct $n$ iid experiments, then $\sum\limits_{i=1}^mx_i=n$ and $P=\{\frac{x_1}{n},\frac{x_2}{n},...,\frac{x_m}{n}\}$ forms a pmf. Prove that the multinomial coefficient $\left(\begin{array}{c}n\\x_1,x_2,\ldots,x_m\end{array}\right)=2^{nH(P)-\frac{m-1}{2}\log n+O(1)}$ where $H(P)$ is the entropy of the pmf $P$. Thanks a lot!

-
It seems that we can use Stirling's approximation $n!\approx\sqrt{2\pi n}(n/e)^n$. But this is only an approximation and a big-O term $O(\ldots(n))$ or something is needed for the equation to hold exactly. I don't know what form of $O(\ldots(n))$ is. Any comment is welcome! ... I have to go to bed now:-( –  Zhou Heng Mar 2 '13 at 16:11

Plug the Stirling's approximation (http://en.wikipedia.org/wiki/Stirling%27s_approximation): $n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1+O\left(\frac{1}{n}\right)\right)$ into the expression of the multinomial coefficient.