0 votes 0 votes 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? Combinatory discrete-mathematics combinatory + – noxevolution asked Jul 1, 2018 noxevolution 722 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Soumya29 commented Jul 2, 2018 reply Follow Share 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. 1 votes 1 votes noxevolution commented Jul 2, 2018 reply Follow Share 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 votes 0 votes Soumya29 commented Jul 3, 2018 reply Follow Share 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 votes 1 votes Please log in or register to add a comment.