52 votes 52 votes 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 $0's$ as $1's.$ Combinatory gate1991 combinatory normal descriptive catalan-number + – Kathleen asked Sep 12, 2014 retagged May 16, 2018 by kenzou Kathleen 6.3k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply minal commented Nov 15, 2015 reply Follow Share sir , am not getting question... one side ,says no of 0 and 1 are equal then w and prefix ..not getting 0 votes 0 votes Arjun commented Nov 15, 2015 reply Follow Share it was a typo- the property must hold in every prefix of string- "100" is not allowed as for the prefix "1" the property is violated. 1 votes 1 votes rambo commented Aug 1, 2018 reply Follow Share Sir...what is meaning of "every prefix of w...." 1 votes 1 votes !KARAN commented Dec 1, 2018 i edited by !KARAN Dec 1, 2018 reply Follow Share There are $2n$ positions out of which we need to select only n for $0's$ which makes it $2nCn$. But why we are dividing it with $n+1$ that part is not clear and how do we know, how many strings are there in $2nCn$ which needs to be remove from counted strings. Just thinking this problem in the terms of TOC Is it possible to construct DFA for this or find a regular expression for it. As i have read one similar problem in TOC which has same wording for $\text{at least as many 0's as 1's }$. 3 votes 3 votes palashbehra5 commented Sep 17, 2021 reply Follow Share I don't think so a DFA is possible, extra memory will be required. If you manage to find a solution do let me know. 0 votes 0 votes Shivani Shukla commented Nov 17, 2022 reply Follow Share Can someone please explain me that how we come to know that we need to use Catalan number to find solutions of particular questions? As upto now I have seen that it is used to form the number of pairs for a particular sequence or in binary tree. 0 votes 0 votes Chandrabhan Vishwa 1 commented Feb 2 reply Follow Share here the meaning at least asmany 0's as1'snumber of zeros is equal or greater than number of 1 and string should start with 0000111,0011,00001,00011011 its best example is balance parenthesismeans string always start with 0 1 votes 1 votes Please log in or register to add a comment.
Best answer 37 votes 37 votes Answer to a is $\frac{^{2n}C_n}{(n+1)}$ which is the Catalan number. This is also equal to the number of possible combinations of balanced parenthesizes. See the $5^{\text{th}}$ proof here https://en.wikipedia.org/wiki/Catalan_number#Fifth_proof Arjun answered Apr 21, 2015 edited Dec 5, 2021 by Kiyoshi Arjun comment Share Follow See all 26 Comments See all 26 26 Comments reply Show 23 previous comments kiioo commented Nov 10, 2020 reply Follow Share @mrinmoy Did you get the answer for the (n+1) part? 0 votes 0 votes Shoto commented Dec 24, 2021 reply Follow Share @ankit3009 This question is same is balanced parantheses right? Considering 0 as closing braces and 1 as opening braces therefore answer is Catalan number. 2 votes 2 votes ankit3009 commented Dec 24, 2021 reply Follow Share Yes @adad20 it is same as balanced parenthesis. 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes Cn is the number of Dyck words[3] of length 2n. A Dyck word is a string consisting of nX's and n Y's such that no initial segment of the string has more Y's than X's. For example, the following are the Dyck words of length 6: XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY. Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cncounts the number of expressions containing n pairs of parentheses which are correctly matched: ((())) ()(()) ()()() (())() (()()) Cn is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating napplications of a binary operator). For n = 3, for example, we have the following five different parenthesizations of four factors: ((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd)) source :- https://en.m.wikipedia.org/wiki/Catalan_number Rishiryanemo answered Jan 16, 2020 Rishiryanemo comment Share Follow See all 0 reply Please log in or register to add a comment.