Entropy of the multinomial distribution In my work I've found myself in the position of needing to calculate the entropy of the multinomial distribution:
$$\text{Multinomial}({\bf x};\; n,{\bf p})$$
I imagine it would be too much to expect a closed-form formula for this value, but what is the current standard method for efficiently calculating/approximating the entropy of a multinomial distribution?
Also my situation is for small $n$, so asymptotic approximations probably aren't the best for me unless they converge extremely quickly.
 A: Ok so I guess I should have done a bit of experimentation before posting this question.  I just assumed that since the Wikipedia article for the multinomial distribution didn't mention entropy, and since I couldn't find anything about it on google, that it was very difficult to compute. 
Let
$${\bf X}\sim \text{Multinomial}(n,{\bf p})$$
The entropy for $\bf X$ is given by:
$$\text{H}({\bf X})=-\hspace{-4mm}\sum_{\substack{ {\bf x}\geq0\\\\\\ \sum_ix_i=n}}\frac{n!}{x_1!\cdots x_k!}p_1^{x_1}\cdots p_k^{x_k}\log\Big[\frac{n!}{x_1!\cdots x_k!}p_1^{x_1}\cdots p_k^{x_k}\Big].$$
Using the logarithm to break this up we obtain:
\begin{align}
\text{H}({\bf X}) &= -\log n! - \sum_{i=1}^k\log p_i\text{E}[X_i]+\sum_{i=1}^k\text{E}[\log X_i!]\notag\\
&=-\log n! - n\sum_{i=1}^kp_i\log p_i+\sum_{i=1}^k\text{E}[\log X_i!]\notag\\
&=-\log n! - n\sum_{i=1}^kp_i\log p_i+\sum_{i=1}^k\sum_{x_i=0}^n\binom{n}{x_i}p_i^{x_i}(1-p_i)^{n-x_i}\log x_i!.\notag
\end{align}
Thus we see that instead of summing over all distinct permutations of the partitions of $n$, which scales exponentially with both the size of $n$ and $k$, the derived form scales as $O((n+1)k)$, which is linear in both $n$ and $k$.
