GATE CSE 1991 | Question: 16,a

Question

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.$

Comments

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.

---

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.

---

here the meaning at least asmany 0's as1's

number of zeros is  equal or greater than number of 1 and string should start with 0

000111,0011,00001,00011011

  its best example is balance parenthesis

means string always start with 0

Answer 1

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

Comments

@mrinmoy Did you get the answer for the (n+1) part?

---

@ankit3009 This question is same is balanced parantheses right? Considering 0 as closing braces and 1 as opening braces therefore answer is Catalan number.

---

Yes @adad20 it is same as balanced parenthesis.

Answer 2

• 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