I have a question regarding Catalan Number. The question is as follows,
Find the number of binary strings $w$ of length $2n$ with an equal number of $1’$s and $0’$s and the property that every prefix of $w$ has at least as many as $0’$s as $1’$s.
Now I know the answer for this question is $\frac{1}{n+1}\binom{2n}{n}.$ I wanted to know how this question relates to Catalan number?
I know this interpretation of lattice paths, But my question is how is this generalization can be used for this question?
To find the ways without touching the diagonal is =
$\binom{2n}{n} - \binom{2n}{n-1},$ where $\binom{2n}{n-1}$ is the number of violating paths.
so to find the answer for the sequence question we have to take all the length $2n$ strings with an equal number of $1’$s and $0’$s which is $\binom{2n}{n}.$ But the answer is $\binom{2n}{n} - \binom{2n}{n-1}.$ We know for the lattice path problem that $\binom{2n}{n-1}$ is the number of violating paths, but what is this $\binom{2n}{n-1}$ for this particular question?
It the number of "violating words," the strings with an equal number of $0's$ and $1'$s where some prefix has more $1'$s than $0'$s. Interpret $0$ as a move up and $1$ as a move to the right to see the equivalence with the lattice path problem.