Balanced binary sequence with odd length.

38 Views Asked by At

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):

  1. Create a balanced binary sequence with length of 2n. //All possible options = $C(n)$
  2. 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.