Let $a$ and $b$ be two positive integers, and say $b\gg a$. Let $S$ be a random sequence with $ab$ elements, whose entries are all integers from $1$ to $a$, such that each number from $1$ to $a$ appears exactly $b$ times. What is the probability that $S$ contains a consecutive subsequence $\{s_i,\dots,s_{i+a1}\}$, whose elements are all distinct? What if I look for a contiguous subsequence of, say $2a$ elements $\{s_i,\dots,s_{i+2a1}\}$, such that each number $1$ to $a$ appears at least once? This seems like it should be easy, but I am having difficulty with the dependencies.
I don't know if this helps, but we can compute the expected number of such good sequences quite easily.
First: What is the number of good sequences starting at position 1?
Well, the first element can be chosen in $a$ ways, the next $a1$ and so on, so we get $a!$ such ways.
There are $(ab)!/(b!)^a$ words of length $ab$ in total (permute all letters, but for all instances of $b$ equal letters, we need to compensate). Thus, the expected number of good sequences at position 1 is $$ \frac{a! (b!)^a}{(ab)!}. $$ Now, there is nothing special about the first sequence, so we can just sum the above over all $aba+1$ starting positions. Thus, the expected number of good sequences is $$ \frac{a!(aba+1) (b!)^a}{(ab)!}. $$

$\begingroup$ Nice but does it work for $ a=b=2$? $\endgroup$ – Bjørn KjosHanssen Oct 9 '14 at 3:55

1$\begingroup$ Checking the calculations above is left as an exercise to the reader: it was late yesterday. $\endgroup$ – Per Alexandersson Oct 9 '14 at 5:52