of the multiset and the dictionary. Consider the rate requirements of these two parts separately. First, let us bound the rate that is required to represent the pattern of the multiset (the type of the pattern). We can make use of the fact that there are $2^{n-1}$ types of patterns. This enumeration follows because the types are sequences of positive integers that sum to $n$. These can appear in any order, thus we are counting ordered partitions. It is well known that there are $2^{n-1}$ ordered partitions, which can be seen as determining arrangements of $n-1$ possible separations of $n$ places. Thus the rate requirement for an enumerative universal scheme representing the type of the pattern is $n-1$ bits.

Now to determine the rate requirement of the dictionary given the type of pattern. If the underlying distribution were known, we saw in Theorem \[thm:coincide\] that $H(\Delta | \{\Psi_i\}_{i=1}^n)$ is $o(n)$. It was shown in [@OrlitskySZ2004] that there is an $O(\sqrt{n})$ upper bound on the pattern redundancy, independent of $|\mathcal{X}|$. Since this is sublinear, the asymptotic per-letter redundancy in coding a class of sequences $(X_i)_{i=1}^{n}$ from a countable alphabet coincides with the asymptotic per-letter redundancy in coding the dictionary given the 