Skip to main content
2 of 4
added link; added latex
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

Binary Sequences of Length 2n

I had posted an urn probability problem that didn't have good motivation. I'd like to try to explain the motivation here, and reintroduce the problem.

Consider binary sequences of length $2n$. Let's say we put a marker in such a sequence as soon as we see a total of $n$ 0's or $n$ 1's, reading left to right. For example, if $n=4$, then the sequence 00101011 would receive a marker thus: 001010|11. Now write down the bits to the right of the marker. In the case of our example, this would be 11. Do this for every binary sequence of legnth $2n$. We observe that we have written down $2n\binom{2n}{n}$ bits, half 0's and half 1's. It is possible to prove this observation using binomial coefficient identities, but I wonder whether there is a simple bijective proof.

The previous urn problem was an equivalent probabilistic formulation of the case $n=5$.