Type class ($T_n(q)$)

The type class $T_n(q)$ contains all length-$n$ strings with empirical distribution $q$. Each $nq(a)$ must be a nonnegative integer and the counts must sum to $n$; otherwise the class is empty. Distinct type classes partition ${\mathcal{A}}^n$: every string belongs to exactly one class.

For four binary symbols there are five type classes, indexed by the number $k$ of ones. Their cardinalities are $1,4,6,4,1$, which sum to $16=2^4$. The balanced class contains exactly $0011,0101,0110,1001,1010,1100$. These are six different strings, not six different empirical distributions.

Write $n_a=nq(a)$. Arranging $n_a$ copies of each symbol gives the multinomial coefficientThe division by the factorials removes permutations among identical copies. In the balanced four-symbol example, $|T_4(q)|=4!/(2!2!)=6$. For binary symbols this becomes the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; for three symbols with counts $(2,1,1)$, the class contains $4!/(2!1!1!)=12$ strings.

If a decoder already knows the length, alphabet and empirical distribution, it only needs to distinguish $|T_n(q)|$ possible strings. A fixed-length index therefore needs $\lceil {\log }_2|T_n(q)|\rceil$ bits. List the six balanced four-symbol strings in increasing lexicographic order and number them $0$ through $5$. A three-bit index identifies any one of them, whereas writing the original binary string directly takes four bits.

Knowing the empirical distribution is essential to that calculation. If it must also be sent, a simple fixed-length description of which of the five classes was used costs another $\lceil {\log }_{2}5\rceil =3$ bits. That naive balanced-string message totals six bits and is longer than the raw four-bit string. The example demonstrates the benefit of shared constraints, rather than a free lossless source coding scheme for every input. For long strings over a fixed alphabet, the overhead for identifying a class grows only logarithmically with length, while the information entropy of its frequency profile controls the leading cost within the class.