All possibilities of a binary string of certain length with restriction

179 Views Asked by At

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

There are 1 best solutions below

0
On BEST ANSWER

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!