68 views

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 2nCn/(n+1). I wanted to know how this question relates to Catalan number?

| 68 views
+1

Check this if it helps -https://gateoverflow.in/214618/counting?show=214964#a214964
Just replace open parenthesis or right steps with $0's$ and closed parenthesis or left steps with $1's$ in the given answer.

0
Hello Thank you for commenting......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 = 2nCn - 2nCn-1 where 2nCn-1 is the violating paths right??

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 = 2nCn. But the answer is = 2nCn - 2nCn-1. we know for the lattice path problem that (2nCn-1) is the no of violating paths. but what is this (2nCn-1) for this particular question??
0
Here $\binom{2n}{n-1}$ includes those strings which have more no. of $1's$ than $0's$ in any of their prefix.
For ex. - 111000, 100110 etc.

1
2