How many binary strings with size $2n$ and satisfies the restrictions that 1)Total occurences of 1 equals to that of 0, 2) in any substring that begin with the first character of the string, there are no less occurrences of $1$ than $0$, are possible?

For example, when $n=1$, the only possible string is $(10)$.

When $n=2$, possible strings are $(1100),(1010)$

When $n=3$, possible strings are $(111000),(110100),(110010),(101100),(101010)$

And I did enumerate through all cases for $n=4$, but didn't find a clear pattern...

  • 1
    $\begingroup$ Why isn't $11$ also a possibility when $n=1?$ $\endgroup$
    – saulspatz
    Mar 29 '18 at 2:02
  • $\begingroup$ Sorry, I forgot another restriction, just added $\endgroup$
    – Macrophage
    Mar 29 '18 at 2:04
  • $\begingroup$ Makes a lot more sense now, thanks. $\endgroup$
    – saulspatz
    Mar 29 '18 at 2:06
  • 5
    $\begingroup$ Is this what you are looking for? $\endgroup$
    – N. Shales
    Mar 29 '18 at 2:19
  • 2
    $\begingroup$ Since you figured out that the answer is 14 when $n=4,$ here's a useful trick. Go to OEIS and enter 1,2,5,14 in the search box. $\endgroup$
    – saulspatz
    Mar 29 '18 at 2:28

Thanks for the helpful comments to the original problem. The number of possible strings can be described by the Calatan numbers: $1, 1, 2, 5, 14, 42, 132...$.

The following is what I found on OEIS:

Number of sequences consisting of n 'x' letters and n 'y' letters such that (counting from the left) the 'x' count >= 'y' count. For example, for n=3 we have xxxyyy, xxyxyy, xxyyxy, xyxxyy and xyxyxy. - Jon Perry, Nov 16 2012

Actually the same stuff as my problem statement!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.