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