parent. Then $$\Pr[K_i = k_i] = \binom{n}{k_1,k_2,\ldots,k_{|\mathcal{X}|}} \prod_{i=1}^{|\mathcal{X}|}p_i^{k_i}, \qquad \mbox{for $i = 1,\ldots, |\mathcal{X}|$,}$$ for any type $(k_1,k_2,\ldots,k_{\left|\mathcal{X}\right|})$ of non-negative integers with sum $n$.

The simplest case of a binary source ($|\mathcal{X}| = 2$) gives $K_1 \sim \binomial(n,p)$ and $K_2 = n - K_1$, where $p = \Pr[X_i = 1]$. Then since $K_2$ is a deterministic function of $K_1$, we have the simplification $H(K_1,K_2) = H(K_1)$. Now we have $$H(\{X_i\}_{i=1}^n)
   = H(K_1)
   = \Half \log(2\pi e p(1-p) n) + \sum_{k=1}^\infty a_k n^{-k}
\label{eq:binomialEntropy}$$ for some constants $a_1,\,a_2,\,\ldots$. The leading term can be obtained with the de Moivre approximation of a binomial random variable with a Gaussian random variable [@deMoivre1756 pp. 243–259]; the full expansion requires more sophisticated techniques [@JacquetS1999].

To emphasize the dependence on $n$, note that the rate in (\[eq:binomialEntropy\]) is $\Half \log n + c + o(1)$, where $c$ is some constant. We will now see that $O(\log n)$ lossless coding rate extends to all finite-alphabet multiset sources.

Let $|\mathcal{X}|$ be finite. Then $H(\{X_i\}_{i=1}^n) = O(\log n)$. \[thm:HRzero\]

Denote the alphabet of distinct types by $\mathcal{K}(\mathcal{X},n)$. By simple combinatorics [@Csiszar1998], $$|\mathcal{K}(\mathcal{X},n)| = \binom{n + |\mathcal{X}| - 1}{|\mathcal{X}| - 1} \le (n+1)^{|\mathcal{X}|} \mbox{.}
\label{eq:NofTypes}$$ Recalling the equality (\[eq:multinomialEquiv\]), the 