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

The "prefix" condition is not there.

---

Not able to understand that proof, can you explain , how "number of possible combinations of balanced parenthesizes. " == This problem  in easy words ?

---

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. 

---

Thanks got it :)

---

r u considering even or odd length prefix @praveen sir ?? i am little confused ...

---

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

---

cant i say that it is referring even length prefixes ...??

---

Why only even length ? Consider ((())), here one of the prefix is ((( or 0's and no of zeroes greater than 1's.

---

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??

---

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

---

Thank u very much ... i hav to read the question more minutely ...

---

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.

---

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?

---

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

---

@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??

---

0011 is valid because {},{0},{00},{001},{0011} in all these prefixes number of 0's $\geq$ number of 1's

---

1100 is not valid because there exist prefixes like {11},{110},{1} which violate the condition mentioned

---

at least means$($Kam se kam  $0$ more than $1$ right$)$ but $0011$ violated the condition$?$

---

it simply means every prefix should follow this condition $\left | 0's \right | \geq \left | 1's \right |$

---

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

---

$S->0S1|SS|\epsilon$

---

@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?

 

---

@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

---

@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