optimality. This is expressed in information theoretic terms by the following theorem.

\[thm:Hdecomp\] For exchangeable sources, the order and the value are independent, and the sequence entropy $H((X_i)_{i=1}^n)$ can be decomposed into the value entropy $H(\{X_i\}_{i=1}^n)$ and the order entropy $H(J)$: $$\label{eq:Hdecomp}
H\left( (X_i)_{i=1}^n \right) = H\left( \{X_i\}_{i=1}^n \right) + H(J) \mbox{.}$$

Suppressing unnecessary subscripts, we can write $$\begin{aligned}
\label{eq:Hdecomp}
H((X)) & \stackrel{(a)}{=}  H((X)) + H(\{X\}) -  H((X)|J)
       \ = \                H(\{X\}) + I((X) \; ; \; J) \notag \\
       & =                  H(\{X\}) + H(J) - H(J|(X))
      \ \stackrel{(b)}{=} \ H(\{X\}) + H(J) \mbox{.} \notag\end{aligned}$$ Step (a) follows from noting that $H(\{X\}) = H((X)|J)$ for exchangeable sources, since all orderings are equiprobable and uninformative about the value. Step (b) follows from the fact $H(J|(X)) = 0$, since the sequence determines the order. The other steps are simple informational manipulations.

When we disregard order, we are just left with a multiset. Type classes—also known variously as histograms or empirical distributions in statistics and as rearrangement classes or Abelian classes in combinatorics—are complete, minimal sufficient statistic for multisets. For discrete-alphabet sources, types are convenient mathematical representations for multisets; several results for these sources will depend on counting numbers of type classes.

Despite 