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.4k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments 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 Arjun commented Apr 22, 2015 reply Follow Share The "prefix" condition is not there. 0 votes 0 votes Akash Kanase commented Nov 25, 2015 reply Follow Share Not able to understand that proof, can you explain , how "number of possible combinations of balanced parenthesizes. " == This problem in easy words ? 0 votes 0 votes Praveen Saini commented Nov 25, 2015 reply Follow Share balanced parenthesis mean equal no of left parenthesis, ( and ) , right parenthesis and ) cannot more than ( in any "prefix" . means strings like ) , )), ()) , (())) ,()))( are not allowed. strings will be as (),()(), ((())),((()()())) and so on . in above problem ( means 0 and ) means 1. 69 votes 69 votes Akash Kanase commented Nov 25, 2015 reply Follow Share Thanks got it :) 0 votes 0 votes Puja Mishra commented Sep 8, 2017 reply Follow Share r u considering even or odd length prefix @praveen sir ?? i am little confused ... 0 votes 0 votes Xylene commented Sep 8, 2017 reply Follow Share @Puja Mishra, The condition in the question will satisfy for any valid prefix (not only of even or odd length) of w as long as w is balanced. You can check it with any valid w. 0 votes 0 votes Puja Mishra commented Sep 8, 2017 reply Follow Share cant i say that it is referring even length prefixes ...?? 0 votes 0 votes Xylene commented Sep 8, 2017 reply Follow Share Why only even length ? Consider ((())), here one of the prefix is ((( or 0's and no of zeroes greater than 1's. 1 votes 1 votes Puja Mishra commented Sep 8, 2017 reply Follow Share bt the question states that the property that every prefix of ww has at least as many 0′s0′s as 1′s. then is it valid?? 2 votes 2 votes srestha commented Sep 9, 2017 reply Follow Share at least as many as 0's as 1's means 01 ,0011,00011,000011 are valid string but 011,10,11 are not valid string 16 votes 16 votes Puja Mishra commented Sep 10, 2017 reply Follow Share Thank u very much ... i hav to read the question more minutely ... 1 votes 1 votes bhuv commented Oct 11, 2017 reply Follow Share 00011,000011 these are not valid string @srestha as they don't satisfy the string property for the equal number of 0's & 1's. "at least as many as 0's as 1's" property is for prefixes of the obtained string. 6 votes 6 votes Mk Utkarsh commented Feb 21, 2018 reply Follow Share bhuv so the question requirement is 1) even length string 2) equal number of 0's and 1's 3) balanced parenthesis 0 is ( and 1 is ) am i right? 1 votes 1 votes bhuv commented Feb 22, 2018 reply Follow Share @Mk Utkarsh first two conditions are on string 'w' and "at least as many as 0's as 1's" property is for prefixes of the obtained string 'w'. w=0011 a)even in length b)equal no. of 0's and 1's c) checking prefixes of 0011 {},{0},{00},{001},{0011} All prefixes contain at least as many 0's as 1's. w=0011 is a valid string. 6 votes 6 votes Lakshman Bhaiya commented Mar 2, 2018 reply Follow Share @bhuv i'm not getting this line please explain All prefixes contain at least as many 0's as 1's. {0011} this is valid why?? 0 votes 0 votes Mk Utkarsh commented Mar 2, 2018 reply Follow Share 0011 is valid because {},{0},{00},{001},{0011} in all these prefixes number of 0's $\geq$ number of 1's 4 votes 4 votes Mk Utkarsh commented Mar 2, 2018 reply Follow Share 1100 is not valid because there exist prefixes like {11},{110},{1} which violate the condition mentioned 2 votes 2 votes Lakshman Bhaiya commented Mar 2, 2018 i edited by Lakshman Bhaiya Feb 9, 2019 reply Follow Share at least means$($Kam se kam $0$ more than $1$ right$)$ but $0011$ violated the condition$?$ 0 votes 0 votes Mk Utkarsh commented Mar 2, 2018 reply Follow Share it simply means every prefix should follow this condition $\left | 0's \right | \geq \left | 1's \right |$ 11 votes 11 votes rambo commented Aug 1, 2018 reply Follow Share Yes utkarsh sir is right...0011 is valid string...here prefix can be 0,00,001 and in every prefixes here...we have atleast as many 0's as 1's...i.e #0's>=#1's 1 votes 1 votes Ayush Upadhyaya commented Oct 10, 2018 reply Follow Share $S->0S1|SS|\epsilon$ 3 votes 3 votes vupadhayayx86 commented Dec 10, 2018 reply Follow Share @Praveen Saini sir it means when n =1 we have 01 and for n=2 it's 0011 ,0101 for n=3 it's 000111,010101,001101,010011,001001? Sir please check if all strings are valid? 0 votes 0 votes mrinmoyh commented Sep 2, 2019 reply Follow Share @Praveen Saini sir, I can't connect the division of (n+1) after finding equal no. of 0's & 1's strings. equal no. of 0's & 1's is easy = 2nCn but after that, every prefix of ww has at least as many 0′s as 1′s = [2nCn]/(n+1) why dividing by (n+1). please help 3 votes 3 votes 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.