I have a table with $r$ rows of length $\ell$, with each cell containing a letter from an alphabet $A$ of length $a$. I'm trying to determine the expected number of distinct strings of length $k$ appearing from left to right along a row (strings cannot `loop round' or continue on the next row). I'm fairly certain that a closed form is not worth pursuing as different strings occur with different probabilities. For example, denoting by $p_J$ the probability that a string $J$ will occur on a given row, the expected number of strings is
$$ \sum_J 1-(1-p_J)^r $$
which seems very difficult to calculate.
Can we bound the above value to any extent?
