# Probability of a contiguous sub-sequence with different elements

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 sub-sequence $\{s_i,\dots,s_{i+a-1}\}$, whose elements are all distinct? What if I look for a contiguous sub-sequence of, say $2a$ elements $\{s_i,\dots,s_{i+2a-1}\}$, 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.

Well, the first element can be chosen in $a$ ways, the next $a-1$ 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 $ab-a+1$ starting positions. Thus, the expected number of good sequences is $$\frac{a!(ab-a+1) (b!)^a}{(ab)!}.$$
• Nice but does it work for $a=b=2$? – Bjørn Kjos-Hanssen Oct 9 '14 at 3:55