 Number of empirical types

A possible empirical distribution corresponds to nonnegative integer counts $(n_1,\dots ,n_m)$ with sum $n$. Stars and bars therefore givesThe bound also follows by letting each count independently range from zero to $n$, which overcounts tuples whose sum is wrong. With the alphabet fixed, the count grows polynomially in $n$, whereas there are $m^n$ strings when $m\ge 2$. For binary symbols there are exactly $n+1$ profiles: the number of ones can be any integer from zero through $n$.

This reduces a rare-event calculation to a sum over profiles when the event depends only on counts. An event that depends on order may instead require counting the relevant subset inside each type class. A source with statistical dependence need not make strings of the same empirical distribution equiprobable; the memoryless assumption cannot simply be dropped.