= Number of empirical types
{title2=$\binom{n+m-1}{m-1}$}
A possible <empirical distribution> corresponds to nonnegative <integer> counts $(n_1,\ldots,n_m)$ with sum $n$. <Stars and bars> therefore gives
$$
\#\{\text{length-}n\text{ types}\}=\binom{n+m-1}{m-1}\leq(n+1)^m.
$$
The 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\geq2$. 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.
Back to article page
