The Gateway to Computer Science Excellence

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

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

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

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

+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

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

@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

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

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

means 01 ,0011,00011,000011 are valid string

but 011,10,11 are not valid string

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

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

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

+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

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

52,345 questions

60,470 answers

201,795 comments

95,272 users