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.5k 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 38 votes 38 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.