Consider the set of all $(o+z)$-sized binary strings that contains $o$ 1's and $z$ zeros (and we assume $o>z$).
Obviously, there are ${o + z \choose z}$ such sequences.
I was wondering how many of them contain a prefix in which there number of zeros which is greater than or equal to the number of ones.
E.g., 10011 is counted, while 11010 is not.
In the case of $o=3, z=2$, the answer should be 8, as we have {$00111,01011,01101,01110,10011,10101,10110,11001$}. The sequences which should not be counted are $11010$ and $11100$.
How can we compute the number of such sequences?
This probably is related to Catalan numbers, but I don't see the direct connection.
Thank you very much !
Best Answer
This is a variant of Bertrand’s ballot problem. If you give the $\binom{o+z}z$ strings the uniform distribution and pick one at random, Bertrand’s ballot theorem says that the probability that it will not have such a prefix is
$$\frac{o-z}{o+z}\;.$$
Thus, the number of sequences with such a prefix is
$$\begin{align*} \left(1-\frac{o-z}{o+z}\right)\binom{o+z}z&=\frac{2z}{o+z}\binom{o+z}z\\ &=2\binom{o+z-1}{z-1}\\ &=2\binom{o+z-1}o\;. \end{align*}\tag{1}$$
As a partial check, note that if $o=z+1$, the ‘bad’ strings are those that have a $1$ followed by a string of length $2z$ that corresponds to a Dyck path, so there are $C_z$ such strings and therefore
$$\begin{align*} \binom{o+z}z-C_z&=\binom{2z+1}z-\frac1{z+1}\binom{2z}z\\ &=\binom{2z+1}z-\frac1{2z+1}\binom{2z+1}z\\ &=\frac{2z}{2z+1}\binom{2z+1}z\\ &=2\binom{2z}{z-1}\\ &=2\binom{o+z-1}{z-1}\;, \end{align*}$$
as given by $(1)$.