I am facing an equal problem to this but I can't seem to have an algorithm that would allow me to count it.
The problem:
Let X(n) be the set of all possible balanced binary sequences, where 0's appear n+1 times and 1's appear n times, which means: $\forall{y\in X(n),} y.length = 2n+1$. What's the cardinality of X(n)?
Now I tried using the following algorithm to construct all of the elements in X(n):
- Create a balanced binary sequence with length of 2n. //All possible options = $C(n)$
- Choose a place either in the start/end of the sequence or between it's elements. //Which means = $\binom{n+1}{1}$ options.
Using the rule of product we will get: $|X(n)| = C(n)\times \binom{n+1}{1}$.
But that's wrong since I'm not taking into account repetitions, e.g.: $$n = 2; <001x1, <0x101>$$ the $x$ representing the additional 0 I would insert in step 2. As you see, the outcome is two identical sequences that are being counted twice.
Thank you for your time.