The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
639 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.$
asked in Combinatory by Veteran (68.9k points)
retagged by | 639 views
sir , am not getting question... one side ,says no of 0 and 1 are equal then w and prefix ..not getting
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 Answer

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

 

answered by Veteran (332k points)
edited by
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.


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

32,693 questions
39,293 answers
110,109 comments
36,701 users