The Gateway to Computer Science Excellence
+39 votes
2k views
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.$
in Combinatory by
retagged by | 2k views
0
sir , am not getting question... one side ,says no of 0 and 1 are equal then w and prefix ..not getting
+1
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
Sir...what is meaning of "every prefix of w...."
+1
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 }$.

2 Answers

+29 votes
Best answer

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 5th proof here http://en.wikipedia.org/wiki/Catalan_number

by
edited by
0
The "prefix" condition is not there.
0
Not able to understand that proof, can you explain , how "number of possible combinations of balanced parenthesizes. " == This problem  in easy words ?
+46

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. 

0
Thanks got it :)
0
r u considering even or odd length prefix @praveen sir ?? i am little confused ...
0
@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
cant i say that it is referring even length prefixes ...??
0
Why only even length ? Consider ((())), here one of the prefix is ((( or 0's and no of zeroes greater than 1's.
+2
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??
+12
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
+1
Thank u very much ... i hav to read the question more minutely ...
+4
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.
0

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?

+4
@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.
0
@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??
+2
0011 is valid because {},{0},{00},{001},{0011} in all these prefixes number of 0's $\geq$ number of 1's
+1
1100 is not valid because there exist prefixes like {11},{110},{1} which violate the condition mentioned
0

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

+6
it simply means every prefix should follow this condition $\left | 0's \right | \geq \left | 1's \right |$
0
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
+2
$S->0S1|SS|\epsilon$
0

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

 

+2

@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

0 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

by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,470 answers
201,795 comments
95,272 users